• ISSN 1006-3080
• CN 31-1691/TQ
 引用本文:
 Citation:

• 中图分类号: TB497

## Mixed No-idle Permutation Flow Shop Scheduling Problem Based on Multi-objective Discrete Sine Optimization Algorithm

###### Corresponding author: GU Xingsheng, xsgu@ecust.edu.cn
• CLC number: TB497

• 摘要: 针对以最小化最大完工时间（makespan）和最小化最大拖期（maximum tardiness）为目标的多目标混合零空闲置换流水车间调度问题（Mixed No-idle Permutation Flow Shop Scheduling Problem, MNPFSP），提出了一种多目标离散正弦优化算法（Multi-objective Discrete Sine Optimization Algorithm, MDSOA）。首先，建立外部档案集（AS）存储Pareto解，并在每次迭代后对AS进行更新；其次，在正弦优化算法（Sine Optimization Algorithm，SOA）的基础上，引入迭代贪婪（IG）算法的破坏重构机制，重新定义了一种适用于离散调度问题的位置更新策略；最后，引入快速非支配排序和拥挤距离对种群进行筛选，在保留精英解的同时保证了解的多样性和分布性。选取Taillard Benchmark中11个不同规模的算例进行仿真实验，并将仿真结果与NSGA-II和NSGA-III算法进行比较，验证了MDSOA求解MNPFSP的有效性。
• 图 1  基于FNDS和拥挤距离的选择策略

Figure 1.  Selection strategy based on fast non-dominated sorting and crowding distance

图 2  MDSOA算法流程图

Figure 2.  Flowchart of the MDSOA

图 3  MDSOA、NSGA-II和NSGA-III获得的Pareto前沿

Figure 3.  Pareto front obtained by MDSOA, NSGA-II and NSGA-III algorithms

•  [1] 刘翱, 冯骁毅, 邓旭东, 等. 求解零空闲置换流水车间调度问题的离散烟花算法[J]. 系统工程理论与实践, 2018, 38(11): 2874-2884. [2] PAN Q K, WANG L. No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm[J]. International Journal of Advanced Manufacturing Technology, 2008, 39(7/8): 796-807. [3] PAN Q K, RUIZ R. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem[J]. Omega, 2014, 44(2): 41-50. [4] 张晓霞, 吕云虹. 一种求解混合零空闲置换流水车间调度禁忌分布估计算法[J]. 计算机应用与软件, 2017, 34(1): 270-274, 292. [5] CHENG C Y, YING K C, CHEN H H, et al. Minimising makespan in distributed mixed no-idle flowshops[J]. International Journal of Production Research, 2019, 57(1): 48-60. doi: 10.1080/00207543.2018.1457812 [6] ROSSI F L, NAGANO M S. Heuristics for the mixed no-idle flowshop with sequence-dependent setup times and total flowtime criterion[J]. Expert Systems with Applications, 2019, 125(1): 40-54. [7] SANTOSA B, SISWANTO N. Discrete particle swarm optimization to solve multi-objective limited-wait hybrid flow shop scheduling problem[J]. IOP Conference Series: Materials Science and Engineering, 2018, 337(1): 012006. [8] PAN Q K, WANG L, QIAN B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers & Operations Research, 2009, 36(8): 2498-2511. [9] LEI D M, ZHENG Y L. Hybrid flow shop scheduling with assembly operations and key objectives: A novel neighborhood search[J]. Applied Soft Computing, 2017, 61: 122-128. doi: 10.1016/j.asoc.2017.07.058 [10] MURILO Z, APARECIDO C A, JOSU C. A decomposition-based kernel of Mallows models algorithm for bi- and tri-objective permutationflowshop scheduling problem[J]. Applied Soft Computing Journal, 2018, 71: 526-537. doi: 10.1016/j.asoc.2018.07.011 [11] MESHKAT M, PARHIZGAR M. Sine optimization algorithm (SOA): A novel optimization algorithm by change update position strategy of search agent in sine cosine algorithm[C]//2017 3rd Iranian Conference on Intelligent Systems and Signal Processing (ICSPIS)[C]. Shahrood, Iran: IEEE, 2017: 11-16. [12] MIRJALILI S. SCA: A Sine Cosine Algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133. doi: 10.1016/j.knosys.2015.12.022 [13] FERNANDEZ-VIAGAS V, FRAMINAN J M. A beam-search-based constructive heuristic for the PFSP to minimise total flowtime[J]. Computers and Operations Research, 2017, 81: 167-177. doi: 10.1016/j.cor.2016.12.020 [14] JOLAI F, ASEFI H, RABIEE M, et al. Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem[J]. Scientia Iranica, 2013, 20(3): 861-872. [15] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017 [16] MIRJALILI S, LEWIS A. Novel performance metrics for robust multi-objective optimization algorithms[J]. Swarm and Evolutionary Computation, 2015, 21: 1-23. doi: 10.1016/j.swevo.2014.10.005 [17] DEB K, AGARWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]//International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2000: 849-858. [18] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285. doi: 10.1016/0377-2217(93)90182-M [19] MINELLA G, RUIZ R, CIAVOTTA M. Restarted iterated Pareto greedy algorithm for multi-objective flowshop scheduling problems[J]. Computers & Operations Research, 2011, 38(11): 1521-1533. [20] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach: Part I. Solving problems with box constraints[J]. IEEE transactions on evolutionary computation, 2014, 18(4): 577-601. doi: 10.1109/TEVC.2013.2281535 [21] RIQUELME N, LÜCKEN C V, BARAN B. Performance metrics in multi-objective optimization[C]//Latin American Computing Conference (CLEI). Arequipa, Peru: IEEE, 2015: 286-296. [22] QIAN B, WANG L, HUANG D X, et al. An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers[J]. Computers & Operations Research, 2009, 33(10): 2960-2971.

##### 计量
• 文章访问数:  53
• HTML全文浏览量:  56
• PDF下载量:  2
• 被引次数: 0
##### 出版历程
• 收稿日期:  2020-12-01
• 网络出版日期:  2021-03-24

## 基于离散正弦优化算法的多目标混合零空闲置换流水车间调度

###### 通讯作者: 顾幸生, xsgu@ecust.edu.cn
• 华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 200237

### English Abstract

• 零空闲置换流水车间调度问题（No-idle Permutation Flow Shop Scheduling Problem, NPFSP）是广泛存在于集成电路制造、玻璃纤维加工和铸造等现代工业的组合优化问题[1]。NPFSP通常要求机器都处在零空闲状态，即每台机器要不间断地加工工件[2]。然而在实际的生产过程中，往往只有部分特定的机器因设备昂贵或技术限制等受到零空闲条件的约束。混合零空闲置换流水车间调度问题（MNPFSP）是NPFSP的扩展，其要求部分机器受零空闲条件的约束，其余机器为常规机器。2014年，Pan等[3]首先提出了混合零空闲置换流水车间调度问题，并证明其为NP难问题。然而随着规模的增大，MNPFSP的复杂性呈指数增长，精确算法不再适用，因而，通过高效的智能优化算法解决MNPFSP是学术界和工业界的重要课题。

目前，将智能优化算法应用于MNPFSP的研究并不多。Pan等[3]提出了一种改进的迭代贪婪（Iterated Greedy, IG）算法以最小化makespan。张晓霞等[4]提出了一种改进的分布估计算法（Distribution Estimation Algorithm, EDA），将禁忌搜索（Tabu Search, TS）算法引入了EDA，通过禁忌列表控制EDA的进化方向，并以最小化makespan为优化目标，对比了在7种不同零空闲情况的MNPFSP上的求解效果。Cheng等[5]基于云理论设计了一种新的IG算法对MNPFSP进行求解。Rossi等[6]开发了一种构造性启发式算法，求解以最小化总流水时间（Total Flow Time, TFT）为目标的具有序列相关准备时间的MNPFSP。

本文针对车间生产效率和客户满意度这两个不同的生产需求，将makespan和最大拖期（maximum tardiness）作为优化目标。两者在多目标优化问题的研究中已有相关成果，如Santosa等[7]针对最小化makespan、总拖期时间和总机器空闲时间为目标的flow shop调度问题，提出了一种离散粒子群算法（Discrete Particle Swarm Optimization, DPSO）算法。Pan等[8]为解决零等待flow shop问题，提出了一种离散差分进化（Discrete Differential Evolution, DDE）算法以实现最小化makespan和最大拖期的目标，同时设计了几种加速方法提高算法效率。Lei等[9]针对以最小化总拖期时间（Total Tardiness, TTd）、最大拖期和makespan为目标的多目标混合flow shop问题，提出了一种具有全局交换功能的邻域搜索策略（Neighborhood Search with Global Exchange, NSG），通过全局交换和邻域搜索相结合的方式提高解的质量。Murilo等[10]提出了一种多目标进化算法（Multi-Objective Evolutionary Algorithm, MOEA），在分布估计算法中引入对数据排名的Mallows概率模型，解决了以makespan、总流程时间、总拖期时间为目标的多目标PFSP。

正弦优化算法（Sine Optimization Algorithm, SOA）[11]是通过改进正余弦算法（Sine Cosine Algorithm, SCA）[12]的一种利用正弦函数对个体进行位置更新的全局优化方法。本文在SOA的基础上设计了一种多目标离散正弦优化算法（Multi-objective Discrete Sine Optimization Algorithm, MDSOA）。引入IG算法的破坏重构机制对SOA的位置更新进行了改进，并设计适用于离散调度问题的位置更新策略。构建外部档案集（AS）储存Pareto解集，通过AS选取的当前最优解与个体之间的交叉操作保留最优解的部分信息。利用快速非支配排序（FNDS）和拥挤距离筛选更新种群，以此提高种群的分布性。

(3)  表(7) 参考文献 (22)

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈