任务工时不确定的模具车间前摄性调度研究

中国机械工程 ›› 2011, Vol. 22 ›› Issue (21): 2560-2566.

任务工时不确定的模具车间前摄性调度研究

吴立华;陈新度;陈庆新;陈新

广东工业大学广东省计算机集成制造重点实验室,广州,510006

出版日期:2011-11-10 发布日期:2011-11-16
基金资助:
国家自然科学基金资助项目(50875051)；广东省自然科学基金团队资助项目(5200197)
National Natural Science Foundation of China（No. 50875051）;
Team Program of Guangdong Provincial Natural Science Foundation of China（No. 5200197）

Research on Proactive Scheduling of Mould Shop Floor with Uncertain Processing Times

Wu Lihua;Chen Xindu;Chen Qingxin;Chen Xin

Guangdong Key Laboratory of Computer Integrated Manufacturing,Guangdong University of Technology, Guangzhou, 510006

Online:2011-11-10 Published:2011-11-16
Supported by:

National Natural Science Foundation of China（No. 50875051）;
Team Program of Guangdong Provincial Natural Science Foundation of China（No. 5200197）

摘要/Abstract

摘要：

由于模具生产属于非重复性生产模式,各工序的工时具有很强的随机不确定性,这给模具车间制定合理可行的作业计划带来了一定的困难。针对这一实际问题,提出了一种考虑任务工时不确定性的前摄性车间调度算法。首先,分析了模具精加工环节的两道关键工序对制造系统稳定性的影响,并基于工序的工时不确定特性,建立了任务工时不确定的离散概率模型;然后,以调度方案的稳定度作为优化目标,构建了两阶段流水车间前摄性调度模型,针对该模型,提出了一种变宽集束搜索求解算法;最后,将该算法与定宽集束搜索算法进行对比分析,结果表明该算法能很好地兼顾求解质量和计算时间。



关键词:

前摄性调度, 工时不确定, 流水车间, 模具制造

Abstract:

Due to non-repetitive manufacturing of mould & die industry, the processing time of operations is random uncertainty. Hence, it is difficult to make a reasonable and feasible baseline schedule in the mould shop floor. To deal with this problem, a proactive scheduling algorithm with uncertain processing times was proposed herein. Firstly, how did two critical operations in the mould finishing stage to impact the stability of whole manufacturing system was analyzed. Based on the characteristics of uncertainty of processing time quota, a discrete probability model of processing time uncertainty was developed. Secondly, a proactive scheduling model of two-stage flow shop was built, whose objective was schedule stability. Furthermore, a width-variable beam search(VBS) algorithm was presented for solving the proactive scheduling model. Finally, the comparative analysis with the fixed width beam search(FBS) was pursued. And, the computational results show that the presented algorithm has a good balance between solution quality and computation time.

Key words: proactive scheduling, processing time uncertainty, flow shop, manufacturing of mould

中图分类号:

TP391

吴立华, 陈新度, 陈庆新, 陈新.

任务工时不确定的模具车间前摄性调度研究

[J]. 中国机械工程, 2011, 22(21): 2560-2566.

TUN Li-Hua, CHEN Xin-Du, CHEN Qiang-Xin, CHEN Xin.

Research on Proactive Scheduling of Mould Shop Floor with Uncertain Processing Times

[J]. China Mechanical Engineering, 2011, 22(21): 2560-2566.

参考文献

[1]Goren S, Sabuncuoglu I. Robustness and StabilityMeasures for Scheduling: Single- machine Environment[J]. IIE Transactions, 2008, 40(1) :66-83.
[2]Aytug H, Lawley M, Mckay K, et al. Executing Production Schedules in the Face of Uncertainties: a Review and Some Future Directions[J]. European Journal of Operational Research, 2005, 161: 86- 110.
[3]Davenport A J, Beck J C. A Survey of Techniques for Scheduling with Uncertainty[EB/OL]. http:// eil. utoronto, ca/profiles/chris/chris, papers, html, 2000/2010-06-01.
[4]van de Vonder S, Demeulemeester E, Herroelen W. Proactive Heuristic Procedures for Robust Pro- jeet Seheduling:an Experimental Analysis[J]. Eu- ropean Journal of Operational Research, 2008, 189 (3) : 723-33.
[5]Bidot J, Vidal T, Laborie P, et al. A Theoretic and Practical Framework for Scheduling in a Stochastic Environment[J]. Journal of Scheduling, 2009, 10 (3) : 315-344.
[6]Leus R, Herroelen W. Scheduling for Stability in Single--machine Production Systems[J]. Journal of Scheduling, 2007, 10: 223-235.
[7]Sabuncuoglu I, Goren S. Hedging Production Schedules Against Uncertainty in Manufacturing Environment with a Review of Robustness and Sta- bility Research[J]. International Journal of Computer Integrated Manufacturing, 2009, 22(2):138- 157.
[8]Mehta S V, Uzsoy R. Predictable Scheduling of a Single Machine Subject to Breakdowns[J]. International Journal of Computer Integrated Manufacturing, 1999, 12(1):15-38.
[9]O'Donovan R, Uzsoy R, McKay K N. Predictable ScheduLing of a Single Machine with Breakdowns and Sensitive Jobs[J]. International Journal of Production Research, 1999, 37(18):4217-4233.
[10]Li Q, Wang B. A Stable Scheduling for Single Machine under Uncertainty[C]//Proceedings of the IEEE International Conference on Automation and Logistics. Shenyang, 2009 : 526-531.
[11]Leus R, Herroelen W. The Complexity of Ma- chine Scheduling for Stability with a Single Dis- rupted Job [J]. Operations Research Letters, 2005, 33:151-156.
[12]李英杰[1],陈庆新[1],陈新度[1],陈新[1].多属性的虚拟企业并行协商项目规划算法[J].机械工程学报,2005,41(2):215-222.
[13]李英杰[1],陈庆新[1],陈新度[1],陈新[1].多属性的虚拟企业串行协商项目规划[J].中国机械工程:598-603.
[14]Johnson S M. Optimal Two--and Three--stage Production Schedules with Set--up Times Includ- ed[J]. Naval Research Logistics Quarterly, 1954, 1:61-68.
[15]Pinedo M L. Scheduling Theory, Algorithms, and Systems[M]. London:Springer, 2008.
[16]Sabuncuoglu I, Bayiz M. Job Shop Scheduling with Beam Search[J]. European Journal of Opera- tional Research, 1999, 118:390-412.
[17]XErenay F S, Sabuncuoglu I, Toptal A. New Solu- tion Methods for Single Machine Bicriteria Scheduling Problem: Minimization of Average Flowtime and Number of Tardy Jobs[J]. European Journalof Operational Research, 2010, 201:89-98.
[18]Valente J M S, Alves R. Beam Search Algorithms for the Single Machine Total Weighted Tardiness Scheduling Problem with Sequence- dependent Setups[J]. Computers & Operations Research, 2008, 35:2388-2405.