随机工时下的多目标柔性作业车间鲁棒调度问题

摘要/Abstract

摘要： 针对工时不确定条件下的多目标柔性作业车间调度问题，采用2个不确定参数描述随机工时的波动程度和约束条件允许违背程度，将不确定条件下的柔性作业车间调度问题模型转换成确定条件下的鲁棒对等问题模型。在算法设计中采用全局非支配解集保存每代进化过程中产生的非支配解，并选择全局非支配解集中的个体参与变异操作。在交叉和变异操作之后，设计了一种基于变邻域结构的局部搜索策略。最后，运用该算法求解经典基准算例，验证了其有效性。

关键词: 随机工时, 柔性作业车间, 多目标, 鲁棒对等模型

Abstract: Multiobjective flexible job shop schedule problem with uncertain processing time was studied. Two uncertain parameters were adopted to describe the degree of disturbance volatility and allowable constraints violence respectively. A robust optimization approach to translate multiobjective flexible job shop scheduling problem into deterministic robust counterpart problem was proposed. A set of global nondominated solution was adopted to preserve the best solutions in every generation, and the solution which in the set was selected to participate in the mutation operation. After crossover and mutation, a local search strategy was proposed based on neighborhood structure. Several benchmark problems were handled by the algorithm, the results indicate that it is effective for such problem.

Key words: rand process time, flexible job shop, multiobjective, robust counterpart model

中图分类号:

TP18

朱传军, 邱文, 朱孟周, 陈光, 张超勇. 随机工时下的多目标柔性作业车间鲁棒调度问题[J]. 中国机械工程.

Zhu Chuanjun, Qiu Wen, Zhu Mengzhou, Chen Guang, Zhang Chaoyong. Multiobjective Flexible Job Shops Robust Scheduling Problem under Stochastic Processing Times[J]. China Mechanical Engineering.

参考文献

[1]于晓义,孙树栋,王彦革.面向随机加工时间的车间作业调度[J].中国机械工程,2008,19(19):2319-2324.

Yu Xiaoyi, Sun Shudong, Wang Yange. Researche on Stochastic Processing Time Oriented Job-shop Scheduling[J]. China Mechanical Engineering, 2008, 19(19): 2319-2324

[2]Honkomp S J, Mockus L, Reklaitis G V. Robust Scheduling with Processing Time Uncertainty[J]. Computers & Chemical Engineering, 1997, 21(10): S1055-S1060.

[3]Bonfill A, Espua A, Puigjaner L. Proactive Approach to Address the Uncertainty in Short-term Scheduling[J]. Computers & Chemical Engineering, 2008, 32(8): 1689-1706.

[4]徐震浩, 顾幸生. 不确定条件下具有零等待的流水车间免疫调度算法[J]. 计算机集成制造系统, 2004, 10(10):1247-1251.

Xu Zhenghao, Gu Xingsheng. Immune Scheduling Algorithm for Flow Shop under Uncertainty with Zero Wait[J]. Computer Intergrated Manufacturing Systems, 2004,10(10):1247-1252.

[5]He C, Qiu D, Guo H. Solving Fuzzy Job Shop Scheduling Problem Based on Interval Number Theory[J]. Lecture Notes in Electrical Engineering, 2013, 211:393-401.

[6]Lei D. Population-based Neighborhood Search for Job Shop Scheduling with Interval Processing Time[J]. Computers & Industrial Engineering, 2011, 61(4): 1200-1208.

[7]Lei D. Interval Job Shop Scheduling Problems[J]. International Journal of Advanced Manufacturing Technology, 2012, 60(1/4):291-302.

[8]Janak S L, Lin X, Floudas C A. A New Robust Optimization Approach for Scheduling under Uncertainty : II. Uncertainty with Known Probability Distribution[J]. Computers & Chemical Engineering, 2007, 31(3):171-195.

[9]唐秋华, 何明, 何晓霞,等. 随机工时下柔性加工车间的鲁棒优化调度方法[J]. 计算机集成制造系统, 2015, 21(4):1002-1012.

Tang Qiuhua, He Ming, He Xiaoxia, et al. Robust Optimization Scheduling of Flexible Job Shops under Stochastic Processing Times[J]. Computer Integrated Manufacturing Systems,2015,21(4):1002-1012.

[10]Lin X, Janak S L, Floudas C A. A New Robust Optimization Approach for Scheduling under Uncertainty: I. Bounded Uncertainty[J]. Computers & Chemical Engineering, 2004, 28(6/7):1069-1085.

[11]Xue F, Sandeson A C, Graves R J. Pareto-based Multi-objective Differential Evolution[C]//Proceedings of the 2003 Congress on Evolutionary Computation. Washington D C, 2003:862-869.

[12]汪双喜, 张超勇, 刘琼,等. 不同再调度周期下的柔性作业车间动态调度[J]. 计算机集成制造系统, 2014, 20(10): 2470-2478.

Wang Shuangxi, Zhang Chaoyong, Liu Qiong, et al. Flexible Job Shop Dynamic Scheduling under Different Reschedule Periods[J].Computer Integrated Manufacturing Systems,2015,21(4):1002-1012.

[13]张利平.作业车间预反应式动态调度理论与方法研究：[D]. 武汉：华中科技大学，2013.

[14]王凌.智能优化算法及其应用[M].北京：清华大学出版社，2001.

[15]Xia W J, Wu Z M. An Effective Hybrid Optimization Approach for Multi-objective Flexible Job Shop Scheduling Problems[J]. Computers & Industrial Engineering, 2005,48(2): 409-425.

[16]Murata T, Ishibuchi H, Gen M. Multi-objective Fuzzy Scheduling with the OWA Operator for Handling Different Scheduling Criteria and Different Job Importance[C]//IEEE International Fuzzy Systems Conference Proceedings. Seoul, 1999:773-778.

[17]Li J Q, Pan Q K, Gao K Z. Pareto-based Discrete Artificial Bee Colony Algorithm for Multi-objective Flexible Job-shop Scheduling Problems[J]. International Journal of Advanced Manufacturing Technology,2011,55: 1159-1169.

[18]Moslehi G, Mahnam M. A Pareto Approach to Multi-objective Flexible Job-shop Scheduling Problem Using Particle Swarm Optimization and Local Search[J]. International Journal of Production Economics, 2011,129(1): 14-22.

[19]Sakawa M, Kubota R. Fuzzy Programming for Multi-objective Job Shop Scheduling with Fuzzy Processing Time and Fuzzy due Date Through Genetic Algorithm[J].European Journal of Operational Research, 2000,120(2):393-407.

[20]刘炜琪,刘琼，张超勇，等. 基于混合粒子群算法求解多目标混流装配线排序[J].计算机集成制造系统, 2011, 17(12): 2590-2598.

Liu Weiqi, Liu Qiong, Zhang Chaoyong, et al. Hybrid Particle Swarm Optimization for Multy-objective Sequencing Problem in Mixed Model Assembly Lines[J]. Computer Integrated Manufacturing Systems, 2011, 17(12): 2590-2598.