考虑加班的无拖期作业车间调度问题多目标金鹰优化算法研究

doi:10.3969/j.issn.1004-132X.2023.17.007

摘要/Abstract

摘要： 按期交货是面向订单型制造企业生产运作所追求的重要目标之一。当制造系统生产负荷较重时，加班作业是保证交货期最常采用的有效措施。为实现订单的无拖期交付和加班时间的合理优化使用，以面向订单型制造系统为背景，提出了一种考虑加班的多目标无拖期作业车间调度问题，建立了以最小化总加班时间和最大完工时间为目标的数学规划模型。为有效求解该问题，提出了一种多目标金鹰优化算法。在算法中设计了连续解空间映射至问题离散解空间的编码方法；提出了两阶段解码方案；融入了基于精英保留策略的非支配排序选择算子；引入了自适应子代个体生成策略。以23个作业车间调度问题基准算例为实验对象进行了对比实验，实验结果验证了所提出算法的有效性和优越性。

关键词: 作业车间调度, 无拖期, 加班作业, 多目标金鹰优化算法

Abstract: Delivery on time was one of the important goals of the production operations in make-to-order industries. When the production load of the manufacturing system was heavy， overtime work was the most commonly used effective measure to ensure the delivery time. In order to realize the no-tardiness delivery of order tasks and the optimal use of overtime hours， a multi-objective no-tardiness job shop scheduling problem considering overtime was proposed， and a mathematical model with the objective of minimizing the total overtime hours and the makespan was established. To solve the problem effectively， a multi-objective golden eagle optimizer was proposed. In the algorithm， a coding method was designed to map the continuous solution space to the discrete solution space of the problem， a two-stage decoding scheme was proposed， an elitist no-dominated sorting selection operator was integrated， and an adaptive offspring individual generation strategy was introduced. The effectiveness and superiority of the proposed algorithm were verified by comparison experiments on 23 modified job shop scheduling problem benchmarks as experimental objects.

Key words: job shop scheduling, no-tardiness, overtime, multi-objective golden eagle optimizer

中图分类号:

TP18

史双元, 熊禾根. 考虑加班的无拖期作业车间调度问题多目标金鹰优化算法研究[J]. 中国机械工程, 2023, 34(17): 2077-2088.

SHI Shuangyuan, XIONG Hegen. Research on Multi-objective Golden Eagle Optimizer for No-tardiness Job Shop Scheduling Problems with Overtime Consideration[J]. China Mechanical Engineering, 2023, 34(17): 2077-2088.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.cmemo.org.cn/CN/10.3969/j.issn.1004-132X.2023.17.007

http://www.cmemo.org.cn/CN/Y2023/V34/I17/2077

参考文献

［1］吴秀丽，刘夏晶. 差分进化算法求解分布式柔性作业车间调度问题［J］. 计算机集成制造系统， 2019， 25（10）：2539-2558.
WU Xiuli， LIU Xiajing. Differential Evolution Algorithm for Solving Distributed Flexible Job Shop Scheduling Problem［J］. Computer Integrated Manufacturing System， 2019， 25（10）：2539-2558.
［2］HE L J， LI W F， CHIONG R， et al. Optimizing the Job-shop Scheduling Problem Using a Multi-objective Jaya Algorithm［J］. Applied Soft Computing， 2021， 111：107654.
［3］戴敏，王辉. 基于遗传退火算法的绿色作业车间调度［J］. 现代制造工程， 2021（5）：26-31.
DAI Min， WANG Hui. Green Job Shop Scheduling Based on Genetic Annealing Algorithm［J］. Modern Manufacturing Engineering， 2021（5）：26-31.
［4］YAZDANI M， ALETI A， KHALITI S， et al. Optimizing the Sum of Maximum Earliness and Tardiness of the Job Shop Scheduling Problem［J］. Computers & Industrial Engineering， 2017， 107：12-24.
［5］王秋莲，段星皓. 基于高维多目标候鸟优化算法的柔性作业车间调度［J］. 中国机械工程， 2022， 33（21）：2601-2612.
WANG Qiulian， DUAN Xinghao. Scheduling of Flexible Job Shop Based on High-dimension and Multi-objective Migrating Bird Optimization Algorithm［J］. China Mechanical Engineering， 2022， 33（21）：2601-2612.
［6］CHAND S， SCHNEEBERGER H. Single Machine Scheduling to Minimize Weighted Earliness Subject to No Tardy Jobs［J］. European Journal of Operational Research， 1988， 34（2）：221-230.
［7］ZHAO C L， TANG H Y. Single Machine Scheduling Problems with Deteriorating Jobs［J］. Applied Mathematics and Computation， 2005， 161（3）：865-874.
［8］SOROUSH H. On the Scheduling with Past-sequence-dependent Setup Times and Learning Effects on a Single Machine［J］. International Journal of Advanced Manufacturing Technology， 2013， 68：2483-2487.
［9］HOLLOWAY C， NELSON R. Job Shop Scheduling with Due Dates and Overtime Capability［J］. Institute for Operations Research and the Management Science， 1974， 21（1）：68-78.
［10］陈淑玲，李铁克，王柏琳. 考虑加班因素的订单接受问题优化模型与算法［J］. 工业工程， 2015， 18（2）：1-8.
CHEN Shuling， LI Tieke， WANG Bailin. An Optimization Model and Algorithms for Order Acceptance Problem with Overtime Strategy［J］. Industrial Engineering Journal， 2015， 18（2）：1-8.
［11］ZHANG J， YANG W S， TU Y L. Scheduling with Compressible and Stochastic Release Dates［J］. Computers & Operations Research， 2013， 40（7）：1758-1765.
［12］YODA M， EGUCHI T， MURAYAMA T. Job Shop Scheduling for Meeting Due Dates and Minimizing Overtime Using Genetic Algorithm Incorporating New Priority Rules［J］. Journal of Advanced Mechanical Design Systems & Manufacturing， 2014， 8（5）：1-10.
［13］MOHAMMADI-BALANI A， NAYERI M， AZAR A， et al. Golden Eagle Optimizer：a Nature-inspired Metaheuristic Algorithm［J］. Computers & Industrial Engineering， 2020， 152：107050.
［14］LYU J X， YAN L J， CHU S C， et al. A New Hybrid Algorithm Based on Golden Eagle Optimizer and Grey Wolf Optimizer for 3D Path Planning of Multiple UAVs in Power Inspection［J］. Neural Computing and Applications， 2022， 34：11911-11936.
［15］ZRKANDI S. Dynamic Modeling and Power Optimization of a 4RPSP+PS Parallel Flight Simulator Machine［J］. Robotica， 2022， 40：646-671.
［16］ABDEL-BASSET M， MOHAMED R， ELKMOY O， et al. Recent Metaheuristic Algorithms with Genetic Operators for High-dimensional Knapsack Instances：a Comparative Study［J］. Computers and Industrial Engineering， 2022， 166：107974.
［17］ELURI R， DEVARAKONDA N. Binary Golden Eagle Optimizer with Time-varying Flight Length for Feature Selection［J］. Knowledge-Based Systems， 2022， 247：108771.
［18］XU W X， HU Y W， LUO W， et al. A Multi-objective Scheduling Method for Distributed and Flexible Job Shop Based on Hybrid Genetic Algorithm and Tabu Search Considering Operation Outsourcing and Carbon Emission［J］. Computers & Industrial Engineering， 2021， 157：107318.
［19］JANGIR P， HEIDARI A， CHEN H L. Elitist Non-dominated Sorting Harris Hawks Optimization：Framework and Developments for Multi-objective Problems［J］. Expert Systems with Application， 2021， 186：115747.
［20］ZHANG C Y， RAO Y Q， LI P G. An Effective Hybrid Genetic Algorithm for the Job Shop Scheduling Problem［J］. International Journal of Advanced Manufacturing Technology， 2008， 39：965-974.
［21］WEN X Y， WANG K H， LI H， et al. A Two-stage Solution Method Based on NSGA-Ⅱ for Green Multi-objective Integrated Process Planning and Scheduling in a Battery Packaging Machinery Workshop［J］. Swarm and Evolutionary Computation， 2021， 61（10）：100820.
［22］ZHANG Q F， LI H. MOEA/D：a Multi-objective Evolutionary Algorithm Based on Decomposition［J］. IEEE Transactions on Evolutionary Computation， 2008， 11（6）：712-731.
［23］ZHAO F Q， ZHEN C， WANG J B， et al. An Improved MOEA/D for Multi-objective Job Shop Scheduling Problem［J］. International Journal of Computer Integrated Manufacturing， 2016， 30（6）：616-640.
［24］姜一啸，吉卫喜，何鑫，等. 基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度［J］. 中国机械工程， 2022， 33（21）：2564-2577.
JIANG Yixiao， JI Weixi， HE Xin， et al. Low-carbon Scheduling of Multi-objective Flexible Job-shop Based on Improved NSGA-Ⅱ［J］. China Mechanical Engineering， 2022， 33（21）：2564-2577.
［25］SUKKERD W， WUTTIPORNPUN T. Hybrid Genetic Algorithm and Tabu Search for Finite Capacity Material Requirement Planning System in Flexible Flow Shop with Assembly Operations［J］. Computers & Industrial Engineering， 2016， 97：157-169.

[1]	魏书鹏, 唐红涛, 李西兴, 杨冠宇, 张健. 考虑双资源约束的柔性机械加工车间逆调度问题研究[J]. 中国机械工程, 2024, 35(03): 457-471.
[2]	魏光艳, 叶春明. 分布式多柔性装配作业车间调度问题研究[J]. 中国机械工程, 2023, 34(20): 2442-2455.
[3]	张维存, 顾洪羽. 一人多机模式下考虑相似学习效应的车间调度问题[J]. 中国机械工程, 2023, 34(14): 1701-1709.
[4]	孙爱红, 宋豫川, 杨云帆, 雷琦. 考虑关键件加工质量的双资源约束车间调度算法[J]. 中国机械工程, 2022, 33(21): 2590-2600.
[5]	李西兴, 杨道明, 李鑫, 吴锐, . 基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法[J]. 中国机械工程, 2021, 32(08): 938-950，986.
[6]	李益兵1,2;黄炜星1;吴锐1. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究[J]. 中国机械工程, 2020, 31(11): 1344-1350,1385.
[7]	曾强, 邓敬源, 常梦辉, 张进春. [车间调度]混合工作日历下作业车间调度遗传进化方法[J]. 中国机械工程, 2018, 29(22): 2690-2702.
[8]	杨宇;黄敏;王震宇;朱启兵. 利用有限制稳定配对策略求解双目标柔性作业车间调度问题[J]. 中国机械工程, 2018, 29(14): 1743-1750.
[9]	朱传军 , 宋文家, 张超勇, 曹静 , 朱孟周. 基于维修时间窗的柔性作业车间调度优化研究[J]. 中国机械工程, 2016, 27(10): 1337-1343.
[10]	赵敏, 殷欢, 孙棣华, 郑林江, 何伟, 袁川. 基于改进人工鱼群算法的柔性作业车间调度[J]. 中国机械工程, 2016, 27(08): 1059-1065.
[11]	彭建刚, 刘明周, 张玺, 张铭鑫, 葛茂根. 基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题[J]. 中国机械工程, 2015, 26(5): 620-626.
[12]	杨宏安, 席志成, 夏常凯, 王经国. Job Shop调度问题的Minimax模型及双空间协同遗传算法[J]. 中国机械工程, 2015, 26(3): 330-338.
[13]	巴黎, 李言, 曹源, 杨明顺, 刘永. 考虑批量装配的柔性作业车间调度问题研究[J]. 中国机械工程, 2015, 26(23): 3200-3207.
[14]	刘琼, 田有全, John W. Sutherland, 周迎冬. 产品制造过程碳足迹核算及其优化问题[J]. 中国机械工程, 2015, 26(17): 2336-2343.
[15]	宋文家, 张超勇, 尹勇, 邵新宇. 基于多目标混合殖民竞争算法的设备维护与车间调度集成优化[J]. 中国机械工程, 2015, 26(11): 1478-1487.