A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness
成果类型：
Article
署名作者：
Wu, SD; Byeon, ES; Storer, RH
署名单位：
Lehigh University; Korea Transport Institute
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.1.113
发表日期：
1999
页码：
113-124
关键词：
摘要：
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.