Minimizing functions of infeasibilities in a two-machine flow shop

Abstract

We consider a class of schedules obtained in the following way. In a schedule of processing n jobs in the two-machine flow shop we shift the jobs on the second machine backward in time to complete them by a deadline which is less than the optimal makespan. For the obtained schedule, the infeasibility of a job is defined as the length of the time interval for which the processing of this job on the first machine is not completed but its processing on the second machine has already started. A given function of the infeasibilities is to be minimized. We prove that the permutation version of this problem is equivalent to a single machine scheduling problem of minimizing an analogous function of tardiness. A number of complexity results for the nonpermutation version of this problem is also obtained. The permutation version of the problem under precedence constraints is investigated. As a side result, we find a new solvable case for the two-machine flow shop scheduling problem under precedence constraints to minimize makespan.