SEQUENCE-DEPENDENT SETUP AND CLEAN-UP TIMES IN A TWO-MACHINE JOB-SHOP WITH MINIMIZING MAKESPAN

What is it about?

The job-shop scheduling problem of minimizing the makespan for processing n jobs by one or two machines with sequence-dependent setup times and clean-up times is addressed. The processing of each job includes at most two operations that have to be non-preemptive. Machine routes may differ from job to job. We present sufficient conditions when Jackson's pair of job permutations may be used for solving the two-machine job-shop scheduling problem with sequence-dependent setup times and clean-up times. For the general case of the latter problem, the results obtained provide polynomial lower and upper bounds for the objective function which may be used in an implicit enumeration technique, e.g., in a branch-and-bound algorithm.

Featured Image