A three-phase algorithm for flowshop scheduling with blocking to minimize makespan

作者：Wang Cheng; Song Shiji^*; Gupta Jatinder N D; Wu Cheng

来源：Computers & Operations Research, 2012, 39(11): 2880-2887.

DOI：10.1016/j.cor.2012.02.020

• Flowshop scheduling with zero-buffer and blocking
• Priority rule
• NEH-insert
• Three-phase algorithm
• Simulated annealing with local search
• Pruning procedure

This paper proposes a three-phase algorithm (TPA) for the flowshop scheduling problem with blocking (BFSP) to minimize makespan. In the first phase, the blocking nature of BFSP is exploited to develop a priority rule that creates a sequence of jobs. Using this as the initial sequence and a variant of the NEH-insert procedure, the second phase generates an approximate solution to the problem. Then, utilizing a modified simulated annealing algorithm incorporated with a local search procedure, the schedule generated in the second phase is improved in the third phase. A pruning procedure that helps evaluate most solutions without calculating their complete makespan values is introduced in the local search to further reduce the computational time needed to solve the problem. Results of the computational experiments with Taillard's benchmark problem instances show that the proposed TPA algorithm is relatively more effective and efficient in minimizing makespan for the BFSP than the state-of-the-art procedures. Utilizing these results, 53 out of 60 new tighter upper bounds have been found for large-sized Taillard's benchmark problem instances.

• 出版日期2012-11
• 单位清华大学