Transfer line design problem with parallel operations at workstations as a simple set partitioning problem

http://www.emse.fr/spip/IMG/pdf/RR_2009-500-007_abstract.pdfWe consider the design of a transfer line to be used for a repetitive execution of a given set of operations on the same machine part. The line is a sequence of workstations equipped with processing modules (blocks) each of which performs speci c operations. The machine part moves along the workstations in the same direction. There is the same cost associated with each workstation and there are di erent costs associated with the blocks. The problem is to determine the number of workstations, to select a set of blocks and to assign selected blocks to the workstations so that each operation is performed exactly once and the total cost is minimized. The speci city of the problem is that all operations of the same workstation are performed in parallel, and 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 a reduction of this transfer line design problem to a simple set partitioning problem. The reduction is based on a new concept of a feasible workstation