Measures of subproblem criticality in decomposition algorithms for shop scheduling |
| |
| Authors: | H Aytug K Kempf R Uzsoy |
| |
| Affiliation: | 1. Department of Decision and Information Sciences, Warrington College of Business , University of Florida , Gainesville, FL, 32611, USA;2. Intel Corporation , MS CH3-68, 5000 W. Chandler Blvd, Chandler, AZ, 85226, USA;3. Laboratory for Extended Enterprises at Purdue, School of Industrial Engineering , Purdue University , 1287 Grissom Hall, West Lafayette, IN, 47907-1287, USA |
| |
| Abstract: | Work centre-based decomposition approaches, especially variants of the Shifting Bottleneck algorithm, have been very successful in solving job-shop-scheduling problems. These methods decompose the problem into subproblems involving a single work centre (usually a single machine), which they solve sequentially. We propose new measures of subproblem criticality and show via computational experiments that several of these provide solutions comparable in quality with those obtained from previous work in substantially less central processing unit time. |
| |
| Keywords: | |
|
|
