Job shop scheduling with setup times, deadlines and precedence constraints Export

@article{citeulike:4383822, abstract = {Abstract\ \ In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art.}, author = {Balas, Egon and Simonetti, Neil and Vazacopoulos, Alkis}, citeulike-article-id = {4383822}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s10951-008-0067-7}, citeulike-linkout-1 = {http://www.springerlink.com/content/f7386064p1h87357}, day = {1}, doi = {10.1007/s10951-008-0067-7}, journal = {Journal of Scheduling}, keywords = {jobshop, phd, scheduling}, month = {August}, number = {4}, pages = {253--262}, posted-at = {2009-04-23 08:54:57}, priority = {5}, title = {Job shop scheduling with setup times, deadlines and precedence constraints}, url = {http://dx.doi.org/10.1007/s10951-008-0067-7}, volume = {11}, year = {2008} }

TY - JOUR ID - citeulike:4383822 L3 - citeulike-article-id:4383822 N2 - Abstract  In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art. IS - 4 JF - Journal of Scheduling EP - 262 TI - Job shop scheduling with setup times, deadlines and precedence constraints VL - 11 SP - 253 KW - jobshop KW - phd KW - scheduling AU - Balas, Egon AU - Simonetti, Neil AU - Vazacopoulos, Alkis PY - 2008/08/01/ UR - http://dx.doi.org/10.1007/s10951-008-0067-7 ER -