Minimizing Job Idleness in Deadline Constrained Environments

Reza H. Ahmadi and Uttarayan Bagchi
Additional contact information
Reza H. Ahmadi: University of California, Los Angeles, California
Uttarayan Bagchi: The University of Texas at Austin, Austin, Texas

Operations Research, 1992, vol. 40, issue 5, 972-985

Abstract: 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.

Keywords: inventory/production: inventory minimization through scheduling; production/scheduling: multiple machine deterministic sequencing (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.5.972 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:5:p:972-985

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().