Minimizing Makespan in a Class of Reentrant Shops

M. Y. Wang, Suresh Sethi and S. L. van de Velde
Additional contact information
M. Y. Wang: University of Toronto, Toronto, Canada
S. L. van de Velde: Erasmus University, Rotterdam, The Netherlands

Operations Research, 1997, vol. 45, issue 5, 702-712

Abstract: We study the problem of scheduling a chain-reentrant shop, in which each job goes for its processing first to a machine called the primary machine, then to a number of other machines in a fixed sequence, and finally back to the primary machine for its last operation. The problem is to schedule the jobs so as to minimize the makespan. This problem is unary NP -hard for a general number of machines. We focus in particular on the two-machine case that is also at least binary NP -hard. We prove some properties that identify a specific class of optimal schedules, and then use these properties in designing an approximation algorithm and a branch-and-bound type optimization algorithm. The approximation algorithm, of which we present three versions, has a worst-case performance guarantee of 3/2 along with an excellent empirical performance. The optimization algorithm solves large instances quickly. Finally, we identify a few well solvable special cases and present a pseudo-polynomial algorithm for the case in which the first and the last operations of any job (on the primary machine) are identical.

Keywords: production/scheduling; deterministic; reentrant shop scheduling (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.5.702 (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:45:y:1997:i:5:p:702-712

Access Statistics for this article

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