An Operation Partitioning Problem for Automated Assembly System Design

This paper presents an operation partitioning problem (OPP) that arises from the design of an automated assembly system. To reduce the traffic flow of the system, the OPP assigns operations to machines so that the total number of movements of jobs between machines is minimized. This problem has applications in flexible manufacturing and VLSI design. In flexible manufacturing, OPP relates to a part grouping problem in which different parts are grouped into families. In VLSI design, this problem is related to a VLSI design problem in which a large circuit is partitioned into layers of small circuits. In this paper, we develop a simulated annealing heuristic that finds a near-optimal solution. Random problems are generated for examining the effectiveness of this heuristic.