运筹与管理2024，Vol.33Issue(8)：51-57,7.DOI:10.12005/orms.2024.0250
混合分布估计算法求解分布式柔性作业车间调度问题
Hybrid Estimation of Distribution Algorithm for Distributed Flexible Job Shop Scheduling
摘要
Abstract
In the context of economic globalization,many manufacturing enterprises are being guided by new manufacturing modes to establish distributed manufacturing units,aimed at cost savings and enhancing regional competitiveness.The scheduling decisions of manufacturing systems are transitioning from a centralized single-node model to a distributed multi-center approach.At the same time,small-batch,diverse,and personalized manufacturing services are promoting the development of flexible manufacturing units.The scheduling demands for distributed flexible manufacturing systems have garnered widespread attention.Therefore,this paper addres-ses the Distributed Flexible Job Shop Scheduling Problem(DFJSP),proposes a model that optimizes total cost and tardiness,and designs an H-EDA-TS algorithm combining estimation of distribution algorithm and Tabu search for solving the model. Considerations of cost and time disparities among different machines in heterogeneous factories are incorpo-rated into this study,which formulates a DFJSP model with the objective of minimizing total cost and total tardi-ness.Several constraints are integrated into the model to simulate practical manufacturing conditions:(1)Each job is allocated to a single factory.(2)Multiple jobs can be assigned to each factory.(3)Operations are uninter-rupted,where completion times are equal to start times plus durations.(4)The completion time of a job's final operation defines its departure time from the factory.(5)Machines can process only one job at any given time.(6)Each operation is exclusively performed by one machine at a time.(7)Operations adhere strictly to their designated routing sequences.(8)All operations for each job must be fully executed. Distributed flexible job shop scheduling problem is comprised of three sub-problems:allocating jobs to facto-ries,sequencing job processing within each factory,and selecting suitable machines for operations.This paper introduces a three-dimensional encoding scheme for the DFJSP model to represent the solutions.Each layer of the encoding corresponds to a sub-scheduling problem.Then,an H-EDA-TS algorithm is devised,which combines the global search advantages of estimation of distribution algorithm with the local search advantages of the Tabu search.The algorithm consists of an EDA component with three probabilistic models for population sampling and a TS component with five neighborhood structures designed to optimize objectives.Additionally,to conserve computational resources,an adaptive mechanism based on the sigmoid function regulates the initiation conditions and frequency of the TS component.Since this paper considers two optimization objectives,namely,minimizing total cost and total tardiness,the Pareto optimality principle and the crowding distance operator from NSGA-Ⅱ are employed for comparing and selecting solutions.Finally,experiments conducted on various scales of DFJSP instances demonstrate the significant advantages of the proposed H-EDA-TS algorithm over the estimation of distribution algorithm,Tabu search,and hybrid estimation of distribution algorithm and variable neighborhood search algorithms. With growing environmental awareness and governmental support for green manufacturing policies,manufac-turing enterprises are increasingly focusing on energy savings and emissions reduction during production processes.Carbon emissions can serve as an optimization target in scheduling decisions,aiming to achieve green production through the selection of low-energy-consumption scheduling schemes.Additionally,ensuring equitable workload distribution among manufacturing units is a noteworthy scheduling objective.Further investigation is warranted to refine scheduling optimization algorithms that holistically consider economics,time,environment and fairness.Furthermore,this paper addresses the static scheduling problem of distributed flexible job shops.However,as smart factories become prevalent,dynamic DFJSP research presents an intriguing avenue for future exploration.关键词
分布式柔性作业车间/分布估计算法/禁忌搜索/双目标优化Key words
distributed flexible job shop/estimation of distribution algorithm/Tabu search/bi-objective optimization分类
管理科学引用本文复制引用
魏光艳,叶春明..混合分布估计算法求解分布式柔性作业车间调度问题[J].运筹与管理,2024,33(8):51-57,7.基金项目
国家自然科学基金资助项目(71840003) （71840003）
上海理工大学科技发展基金资助项目(2018KJFZ043) （2018KJFZ043）
