Constructive Backtracking Heuristic for Hybrid Flowshop Scheduling with Limited Waiting Times
This paper deals with the hybrid flowshop scheduling problem with limited waiting time constraint. The problem is to determine a schedule that minimizes the makespan for a given set of jobs over a finite planning horizon respecting the constraint that for each job the waiting time between two consecutive stages cannot be greater than a given upper bound. To solve the problem, a constructive backtracking heuristic algorithm is developed and experimentally analyzed. The proposed algorithm operates on the technique of so-called recursive backtracking which constructs a schedule from sequenced job the first to the last, and for each job from the first stage to the last, while respecting the limited waiting time constraint. Computational experiments show that the proposed algorithm performs well both in efficiency and effectiveness.
constructive backtracking heuristic hybrid flowshop scheduling limited waiting times
Tieke Li Yan Li
Economics and Management School University of Science and Technology Beijing Beijing, China
国际会议
上海
英文
2007-09-21（万方平台首次上网日期，不代表论文的发表时间）