Assembly-line scheduling with concurrent operations and parallel machines

This paper addresses the assembly-line scheduling problem with concurrent operations per stage and parallel machines. The problem can be briefly described as the problem of sequencing a predetermined set of parts with known processing-time requirements through an r-station assembly line so that the makespan is minimized. A set of concurrent operations must be performed at each station on each part. This set of operations is usually part-dependent since different parts have different processing requirements. In this paper, we construct schedules in quadratic time for this strongly NP-hard problem with an absolute performance guarantee independent of the number of jobs. This makes our schedules asymptotically optimal as the number of jobs becomes very large. The implementation of our schedules facilitates the efficient use of concurrent operations and prevents the assembly line from degenerating into performing operations serially, which would result in low production rates. We utilize compact vector summation techniques and first construct a schedule for the case where each concurrent operation is performed by a single machine. We then generalize our schedule to the case where each concurrent operation is performed by a set of identical parallel machines.