Sequence-dependent setup times in a two-machine makespan job-shop scheduling problem

Abstract

job-shop problem of minimizing the schedule length (makespan) for processing n jobs on two machines with sequence-dependent setup times and removal times is consider. The processing of each job includes at most two operations that have to be non-preemptive. Machine routes may differ from job to job. If all setup and removal times are equal to zero, this problem is polynomially solvable via Jackson's permutations, otherwise it is NP-hard even if each of n jobs consists of one operation on the same machine. We present sufficient conditions when Jackson’s permutations may be used for solving the two-machine job-shop problem with sequence-dependent setup times and removal times. For the general case of this problem, the results obtained provide polynomial lower and upper bounds for the makespan which are used in a branch-and-bound algorithm.