Minimizing setup costs in a transfer line design problem with sequential operation processing

International audienceDesign problems constitute the first stage in developing a machining transfer line. This paper is concerned with a problem in which a transfer line has to be designed in an optimal way to produce parts of different types. Each part of a specific type requires a unique set of operations to be executed on the stations. Parts move along the stations in the same direction one after another in a given sequence, and a station is set up if at least one operation is executed on this station. Setup costs and times are part-type dependent. Each operation has its size, which is the number of standard tools required to perform this operation, and its processing time. Operations on the same part assigned to the same station are performed sequentially. Re-design, i.e., re-assignment of operations when switching from one type part to another is not allowed. Precedence relations are given on the superset of all operations. There is an upper bound on the total size of operations assigned to the same station, and an upper bound on the time that a part of a given type stays on the same station for all types. The primary objective is to minimize the number of stations. The secondary objective is to minimize the total setup cost. We establish computational complexity of various special cases of this problem, present constructive heuristic algorithms, integer linear programs as well as computational results. These results are applicable in designing transfer lines for mechanical parts manufacturing by multi-spindle turret heads in situations where the station costs are the primary concern and the station setup costs are the secondary concern of the designer