|
|
A Heuristic Algorithm for Flowshop Scheduling with Limited Waiting Times |
LI Tie-Ke, YIN Zhao-Tao |
University of Science and Technology Beijing, Beijing, China |
|
|
Abstract his paper focuses on flowshop scheduling with limited waiting times. Analytical relation between the upper bound of waiting times and feasible solutions is analyzed and certain property of the objective function is obtained, based on which a heuristic algorithm is proposed. The algorithm firstly sequences jobs by a heuristic rule combining greed with insertion, and then solves the violated waiting time constraints using recursive backtracking. Emulating experiments show that the proposed heuristic rule is superior to some commonused sequencing rules, especially when the limited waiting time constraints are tighter or the problem scale is larger.
|
Received: 17 April 2008
|
|
|
|
|
|
|