Workforce Minimization for a Mixed-Model Assembly Line

International audienceWe consider a paced production line consisting of several assembly stations, some of which are associated with sub-assembly stations. This line is intended for manufacturing products of different types. The sequence of technological operations is common for all types of products. The assignment of operations to the stations and their sequences on the stations are known, and they do not depend on the product type. Operations assigned to different stations are performed in parallel and those assigned to the same station are performed sequentially. The processing time of an operation depends on the number of workers performing this operation. If a worker is assigned to an operation, he is busy with this operation from its start till completion. Workers can switch between the operations at zero time. The problem is to assign workers to operations in one production cycle so that the total number of workers is minimized, provided that a given cycle time is satised. We prove that the problem is NP-hard, develop an integer linear programming formulation to solve it, and propose conventional and randomized heuristics. Optimal solution to any of 20 real industrial instances is found by a commercial solver in less than six minutes