Minimizing functions of infeasibilities in a two-machine flow shop

Minimizing functions of infeasibilities in a two-machine flow shop

0.00 Avg rating0 Votes
Article ID: iaor2001215
Country: Netherlands
Volume: 121
Issue: 2
Start Page Number: 380
End Page Number: 393
Publication Date: Mar 2000
Journal: European Journal of Operational Research
Authors:
Keywords: computational analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.