Job Shop Scheduling with Due Dates and Operation Overlap Feasibility

Abstract The job shop problem with due dates is formulated to allow overlaps among successive operations on a job. Multiple transports of sub lots and existence of setup times are two applications where this formulation can result in technologically feasible schedules. A procedure is described for generating overlap schedules and it is applied to eight test problems from the literature. The resulting schedules are compared to alternative schedules involving tardiness or overtime. The results indicate that the procedure is effective in generating multiple transport schedules for the manager's consideration. The comparative data provide useful tradeoff information for evaluation of alternatives and indicate that multiple transport scheduling may sometimes be a very economical way to try to meet due dates without using overtime operations.