Minimizing Job Idleness in Deadline Constrained Environments

The paper presents a formulation of an n-job, m-machine flowshop problem whose objective is to determine a processing sequence of jobs that minimizes total job idleness subject to meeting job deadlines. A mirror image problem is defined with the property that there is a one-to-one correspondence between the feasible schedules of the original problem and the feasible schedules of the mirror image problem. The mirror image problem is a traditional scheduling problem with a regular performance measure, whereas the performance measure in the original problem is not regular. The equivalence of the original problem and its mirror image problem enables us to solve one by solving the other. One special case of the original problem is investigated. It concerns minimization of total job idleness in a 2-machine flowshop. For this NP-hard problem we study permutation schedules under sufficient conditions of feasibility. We present complexity results, dominance properties, bounding criteria, and computational experience with a branch-and-bound procedure.