Combinatorial design of a minimum cost transfer line with parallel operations at workstations
Abstract
We study a problem related to the optimal design of a transfer line. The line is to be used for a mass production of a single machine component, which requires a given set of operations to be performed. The line is a sequence of workstations, which number has to be decided, and each workstation has to be assigned a number of processing modules (blocks). A set of available blocks is given. There is the same cost associated with each workstation and there are di erent costs associated with the blocks. The problem is to design a minimum cost transfer line. The speci city of the problem is that all operations of the blocks assigned to the same workstation are performed in parallel so that the processing time of the machine component on the workstation is determined by the longest operation of this workstation, and the transfer line cycle time is determined by the longest operation of all the operations. Furthermore, there are inclusion, exclusion and precedence relations that restrict the assignment of the blocks and operations to the same workstation and the processing order of the operations on the transfer line. We suggest two combinatorial approaches for solving this problem, which are theoretically e cient if the number of blocks assigned to the same workstation and the number of workstations are upper bounded by given constants. The rst approach is to combinatorially enumerate all feasible solutions, and the second approach is to reduce the problem to the well studied maximum weight clique problem.