A Pareto-Based Estimation of Distribution Algorithm for Solving Multiobjective Distributed No-Wait Flow-Shop Scheduling Problem With Sequence-Dependent Setup Time
A Pareto-Based Estimation of Distribution Algorithm for Solving Multiobjective Distributed No-Wait Flow-Shop Scheduling Problem With Sequence-Dependent Setup Time
复制标题
DOI：
10.1109/tase.2018.2886303
复制
发表时间：
2019-01
影响因子：
5.6
通讯作者：
W. Shao;D. Pi;Zhongshi Shao
中科院分区：
文献类型：
--
作者：
W. Shao;D. Pi;Zhongshi Shao
受经济全球化的影响，分布式制造已成为一种普遍的生产方式。本文研究了一类具有序列相关设置时间的多目标分布式无等待流车间调度问题（mndwfsp - sdst）。这种调度问题存在于许多实际生产中，如烘焙生产、并行计算机系统、手术调度等。性能标准是完工时间和总重量延迟。在mmdnwfsp - sdst中，考虑了多个相同工厂的无等待约束流车间调度问题。针对MDNWFSP-SDST问题，提出了一种基于pareto的分布估计算法（PEDA）。构建了空厂工作概率、同一厂两个工作概率和相邻工作概率三个概率模型。将PWQ启发式方法扩展到分布式环境中，生成初始个体。提出了一种基于参考模板的抽样方法来生成子代个体。提出了几种多目标邻域搜索方法来优化解的质量。比较结果表明，PEDA算法在寻址MDNWFSP-SDST问题上明显优于其他多目标优化算法。从业人员注意事项——本文的动机是多生产工厂（或生产线）的生产过程周期、手术调度和并行计算机系统。在这些过程周期中，作业被分配到多个生产工厂（或生产线），并且连续操作之间不存在中断。本文将此过程建模为具有SDST的多目标分布式无等待流车间调度。当面对分布式工厂时，调度变得更具挑战性。本文提出了一种基于Pareto支配概念的分布式估计算法，该算法使用概率模型来产生子代。实验结果表明，该算法可以在大规模实例中找到较优解。通过考虑其他约束，如装配过程、混合无等待和运输时间，可以将该调度模型扩展到实际问题。此外，该算法还可以应用于解决其他分布式调度问题和工业案例，只要它们的约束条件已知，即操作的处理时间、机器的设置时间。
Influenced by the economic globalization, the distributed manufacturing has been a common production mode. This paper considers a multiobjective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time (MDNWFSP-SDST). This scheduling problem exists in many real productions such as baker production, parallel computer system, and surgery scheduling. The performance criteria are the makespan and the total weight tardiness. In the MDNWFSP-SDST, several identical factories are considered with the related flow-shop scheduling problem with no-wait constraints. For solving the MDNWFSP-SDST, a Pareto-based estimation of distribution algorithm (PEDA) is presented. Three probabilistic models including the probability of jobs in empty factory, two jobs in the same factory, and the adjacent jobs are constructed. The PWQ heuristic is extended to the distributed environment to generate initial individuals. A sampling method with the referenced template is presented to generate offspring individuals. Several multiobjective neighborhood search methods are developed to optimize the quality of solutions. The comparison results show that the PEDA obviously outperforms other considered multiobjective optimization algorithms for addressing MDNWFSP-SDST. Note to Practitioners—This paper is motivated by the process cycles in multiproduction factories (or lines) of baker production, surgery scheduling, and parallel computer systems. In these process cycles, jobs are assigned to multiproduction factories (or lines), and no interruption exists between consecutive operations. This paper models this process as a multiobjective distributed no-wait flow-shop scheduling with SDST. Scheduling becomes more challenging when facing distributed factories. This paper provides an estimation of distributed algorithm with Pareto dominate concept which uses a probabilistic model to generate offspring. Experiment results suggest that the proposed algorithm can find superior solutions of large-scale instances. This scheduling model can be extended to practical problems by considering other constraints, such as assembly process, mixed no-wait, and transporting times. Besides, the proposed algorithm can be applied to solve other distributed scheduling problems and industrial cases, once their constraints are known, i.e., the processing time of operations, the setup time of machines.