分布式多柔性装配作业车间调度问题研究

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

摘要/Abstract

摘要： 针对分布式柔性装配作业车间环境，综合考虑了调度过程中的机器选择柔性、工人安排柔性和工序顺序柔性，构建了以最小化最大完工时间和最小化总能耗为优化目标的分布式多柔性装配作业车间调度问题（DMFAJSP）的数学模型。为求解DMFAJSP模型，提出了一种以分布估计算法为全局搜索组件、以邻域搜索算子为局部搜索组件的多维模因算法（MDMA）。最后，将所提出的算法与其他算法进行了对比试验，结果表明MDMA算法在求解DMFAJSP模型方面具有显著优势。

关键词: 分布式多柔性装配作业车间调度问题, 工序顺序柔性, 多维模因算法, 分布估计算法, 绿色调度

Abstract: Aiming at distributed flexible assembly job-shop environments, the machine selection flexibility, worker scheduling flexibility, and process sequence flexibility in scheduling were comprehensively considered, and a model of DMFAJSP was constructed taking minimizing the makespan and minimizing the total energy consumption as optimization objectives. To solve the DMFAJSP model, MDMA was proposed using estimation of distribution algorithm as the global search component and the neighborhood search operators as the local search component. Finally, comparative experiments were conducted between the proposed algorithm and other algorithms, and the results show that the MDMA has significant advantages in solving DMFAJSP model.

Key words: distributed and multi-flexible assembly job-shop scheduling problem（DMFAJSP）, process sequence flexibility, multi-dimensional memetic algorithm(MDMA), estimation of distribution algorithm, green scheduling

中图分类号:

TP18

魏光艳, 叶春明. 分布式多柔性装配作业车间调度问题研究[J]. 中国机械工程, 2023, 34(20): 2442-2455.

WEI Guangyan, YE Chunming. Research on Distributed and Multi-flexible Assembly Job-shop Scheduling Problems[J]. China Mechanical Engineering, 2023, 34(20): 2442-2455.

参考文献

［1］李政阳, 云昕, 杨怡欣, 等. 在轨空间智能制造:分布式调度建模与优化［J］. 系统工程理论与实践, 2019,39(3):705-724.
LI Zhengyang, YUN Xin, YANG Yixin, et al. In-space Intelligent Manufacturing:Distributed Scheduling and Optimization［J］. Systems Engineering-Theory & Practice， 2019, 39(3):705-724.
［2］王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综述［J］. 控制与决策, 2016,31(1):1-11.
WANG Ling, DENG Jin,WANG Shengyao. Survey on Optimization Algorithms for Distributed Shop Scheduling［J］. Control and Decision, 2016,31(1):1-11.
［3］CHAOUCH I, DRISS O B, GHEDIRA K. A Novel Dynamic Assignment Rule for the Distributed Job Shop Scheduling Problem Using a Hybrid Ant-based Algorithm［J］. Applied intelligence, 2018,49(5):1903-1924.
［4］JIANG E, WANG L, PENG Z. Solving Energy-efficient Distributed Job Shop Scheduling via Multi-objective Evolutionary Algorithm with Decomposition［J］. Swarm and Evolutionary Computation, 2020,58:100745.
［5］瘙塁AHMAN M A. A Discrete Spotted Hyena Optimizer for Solving Distributed Job Shop Scheduling Problems［J］. Applied Soft Computing, 2021,106:107349.
［6］MENG L, ZHANG C, REN Y, et al. Mixed-integer Linear Programming and Constraint Programming Formulations for Solving Distributed Flexible Job Shop Scheduling Problem［J］. Computers & Industrial Engineering, 2020,142:106347.
［7］吴秀丽, 刘夏晶. 差分进化算法求解分布式柔性作业车间调度问题［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 Systems, 2019,25(10):2539-2558.
［8］LI J, DUAN P, CAO J, et al. A Hybrid Pareto-based Tabu Search for the Distributed Flexible Job Shop Scheduling Problem with E/T Criteria［J］. IEEE Access, 2018,6:58883-58897.
［9］王凌, 王晶晶. 考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化［J］. 中国科学:技术科学, 2023,53(2):243-257.
WANG Ling, WANG Jingjing. A Cooperative Memetic Algorithm for the Distributed Green Flexible Job Shop with Transportation Time［J］. Scientia Sinica(Technologica), 2023,53(2):243-257.
［10］DU Y, LI J, LUO C, et al. A Hybrid Estimation of Distribution Algorithm for Distributed Flexible Job Shop Scheduling with Crane Transportations［J］. Swarm and Evolutionary Computation, 2021,62:100861.
［11］张洪亮, 徐公杰, 鲍蔷, 等. 考虑运输时间的分布式柔性作业车间绿色调度［J］. 中国机械工程, 2021,33(21):2554-2563.
ZHANG Hongliang, XU Gongjie, BAO Qiang, et al. Distributed Flexible Job Shop Green Scheduling with Transportation Time［J］. China Mechanical Engineering, 2021,33(21):2554-2563.
［12］XU W, HU Y, 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.
［13］LUO Q, DENG Q, GONG G, et al. An Efficient Memetic Algorithm for Distributed Flexible Job Shop Scheduling Problem with Transfers［J］. Expert Systems with Applications, 2020,160:113721.
［14］郭晨, 曾思豪, 郭钧, 等. 混合分布估计算法求解模糊分布式装配柔性车间调度问题［J］. 系统工程理论与实践, 2021,41(04):1037-1048.
GUO Chen, ZENG Sihao, GUO Jun, et al. Hybrid Estimation of Distribution Algorithm for Distributed Assembly Flexible Job Shop Scheduling Problem with Fuzzy Processing Time［J］. Systems Engineering-Theory & Practice, 2021, 41(4):1037-1048.
［15］TANG H, FANG B, LIU R, et al. A Hybrid Teaching and Learning-based Optimization Algorithm for Distributed Sand Casting Job-shop Schedu-ling Problem［J］. Applied Soft Computing, 2022,120:108694.
［16］SANG Y, TAN J. Intelligent Factory Many-objective Distributed Flexible Job Shop Collaborative Scheduling Method［J］. Computers & industrial Engineering, 2022,164:107884.
［17］桂林, 张春江, 李新宇. 具有工序顺序柔性的车间调度问题研究综述［J］. 工业工程, 2020,23(2):116-123.
GUI Lin, ZHANG Chunjiang, LI Xinyu. A Review of Research on Shop Scheduling Problem with Flexible Process Sequence［J］. Industrial Engineering Journal, 2020,23(2):116-123.
［18］高亮, 李新宇. 工艺规划与车间调度集成研究现状及进展［J］. 中国机械工程, 2011,22(8):1001-1007.
GAO Liang, LI Xinyu. Current Researches on Integrated Process Planning and Scheduling［J］. China Mechanical Engineering, 2011, 22(8):1001-1007.
［19］黄学文, 孙娜, 孙榕, 等. 工序顺序柔性描述模型研究［J］. 计算机集成制造系统, 2016,22(10):2275-2283.
HUANG Xuewen, SUN Na, SUN Rong, et al. Operation Sequence Flexibility Description Model［J］. Computer Integrated Manufacturing Systems,2016,22(10):2275-2283.
［20］钟宏扬, 刘建军, 韩省, 等. 集成零件外协与共享决策的柔性装配作业车间调度研究［J/OL］. 计算机集成制造系统:1-27.［2023-05-25］.http:∥kns.cnki.net/kcms/detail/11.5946.TP.20220823.1541.017.html.
ZHONG Hongyang, LIU Jianjun, HAN Xing, et al. Integrating Part Outsourcing and Sharing Decision in Flexible Assembly Job Shop Scheduling［J/OL］. Computer Integrated Manufacturing Systems:1-27.［2023-05-25］.http:∥kns.cnki.net/kcms/detail/11.5946.TP.20220823.1541.017.html.
［21］胡瑞淇, 程辉, 张执南. 基于表达式树的顺序柔性车间调度问题求解［J/OL］. 计算机集成制造系统:1-15［2023-05-25］. http:∥kns.cnki.net/kcms/detail/11.5946.tp.20220317.1506.002.html.
HU Ruiqi, CHENG Hui, ZHANG Zhinan. Solving Job Shop Scheduling Problem with Flexible Process Sequence Based on Expression Tree Model［J/OL］. Computer Integrated Manufacturing Systems:1-15［2023-05-25］.http:∥kns.cnki.net/kcms/detail/11.5946.tp.20220317.1506.002.html.
［22］ZHANG S, LI X, ZHANG B, et al. Multi-objective Optimisation in Flexible Assembly Job Shop Scheduling Using a Distributed Ant Colony System［J］. European Journal of Operational Research, 2020,283(2):441-460.
［23］董海, 徐晓鹏. 离散回溯搜索算法求解多柔性作业车间调度［J］. 运筹与管理, 2022,31(1):87-91.
DONG Hai, XU Xiaopeng. Solving Multi-flexible Job-shop Scheduling Problem by Discrete Backtracking Search Algorithm［J］. Operations Research and Management Science, 2022,31(1):87-91.
［24］VITAL-SOTO A, BAKI M F, AZAB A. A Multi-objective Mathematical Model and Evolutionary Algorithm for the Dual-resource Flexible Job-shop Scheduling Problem with Sequencing Flexibility［J/OL］. Flexible Services and Manufacturing Journal:1-43.［2023-05-25］.https:∥doi.org/10.1007/s10696-022-09446-x.
［25］GONG G, CHIONG R, DENG Q, et al. A Memetic Algorithm for Multi-objective Distributed Production Scheduling:Minimizing the Makespan and Total Energy Consumption［J］. Journal of Intelligent Manufacturing, 2020,31(6):1443-1466.
［26］李瑞, 王凌, 龚文引. 知识驱动的模因算法求解分布式绿色柔性调度［J］. 华中科技大学学报(自然科学版), 2022,50(6):55-60.
LI Rui, WANG Ling, GONG Wenyin. Knowledge-driven Memetic Algorithm for Distributed Green Flexible Job Shop Scheduling Problem［J］. Journal of Huazhong University of Science & Technology(Natural Science Edition), 2022,50(6):55-60.
［27］王圣尧, 王凌, 方晨, 等. 分布估计算法研究进展［J］. 控制与决策, 2012,27(7):961-966.
WANG Shengyao, WANG Ling, FANG Chen, et al. Advances in Estimation of Distribution Algorithms［J］. Control &Decision, 2012,27(7):961-966.
［28］张梓琪, 钱斌, 胡蓉, 等. 基于多维EDA算法的低碳分布式装配流水车间调度［J］. 控制与决策, 2022,37(5):1367-1377.
ZHANG Ziqi, QIAN Bin, HU Rong, et al. Multidimensional Estimation of Distribution Algorithm for Low Carbon Scheduling of Distributed Assembly Permutation Flow-shop［J］. Control & Decision, 2022, 37(5):1367-1377.
［29］王洪峰, 王娜, 汪定伟. 一种求解动态多峰优化问题的Memetic粒子群算法［J］. 系统工程理论与实践, 2013,33(6):1577-1586.
WANG Hongfeng, WANG Na, WANG Dingwei. A Memetic Particle Swarm Algorithm for Dynamic Multi-modal Optimization Problems［J］. Systems Engineering—Theory & Practice, 2013, 33(6):1577-1586.
［30］黄学文, 陈绍芬, 周阗玉, 等. 求解柔性作业车间调度问题的一种新邻域结构［J］. 系统工程理论与实践, 2021,41(9):2367-2378.
HUANG Xuewen, CHEN Shaofen, ZHOU Tianyu, et al. A New Neighborhood Structure for Solving the Flexible Job-shop Scheduling Problem［J］. Systems Engineering—Theory & Practice. 2021, 41(9):2367-2378.
［31］BALAS E. Machine Sequencing via Disjunctive Graphs:an Implicit Enumeration Algorithm［J］. Operations Research, 1969,17(6):941-957.
［32］DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ［J］. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197.
［33］BRANDIMARTE P. Routing and Scheduling in a Flexible Job Shop by Tabu Search［J］. Annals of Operations Research, 1993,41(3):157-183.
［34］LIN W, GOW H, TSAI M. An Efficient Hybrid Taguchi-immune Algorithm for the Unit Commitment Problem［J］. Expert Systems with Applications, 2011,38(11):13662-13669.

[1]	李西兴, 周文龙, 唐红涛, 吴锐, . 考虑设备预维护的特种车辆白车身试制车间绿色调度优化方法[J]. 中国机械工程, 2023, 34(15): 1832-1847.
[2]	耿凯峰1,2;叶春明1;吴绍兴2;刘丽2. 分时电价下多目标绿色可重入混合流水车间调度[J]. 中国机械工程, 2020, 31(12): 1469-1480.
[3]	钟祾充, 钱斌, 胡蓉, 王凌. [车间调度]混合布谷鸟算法求解绿色流水车间调度问题[J]. 中国机械工程, 2018, 29(22): 2674-2681.
[4]	裴小兵;赵衡. 基于二元分布估计算法的置换流水车间调度方法[J]. 中国机械工程, 2017, 28(22): 2752-2759.
[5]	谢书童, 郭隐彪. 边缘分布估计算法在车削参数优化中的应用 [J]. 中国机械工程, 2010, 21(1): 22-26.