New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling

Robert H. Storer, S. David Wu and Renzo Vaccari
Additional contact information
Robert H. Storer: Department of Industrial Engineering, Lehigh University, Bethlehem, Pennsylvania 18015
S. David Wu: Department of Industrial Engineering, Lehigh University, Bethlehem, Pennsylvania 18015
Renzo Vaccari: Department of Industrial Engineering, Lehigh University, Bethlehem, Pennsylvania 18015

Management Science, 1992, vol. 38, issue 10, 1495-1509

Abstract: In this paper search heuristics are developed for generic sequencing problems with emphasis on job shop scheduling. The proposed methods integrate problem specific heuristics common to Operations Research and local search approaches from Artificial Intelligence in order to obtain desirable properties from both. The applicability of local search to a wide range of problems, and the incorporation of problem-specific information are both properties of the proposed algorithms. Two methods are proposed, both of which are based on novel definitions of solution spaces and of neighborhoods in these spaces. Applications of the proposed methodology are developed for job shop scheduling problems, and can be easily applied with any scheduling objective. To demonstrate effectiveness, the method is tested on the job shop scheduling problem with the minimum makespan objective. Encouraging results are obtained.

Keywords: local search; search neighborhoods; scheduling; combinatorial optimization (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (75)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.38.10.1495 (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:ormnsc:v:38:y:1992:i:10:p:1495-1509

Access Statistics for this article

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