具有交货时间窗约束的无等待流水车间调度模型与算法

中国机械工程 ›› 2010, Vol. 21 ›› Issue (19): 2334-2338,2344.

具有交货时间窗约束的无等待流水车间调度模型与算法

王晶1;王伟玲2

1.燕山大学,秦皇岛,066004

2.北京科技大学,北京,100083

出版日期:2010-10-10 发布日期:2010-10-20
基金资助:
河北省社会科学发展研究课题(200905005)；国家自然科学基金资助项目(71071134)；河北省科学技术研究与发展计划资助项目(10457203D-16)
Hebei Provincial Social Science Development Research Program of China（No. 200905005）;

National Natural Science Foundation of China（No. 71071134）;
Hebei Provincial S&T Research and Development Program of Ministry of Education of China（No. 10457203D-16）

Model and Algorithm for No-wait Flow Shop Scheduling Problem Based on E/T

Wang Jing1;Wang Weiling2

1.Yanshan University, Qinhuangdao, Hebei,066004

2.University of Science and Technology Beijing,Beijing,100083

Online:2010-10-10 Published:2010-10-20
Supported by:

Hebei Provincial Social Science Development Research Program of China（No. 200905005）;

National Natural Science Foundation of China（No. 71071134）;
Hebei Provincial S&T Research and Development Program of Ministry of Education of China（No. 10457203D-16）

摘要/Abstract

摘要：

针对目标函数为提前/拖期惩罚最小、具有交货时间窗要求的无等待流水车间调度问题,建立了约束满足模型,提出了约束传播与邻域搜索相结合的求解方法。在求解过程中,首先应用约束传播的思想通过逐步安排最小加工时间窗工件构造初始调度,在此基础上利用变邻域搜索逐步迭代以获取满意调度,为避免陷入局部极值,迭代过程中采用多重交换邻域的扰动策略。仿真实验证明了算法的有效性。

关键词:

无等待流水车间调度, 提前/拖期, 邻域搜索, 约束满足

Abstract:

For the no-wait flow shop scheduling problem with a delivery time window to minimize the punishment of the E/T, a constraint satisfaction model was established, and a algorithm was proposed based on constraint propagation and neighborhood search. Firstly, an initial scheduling was generated using heuristic method embedded constraint propagation. Secondly, a swap search based on neighborhood structure was designed for iterate operation, in order to avoid falling into local optimum, a disturbance strategy based on dynamic swap was used.The simulation results show the effectiveness of the algorithm.

Key words: no-wait flow shop scheduling, E/T(earliness/tardiness), neighborhood search, constraint satisfaction

中图分类号:

TP273

王晶, 王伟玲.

具有交货时间窗约束的无等待流水车间调度模型与算法

[J]. 中国机械工程, 2010, 21(19): 2334-2338,2344.

WANG Jing, WANG Wei-Ling.

Model and Algorithm for No-wait Flow Shop Scheduling Problem Based on E/T

[J]. China Mechanical Engineering, 2010, 21(19): 2334-2338,2344.

参考文献

[1]Liaw C F. An Efficient Simple Metaheuristic for Minimizing the Makespan in Two--machine No-wait Job Shops [J].Computers & Operations Research, 2008, 35(10) :3276-3283.
[2]Bouquard J L. Two--machine Flow Shop Scheduling Problems with No--wait Jobs[J]. Operations Research Letters, 2005, 33(3): 255-262.
[3]常俊林[1],邵惠鹤[1].两机零等待流水车间调度问题的启发式算法[J].计算机集成制造系统,2005,11(8):1147-1153.
[4]Koulamas C, Kyparisis J. The Three--stage As sembly Flow Shop Scheduling Problem[J]. Computers & Operations Research, 2001, 28(7) :689- 704.
[5]Aldowaisan T, Allahverdi A. New Heuristics for No--wait Flowshops to Minimize Makespan[J]. Computers & Operations Research, 2003, 30(8):1219-1231.
[6]Aldowaisan T, Allahverdi A. New Heuristics for M-machine No--wait Flow Shop to Minimize Total Completion Time[J].The International Journal of Management Science, 2004, 32(5):345-352.
[7]Grabowski J, Pempera J. Some Local Search Algorithm Search for Nowait Flow--shop Problem with Makespan Criterion[J]. Compmers & Operations Research, 2005, 32(8) :2197-2212.
[8]Dileepan P. A Note on Minimizing Maximum Lateness in a Two--machine No--wait Ftowshop[J].Computers in Operations Research, 2004 (31) 2111-2115.
[9]Sung C S, Min J 1. Scheduling in a Two--machine Flowshop with Batch Processing Machine (s) for Earliness/Tardiness Measure under a Common due Date [J]. European Journal of Operational Re search, 2001, 131(2) :211-215.
[10]王莉,王梦光.基于准时制的零等待混合Flow Shop调度问题[J].东北大学学报：自然科学版,1998,19(4):349-351.
[11]Ronconi D P, Luis R S. Some Heuristic Algorithms for Total Tardiness Minimization in a Flowshop with Blocking [J]. The International Journal of Management Science, 2009,37(2) : 272- 281.