HEURISTICS FOR TWO-MACHINE FLOWSHOP SCHEDULING WITH LIMITED WAITING TIME CONSTRAINTS
The flowshop scheduling problem with limited waiting time constraints widely exists in the production process featured by high temperature and continuity. The constraints require that the waiting time of any job between two consecutive machines is not greater than a given upper bound. The problem with two-machine settings and the objective of minimizing the makespan is one of the most important classes in the scheduling field. In this paper, a mixed integer programming model is proposed for the two-machine flowshop problem with limited waiting time constraints. The complexity analysis further shows that the problem is strongly NP-hard. Based on a deep discussion on the analytic properties of the problem, some heuristic algorithms are presented. Computational tests demonstrate the relationship between problem characteristics and algorithm performance, and show that both the model and the heuristics are feasible and efficient.
Flowshop Schueduling Limited WaitingTime Heuristic Algorithm Two-Machine Flowshop
Bailin Wang Tieke Li
School of Economics and Management,University of Science and Technology Beijing,Mailbox 756,Beijing 100083,China
国际会议
上海
英文
1-6
2009-08-02(万方平台首次上网日期,不代表论文的发表时间)