考虑恶化效应的多目标非置换流水车间调度研究

doi:10.3969/j.issn.1007-7375.2022.02.016

摘要/Abstract

摘要： 实际生产过程中，机器经长时间运行后性能会有所降低，从而导致后续工件的加工时间延长。对此，本文研究一个考虑恶化效应的非置换流水车间调度问题。首先，建立一个以最大完工时间和总能耗为优化目标的混合整数线性规划模型。然后提出一种两阶段鲸鱼优化算法(two-stage whale optimization algorithm, TWOA)求解该模型。算法采用基于工件序列的编码方式，通过基于NEH启发式算法的初始化方法提高种群质量，设计一种基于“较优且最近”的引导个体和领导个体的两阶段搜索策略，同时，应用禁忌搜索机制提高局部搜索能力。最后通过仿真实验，验证算法的有效性。

关键词: 恶化效应, 非置换流水车间, 多目标优化, 鲸鱼优化算法

Abstract: The performance of the machine will be reduced after a long period of work, which will lead to longer processing time of the job. Hence, considering the deterioration effect caused by the machine, a non-permutation flow shop scheduling problem is studied. A mixed-integer linear programming model is firstly formulated to minimize maximum completion time and total energy consumption, and a two-stage whale optimization algorithm (TWOA) is proposed to solve this model. In the algorithm, the coding method based on the workpiece sequence is used and an initialization method based on the NEH heuristic is adopted to improve the quality of the population. The "better and nearest" individual is adopted and a two-stage global search is designed. At the same time, the tabu search mechanism is used to improve the local search ability. Finally, the simulation experiment is carried out to verify the effectiveness and superiority of proposed TWOA in solving the proposed problem.

Key words: deterioration effect, non-permutation flow-shop, multi-objective optimization, whale optimization algorithm

中图分类号:

TP391

钱伟康, 唐红涛. 考虑恶化效应的多目标非置换流水车间调度研究[J]. 工业工程, 2022, 25(2): 128-136.

QIAN Weikang, TANG Hongtao. A Research on Multi-objective Non-permutation Flow-shop Scheduling Considering Deterioration Effect[J]. Industrial Engineering Journal, 2022, 25(2): 128-136.

参考文献

[1] WU X, SHEN X, LI C. The flexible job-shop scheduling problem considering deterioration effect and energy consumption simultaneously[J]. Computers & Industrial Engineering, 2019, 135: 1004-1024
[2] LIU S, PEI J, CHENG H, et al. Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes[J/OL]. (2019-11). https://doi.org/10.1016/j.asoc.2019.105701.
[3] 黎阳, 李新宇, 牟健慧. 基于改进模拟退火算法的大规模置换流水车间调度[J]. 计算机集成制造系统, 2020, 26(2): 366-375
LI Yang, LI Xinyu, MOU Jianhui. Large-scale permutation flowshop scheduling method based on improved simulated annealing algorithm[J]. Computer Integrated Manufacturing Systems, 2020, 26(2): 366-375
[4] 刘翱, 冯骁毅, 邓旭东, 等. 求解零空闲置换流水车间调度问题的离散烟花算法[J]. 系统工程理论与实践, 2018, 38(11): 2874-2884
LIU Ao, FENG Xiaoyi, DENG Xudong, et al. A discrete fireworks algorithm for solving no-idle permutation flow shop problem[J]. Systems Engineering-TheoryPractice, 2018, 38(11): 2874-2884
[5] 郑永前, 李燕. 求解带缓冲区和机器可用性约束的非置换流水车间调度[J]. 东北大学学报(自然科学版), 2014, 35(9): 1329-1334, 1345
ZHENG Yongqian, LI Yan. Solution for non-permutation flow shop scheduling with buffers and machine availability constraints[J]. Journal of Northeastern University (Natural Science), 2014, 35(9): 1329-1334, 1345
[6] 肖鹏飞, 张超勇, 孟磊磊, 等. 基于深度强化学习的非置换流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(1): 192-205
XIAO Pengfei, ZHANG Chaoyong, MENG Leilei, et al. Non-permutation flow shop scheduling problem based on deep reinforcement learning[J]. Computer Integrated Manufacturing Systems, 2021, 27(1): 192-205
[7] MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67
[8] PETROVIC M, MILJKOVIC Z, JOKIC A. A novel methodology for optimal single mobile robot scheduling using whale optimization algorithm[J/OL]. (2019-08). https://doi.org/10.1016/j.asoc.2019.105520.
[9] SINGH P, PRAKASH S. Optical network unit placement in Fiber-Wireless (FiWi) access network by whale optimization algorithm[J/OL]. (2019-11). https://doi.org/10.1016/j.yofte.2019.101965.
[10] 闫旭, 叶春明, 姚远远. 量子鲸鱼优化算法求解作业车间调度问题[J]. 计算机应用研究, 2019, 36(4): 975-979
YAN Xu, YE Chunming, YAO Yuanyuan. Solving job-shop scheduling problem by quantum whale optimization algorithm[J]. Application Research of Computers, 2019, 36(4): 975-979
[11] 栾飞, 蔡宗琰, 吴书强, 等. 求解低碳车间调度问题的改进鲸鱼算法[J]. 机械科学与技术, 2020, 39(5): 721-728
LUAN Fei, CAI Zongyan, WU Shuqiang, et al. Improved whale optimization algorithm of scheduling problem for low carbon workshop[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(5): 721-728
[12] 陈辅斌, 李忠学, 杨喜娟. 基于改进NSGA2算法的多目标柔性作业车间调度[J]. 工业工程, 2018, 21(2): 55-61
CHEN Fubin, LI Zhongxue, YANG Xijuan. Multi-objective flexible job shop scheduling based on improved NSGA2 algorithm[J]. Industrial Engineering Journal, 2018, 21(2): 55-61
[13] 何桂霞. 特殊工艺约束下并行机多目标调度问题[J]. 工业工程, 2008, 11(6): 130-136
HE Guixia. Research on multi-objective scheduling problem subjected to special process constraint on parallel machines[J]. Industrial Engineering Journal, 2008, 11(6): 130-136
[14] GUPTA J N D, GUPTA S K. Single facility scheduling with nonlinear processing times[J]. Computers & Industrial Engineering, 1988, 14(4): 387-393
[15] YANG S, WANG J. Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration[J]. Applied Mathematics and Computation, 2011, 217(9): 4819-4826
[16] KUNNATHUR A S , GUPTA S K. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem[J]. European Journal of Operational Research, 1990, 47(1): 56-64
[17] SUNDARARAGHAVAN P S, KUNNATHUR A S. Single machine scheduling with start time dependent processing times: some solvable cases[J]. European Journal of Operational Research, 1994, 78(3): 394-403
[18] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9): 1917-1927
CUI Qi, WU Xiuli, YU Jianjun. Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2017, 23(9): 1917-1927
[19] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197
[20] LU C, GAO L, PAN Q, et al. A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution[J]. Applied Soft Computing, 2019, 75: 728-749
[21] 朱熠, 陈璐. 考虑准备时间的多目标混合流水车间调度[J]. 工业工程与管理, 2020, 25(4): 159-165
ZHU Yi, CHEN Lu. Multi-objective hybrid flow shop scheduling considering setup time[J]. Industrial Engineering and Management, 2020, 25(4): 159-165
[22] 李益兵, 黄炜星, 吴锐. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究[J]. 中国机械工程, 2020, 31(11): 1344-1350, 1385
LI Yibing, HUANG Weixing, WU Rui. Multi-objective green flexible job-shop scheduling problem based on improved artificial bee colony algorithm[J]. China Mechanical Engineering, 2020, 31(11): 1344-1350, 1385