An analysis of heuristics for the parallel-machine flexible-resource scheduling problem

Richard Daniels, Barbara Hoopes and Joseph Mazzola

Annals of Operations Research, 1997, vol. 70, issue 0, 439-472

Abstract: We consider the parallel-machine flexible-resource scheduling (PMFRS) problem in which a set of jobs must be scheduled over a set of parallel machines, where the processing time of each job is a function of the amount of allocated resource. Resource flexibility provides the capability to dynamically reassign a renewable resource across machines to break processing bottlenecks and improve system performance as measured by schedule makespan. The PMFRS problem has many important applications, including production scheduling of manufacturing cells where a cross-trained work force can be dynamically reallocated among cells. The problem is also NP-hard, motivating the development of effective heuristics that approximately determine the allocation of resource to jobs, the sequence of jobs on each machine, and the associated job start times that minimize system makespan. This paper explores heuristics for the PMFRS problem, and in particular the application of tabu-search methodology to this problem setting. We review an existing heuristic (SBH), define two tabu-search heuristics, and discuss extensive computational experience with the procedures. The computational results indicate that the heuristics are effective in obtaining approximate solutions to the PMFRS problem. In particular, the approach that uses tabu-search methodology in tandem with SBH consistently yields high-quality solutions with modest computational effort. Copyright Kluwer Academic Publishers 1997

Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018946810121 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:70:y:1997:i:0:p:439-472:10.1023/a:1018946810121

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018946810121

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().