Workforce minimization for a mixed-model assembly line in the automotive industry

A paced assembly line consisting of several workstations is considered. This line is intended to assemble products of different types. The sequence of products is given. The sequence of technological tasks is common for all types of products. The assignment of tasks to the stations and task sequence on each station are known and cannot be modified, and they do not depend on the product type. Tasks assigned to the same station are performed sequentially. The processing time of a task depends on the number of workers performing this task. Workers are identical and versatile. If a worker is assigned to a task, he/she works on this task from its start till completion. Workers can switch between the stations at the end of each task and the time needed by any worker to move from one station to another one can be neglected. At the line design stage, it is necessary to know how many workers are necessary for the line. To know the response to this question we will consider each possible takt and assign workers to tasks so that the total number of workers is minimized, provided that a given takt time is satisfied. The maximum of minimal numbers of workers for all takts will be considered as the necessary number of workers for the line. Thus, the problem is to assign workers to tasks for a takt. We prove that this problem is NP-hard in the strong sense, we develop an integer linear programming formulation to solve it, and propose conventional and randomized heuristics.