Line configuration to minimize setup costs

A problem is studied in which a production line consisting of a number of workstations has to be designed to produce parts of ff types. Each part of a specific type requires a given set of operations to be executed. There is an upper bound on the number of operations that can be assigned to any single station. Parts move along the stations in the same direction one after another, and a station is set up if at least one operation is executed at this station for the next part. Setup costs are part type dependent. A decision has to be made about the number of stations and an assignment of operations to the stations. The primary objective is to minimize the number of stations with a secondary objective of minimizing total setup cost. Properties of an optimal solution are established and optimal algorithms are developed for the cases f=2f=2, f=3f=3 and arbitrary ff. The algorithms employ combinatorial optimization and linear programming techniques. They run in a constant time if ff is a constant.