A Graph-Theoretic Decomposition of the Job Shop Scheduling Problem to Achieve Scheduling Robustness

S. David Wu, Eui-Seok Byeon and Robert H. Storer
Additional contact information
S. David Wu: Lehigh University, Bethlehem, Pennsylvania
Eui-Seok Byeon: The Korea Transport Institute, Seoul, Korea
Robert H. Storer: Lehigh University, Bethlehem, Pennsylvania

Operations Research, 1999, vol. 47, issue 1, 113-124

Abstract: In this paper we study the weighted tardiness job-shop scheduling problem, taking into consideration the presence of random shop disturbances. A basic thesis of the paper is that global scheduling performance is determined primarily by a subset of the scheduling decisions to be made. By making these decisions in an a priori static fashion, which maintains a global perspective, overall performance efficiency can be achieved. Further, by allowing the remaining decisions to be made dynamically, flexibility can be retained in the schedule to compensate for unforeseen system disturbances. We develop a decomposition method that partitions job operations into an ordered sequence of subsets. This decomposition identifies and resolves a “crucial subset” of scheduling decisions through the use of a branch-and-bound algorithm. We conduct computational experiments that demonstrate the performance of the approach under deterministic cases, and the robustness of the approach under a wide range of processing time perturbations. We show that the performance of the method is superior, particularly for low to medium levels of disturbances.

Keywords: production/scheduling; approximations/heuristic; job-shop scheduling problem; decision analysis; risk; robust optimization and control; programming; integer; algorithms; branch-and-bound; combinatorial optimization (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.1.113 (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:47:y:1999:i:1:p:113-124

Access Statistics for this article

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