Article ID: | iaor2001689 |
Country: | United States |
Volume: | 47 |
Issue: | 1 |
Start Page Number: | 113 |
End Page Number: | 124 |
Publication Date: | Jan 1999 |
Journal: | Operations Research |
Authors: | Wu S. David, Storer Robert H., Byeon Eui-Seok |
Keywords: | decision |
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.