Modified bottleneck-based heuristic for large-scale job-shop scheduling problems with a single bottleneck

作者：Zuo Yan^*; Gu Hanyu; Xi Yugeng

来源：Journal of Systems Engineering and Electronics, 2007, 18(3): 556-565.

• job shop scheduling problem
• bottleneck
• shifting bottleneck procedure

A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a well-defined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck (SB) procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale job-shop scheduling problems.

• 出版日期2007-9
• 单位上海交通大学