A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Abstract

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.

Keywords:

• Flexible job-shop scheduling
• Filtered beam search
• Heuristic algorithm
• Combinatorial optimization

Acknowledgements

This work was supported by the National Science Foundation of China under Grant 60574054 and the Program for New Century Excellent Talents in the University of China (NCET 2006). The authors would like to express sincere appreciation to the anonymous referees for their detailed and helpful comments to improve the quality of the paper. Appreciation is also expressed to Dr Yu Jianbo for his invaluable advice and encouragement.