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 addresses 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 incorporated into this study, which formulates a DFJSP model with the objective of minimizing total cost and total tardiness. 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 uninterrupted, 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 factories, 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-II 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, manufacturing 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

摘要： 随着分布式柔性制造系统的广泛普及,制造系统的调度决策从集中式的单一节点向分布式多中心的模式转变,分布式柔性作业车间调度问题成为近年来的研究热点。为求解分布式柔性作业车间的调度问题,构建了以最小化总成本和总拖期为优化目标的分布式柔性作业车间调度(DFJSP,Distributed Flexible Job Shop Scheduling Problem)模型,提出了一种结合分布估计和禁忌搜索的H-EDA-TS算法(Hybrid Estimation of Distribution Algorithm and Tabu Search Algorithm)。根据DFJSP模型和H-EDA-TS算法设计了三维编码方案。H-EDA-TS算法主要包括EDA组件和TS组件,在EDA组件部分设计了三个概率模型用于抽样生成种群;在TS组件部分针对优化目标设计了五种邻域结构用于生成邻域解。此外,基于sigmoid函数设计了一种自适应机制,用于控制TS组件的启动。最后,在不同规模的实例上进行了对比实验,证明了所提算法对于求解DFJSP具有明显优势。

关键词: 分布式柔性作业车间, 分布估计算法, 禁忌搜索, 双目标优化