A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness

A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness

0.00 Avg rating0 Votes
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: , ,
Keywords: decision
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.

Reviews

Required fields are marked *. Your email address will not be published.