The complexity of two-job shop problems with multi-purpose unrelated machines

This paper deals with scheduling problems of two jobs with multi-purpose unrelated machines. In such problems, two jobs are to be scheduled in order to minimize a regular objective function. Each job consists of a sequence of operations that must be accomplished according to its manufacturing process. Each operation can be performed by any machine from a given set associated with the operation, and its processing time depends on the selected machine. Makespan minimization and total-completion time minimization problems are proved to be NP-hard. The NP-hardness remains true even if the preemption of operations is allowed. In the case where the routing of one job is given, i.e. a job-shop job, a polynomial algorithm is proposed for both cases with and without the preemption assumption. The two algorithms generalize the classical geometric approach.