Robust Scheduling on Flexible Job Shop with Uncertain Processing Time

Abstract

Abstract:

This paper investigated the flexible job-shop scheduling problem (FJSP) with uncertain processing time in a multi-type and low-volume environment. A minimax regret based robust scheduling model was built to minimize the makespan. A novel sequential search rule was put forward to reduce the calculation amount of the algorithm and a two stage genetic algorithm was designed to figure out the redundant and optimal solutions. Orthogonal test was designed to optimize significant parameters, and then, a simulation model was established to evaluate the robustness and objective performance of the algorithm. The results show the proposed algorithm has a better performance than genetic algorithm on flexible job-shop scheduling problem under uncertain and dynamic environment.

Key words: processing time disturbance, flexible job-shop, robustness;sequential search

摘要：

针对中小批量环境下加工时间不确定的柔性作业车间调度问题，采用冗余处理方法构建了以最大完工时间为目标的鲁棒调度模型。为降低算法的搜索规模和提高算法的求解速度，提出了顺序搜索机制，并设计两阶段遗传算法，分阶段获取冗余状态和最优结果。采用某柔性生产线的数据进行正交试验，优化了算法关键参数，并构建了柔性生产线仿真模型，对调度结果的鲁棒性和优化目标性能进行了分析。结果表明，该算法在目标性能和鲁棒性上都显著优于标准遗传算法，能有效处理加工时间不确定的柔性作业车间调度问题。

关键词: 加工时间扰动, 柔性作业车间, 鲁棒性, 顺序搜索

CLC Number:

TH166

Wang Junliang, Zhang Jie, Qin Wei, Yin Li, Chen Dingfang. Robust Scheduling on Flexible Job Shop with Uncertain Processing Time[J]. China Mechanical Engineering, 2015, 26(5): 627-632.

汪俊亮, 张洁, 秦威, 银莉, 陈定方. 加工时间不确定的柔性作业车间鲁棒调度方法[J]. 中国机械工程, 2015, 26(5): 627-632.

References

[1]Van S，Demeulemeester L，Herroelen W. A Classification of Predictive-reactive Project Scheduling Procedures[J]. Journal of Scheduling, 2007, 10(3): 195-207.
[2]陈庭贵，琚春华.多干扰的资源约束项目调度问题[J].计算机集成制造系统，2012,18(11)：2409-2418.
Chen Tinggui，Ju Chunhua.Resource-constrained Project Scheduling Problem with Multi-factor Disruptions[J].Computer Integrated Manufacturing System，2012,18(11)：2409-2418.
[3]Herroelen W，Leus R.Robust and Reactive Project Scheduling: a Review and Classification of Procedures[J].International Journal of Production Research，2004，42(8)：1599-1620.
[4]Novas M, Henning P. Reactive Scheduling Framework Based on Domain Knowledge and Constraint Programming[J]. Computers & Chemical Engineering, 2010, 34(12): 2129-2148.
[5]Xia Y, Chen B, Yue J. Job Sequencing and Due Date Assignment in a Single Machine Shop with Uncertain Processing Times[J]. European Journal of Operational Research, 2008, 184(1): 63-75.
[6]李平，顾幸生.不确定条件下不同交货期窗口的JobShop调度[J].管理科学学报，2004,2：22-26.
Li Ping, Gu Xingsheng. Job Shop Scheduling with Uncertain Processing Time and Distinct Due Windows[J]. Journal of Management Sciences in China, 2004,7(2): 22-26.
[7]Zhang M. Two-stage Minimax Regret Robust Uncapacitated Lot-sizing Problems with Demand Uncertainty[J]. Operations Research Letters, 2011, 39(5): 342-345.
[8]鲁建厦，施锦峰，李修琳，等.一类已知概率分布下的混合车间鲁棒调度问题研究[J].中国机械工程，2010,21(19)：2328-2333.
Lu Jianxia, Shi Jingfeng, Li Xiuling, et al. Study on Hybrid Shop Robust Scheduling Problem with Known Probability Distribution[J]. China Mechanical Engineering, 2010, 21(19): 2328-2333.
[9]Ponsich A, Bonfill A, Espua A, et al. Genetic Algorithms for the Scheduling of Multiproduct Batch Plants within Uncertain Environment[J]. Computer Aided Chemical Engineering, 2007, 24: 619-624.
[10]Hufner M, Tometzki T, Engell S. Two-layer Planning and Scheduling of Batch Production Processes under Uncertainty[J]. Computer Aided Chemical Engineering, 2009, 27: 1197-1202.
[11]Jensen T.Robust and Flexible Scheduling with Evolutionary Computation[D].Arhus:University of Arhus，2001.
[12]Rahmani D, Heydari M. Robust and Stable Flow Shop Scheduling with Unexpected Arrivals of New Jobs and Uncertain Processing Times[J]. Journal of Manufacturing Systems, 2013.