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

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 pr imarily by a subset of the scheduling decisions to be made. By making these decisions in an a priori static fashion, which maintains a global perspect ive, overall performance efficiency can be achieved. Further, by allowing t he remaining decisions to be made dynamically, flexibility can be retained in the schedule to compensate for unforeseen system disturbances. We develo p a decomposition method that partitions job operations into an ordered seq uence of subsets. This decomposition identifies and resolves a ';crucial su bset" of scheduling decisions through the use of a branch-and-bound algorit hm. We conduct computational experiments that demonstrate the performance o f the approach under deterministic cases, and the robustness of the approac h under a wide range of processing time perturbations. We show that the per formance of the method is superior, particularly for low to medium levels o f disturbances.