混合工作日历下批量生产柔性作业车间多目标调度方法

doi:10.3969/j.issn.1007-7375.2021.06.002

摘要/Abstract

摘要： 提出了一种混合工作日历下批量生产柔性作业车间多目标调度方法。考虑设备的混合工作日历约束，构建了以生产周期最短、制造成本最低为优化目标的批量生产柔性作业车间多目标调度模型。设计了一种带精英策略的非支配排序遗传算法(NSGA II)求解该模型。算法中，采用“基于工序和设备的分段编码”方式分别对工序和设备进行编码；采用“基于工序和设备的分段交叉和变异方式”进行交叉和变异操作，采用“遗传算子改进策略”保证交叉、变异后子代个体的可行性；解码操作采用“基于平顺移动的原理”和“基于工作日历的时间推算技术”推算工序的调整开始、调整结束、加工开始和加工结束时刻。最后，通过案例分析验证了所提方法的有效性。

关键词: 批量生产柔性作业车间调度问题, 多目标优化, 混合工作日历, 平顺移动, NSGA II算法

Abstract: A multi-objective scheduling method for batch production flexible job shop scheduling problem (FJSP) under mixed work calendars was proposed. Considering the constraints of mixed work calendars of equipment, a multi-objective scheduling model for batch production FJSP with the objectives to minimize production cycle and manufacturing cost were designed. An elitist non-dominated sorting genetic algorithm (NSGA II) was designed to solve the researched model. A two-segment encoding method based on processes and equipment was used to respectively encode the processes and equipment. A two-segment crossover and mutation operator based on processes and equipment was used to implement crossover and mutation operation, in which an improved strategy of genetic operators was applied to ensure feasibility of the progeny individuals. In decoding operation, the principle based on parallel and sequence shift mode, and the time reckoning technology based on each equipment's calendar were used to calculate the begin and end time of each adjustment and process. Finally, effectiveness of the proposed method was validated by case study.

Key words: batch production flexible job shop scheduling problem, multi-objective optimization, mixed work calendars, parallel and sequence shift mode, NSGA II

中图分类号:

C93-03
TP391

曾强, 吴锦锦, 王培露, 李明金. 混合工作日历下批量生产柔性作业车间多目标调度方法[J]. 工业工程, 2021, 24(6): 8-17.

ZENG Qiang, WU Jinjin, WANG Peilu, LI Mingjin. A Multi-objective Scheduling Method for Batch Production FJSP under Mixed Work Calendars[J]. Industrial Engineering Journal, 2021, 24(6): 8-17.

参考文献

[1] GAO L, PAN Q K. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem[J]. Information Sciences, 2016, 372: 655-676
[2] AMIRGHASEMI M, ZAMANI R. An effective asexual genetic algorithm for solving the job shop scheduling problem[J]. Computers & Industrial Engineering, 2015, 83: 123-138
[3] KUNDAKCI N, KULAK O. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 96: 31-51
[4] 熊唯, 李宗斌, 郝建波. 解决动态作业车间调度关键问题的方法研究[J]. 组合机床与自动化加工技术, 2008(7): 105-108, 112
XIONG Wei, LI Zongbin, HAO Jianbo. Research on solving the key problem of dynamic job shop scheduling[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2008(7): 105-108, 112
[5] 武志军, 宁汝新, 万春辉. 车间调度中的动态工作日制研究与实现[J]. 制造业自动化, 2006, 28(4): 46-48, 75
WU Zhijun, NING Ruxin, WAN Chunhui. Research and realization of dynamic shop calendar in shop scheduling[J]. Manufacturing Automation, 2006, 28(4): 46-48, 75
[6] KRETER S, RIECK J, ZIMMERMANN J. Models and solution procedures for the resource-constrained project scheduling problem with general temporal constraints and calendars[J]. European Journal of Operational Research, 2016, 251(2): 387-403
[7] 黄瑜岳, 李克清, 郑晓峰. 考虑班次约束的Job Shop等量分批调度算法[J]. 科学技术与工程, 2013, 13(1): 1-7, 16
HUANG Yuyue, LI Keqing, ZHENG Xiaofeng. A scheduling algorithm to equal amount of batches for job shop considering the constraint of work-shifts[J]. Science Technology and Engineering, 2013, 13(1): 1-7, 16
[8] 曹礼园, 李深洛. 基于多目标最优化的最小代价决策树构建与实现[J]. 计算机与数字工程, 2019, 47(12): 3020-3024
CAO Liyuan, LI Shenluo. Construction and implementution of minimum cost decision tree based on multi-objective optimization[J]. Computer & Digital Engineering, 2019, 47(12): 3020-3024
[9] 张倩, 熊英, 何明珂, 等. 不确定需求生鲜电商配送路径规划多目标模型[J]. 系统仿真学报, 2019, 31(8): 1582-1590
ZHANG Qian, XIONG Ying, HE Mingke, et al. Multi-objective model of distribution route problem for fresh electricity commerce under uncertain demand[J]. Journal of System Simulation, 2019, 31(8): 1582-1590
[10] 刘隽楷, 邹晓松, 袁旭峰, 等. 含功效系数法的电力系统多目标综合优化[J]. 电测与仪表, 2018, 55(24): 59-63, 71
LIU Junkai, ZOU Xiaosong, YUAN Xufeng, et al. Multi-objective comprehensive of power system containing the efficacy coefficient method[J]. Electrical Measurement & Instrumentation, 2018, 55(24): 59-63, 71
[11] 宋立锋, 韦岗, 王群生. 以多目标优化的轮廓定位分割视频对象[J]. 电子与信息学报, 2002, 24(11): 1551-1558
SONG Lifeng, WEI Gang, WANG Qunsheng. Segment video objects by contour locating of multi-objective optimization[J]. Journal of Electronics & Information Technology, 2002, 24(11): 1551-1558
[12] GAO W, LUO Y, ZHU J, et al. Evolutionary algorithm with multiobjective optimization technique for solving nonlinear equation systems[J]. Information Sciences, 2020, 541: 345-361
[13] YUAN X, ZHANG B, WANG P, et al. Multi-objective optimal power flow based on improved strength Pareto evolutionary algorithm[J]. Energy, 2017, 122: 70-80
[14] LEE C, CHO D, JUNG H, et al. Niching genetic algorithm with restricted competition selection for multimodal function optimization[J]. IEEE Transactions on Magnetics, 1999, 35(3): 1722-1725
[15] BENTURKI M, DIZENE R, GHENAIET A. Multi-objective optimization of two-stage centrifugal pump using NSGA-II algorithm[J]. Journal of Applied Fluid Mechanics, 2018, 11(4): 929-943
[16] BEKKAR A, GUEMRI O, BEKRAR A, et al. An iterative greedy insertion technique for flexible job shop scheduling problem[J]. IFAC-Papers Online, 2016, 49(12): 1956-1961
[17] 吴秀丽, 孙树栋, 余建军, 等. 多目标柔性作业车间调度优化研究[J]. 计算机集成制造系统, 2006, 12(5): 731-736
WU Xiuli, SUN Shudong, YU Jianjun, et al. Research on multi-objective optimization for flexible job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2006, 12(5): 731-736
[18] 曾强, 常梦辉, 王孟华, 等. 混合工作日历下柔性作业车间多目标调度优化方法[J]. 重庆大学学报, 2019, 42(7): 10-26
ZENG Qiang, CHANG Menghui, WANG Menhua, et al. Multi-objective optimization method for FJSP under mixed work calendars[J]. Journal of Chongqing University, 2019, 42(7): 10-26
[19] 陈华平, 谷峰, 卢冰原, 等. 自适应多目标遗传算法在柔性工作车间调度中的应用[J]. 系统仿真学报, 2006, 18(8): 2271-2288
CHEN Huaping, GU Feng, LU Bingyuan, et al. Application of self-adaptive multi-objective genetic algorithm in flexible job shop scheduling[J]. Journal of System Simulation, 2006, 18(8): 2271-2288
[20] 曾强, 邓敬源, 常梦辉, 等. 混合工作日历下作业车间调度遗传进化方法[J]. 中国机械工程, 2018, 29(22): 2690-2720
ZENG Qiang, DENG Jingyuan, CHANG Menghui, et al. Genetic evolution method for JSP under mixed work calendars[J]. China Mechanical Engineering, 2018, 29(22): 2690-2720