MINIMIZING LMAX AND CMAX IN A JOB SHOP PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES

This paper presents an approach for solving a job shop problem with sequence-dependent setup times where the objective is to minimize maximum lateness and makespan. This approach consists of using the “Shifting Bottleneck Procedure”, designed for the job shop problem with the makespan objective, while introducing two major modifications: (1) the use of a new dispatching rule that takes into account the setup times and the due dates; (2) explicit use of the due dates, to optimize both objectives, when solving each one-machine problem generated by this procedure. Encouraging results are obtained through an extensive computational experiment using a set of benchmark instances.