[1]轩 华,李海云,李 冰.具有机器可利用性的双目标置换流水车间调度[J].郑州大学学报(工学版),2022,43(05):17-23.[doi:10.13705/j.issn.1671-6833.2022.05.003]
　XUAN Hua,LI Haiyun,LI Bing.Bi-objective Permutation Flow Shop Scheduling with Machine Availability[J].Journal of Zhengzhou University (Engineering Science),2022,43(05):17-23.[doi:10.13705/j.issn.1671-6833.2022.05.003]
点击复制

具有机器可利用性的双目标置换流水车间调度()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
43
期数:
2022年05期
页码:
17-23
栏目:
出版日期:
2022-08-22

文章信息/Info

Title:
Bi-objective Permutation Flow Shop Scheduling with Machine Availability
作者:
轩 华;  李海云;  李 冰
郑州大学管理学院;

Author(s):
XUAN Hua;  LI Haiyun;  LI Bing
School of Management, Zhengzhou University, Zhengzhou 450001, China
关键词:
Keywords:
bi-objective permutation flow shop;  machine availability;  release time;  improved genetic algorithm;  generationschemes of neighborhood solutions
分类号:
TB49
DOI:
10.13705/j.issn.1671-6833.2022.05.003
文献标志码:
A
摘要:
研究了具有机器可利用性的置换流水车间调度问题,引入 CDS 启发式算法和局域搜索构造出改进遗传算法,用于同时最小化总加权完成时间和总加权拖期。 应用 CDS 启发式算法产生 40%初始工件加工序列群,其余 60%的初始工件加工序列群则通过随机程序产生,以此来提高初始工件加工序列群的质量。 针对交叉和变异之后的工件加工序列,设计基于两两交换、单工件插入和多工件插入 3 种邻域解生成机制的局域搜索,以提高解的搜索空间。 将 所提出的改进遗传算法与基于遗传算法的 3 种启发式算法进行仿真实验,结果表明:所提算法在平均 77. 65 s 内相对于其他算法的目标改进率分别为 5. 05%、3. 09%、7. 33%,这也说明了所提算法在较短的时间内能得到更好的目标值;随着问题规模的增大,改进效果更佳。
Abstract:
A permutation flow shop scheduling problem with machine availability was studied. An improved genetic algorithm was proposed by introducing CDS heuristic algorithm and local search so that the total weighted completion time and total weighted tardiness were minimized. To improve the quality of the initial job processing sequence group, the CDS heuristic algorithm is applied to generate 40% of the group and the remaining 60% of the initial job processing sequence group was yielded by random procedure. For the job processing sequence after crossover and mutation, three generation schemes of neighborhood solutions based on pair-wise exchange, single-job insertion and multiple-job insertion were designed to carry out local search in order to extend the search space. The proposed improved genetic algorithm was tested with three genetic algorithm based heuristic algorithms. The results showed that the target improvement rate of the proposed algorithm was 5.05%, 3.09% and 7.33% in the average 77.65 s, compares with other algorithms. It also showed that the proposed algorithm could obtain better target values in a shorter time. With the increase of the problem scale, the improvement effect was better.

参考文献/References:

[1] YENISEY M M, YAGMAHAN B. Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends [ J ] . Omega, 2014, 45: 119-135.

[2] JOHNSON S M. Optimal two-and three-stage production schedules with setup times included [ J ] . Naval research logistics quarterly, 1954, 1(1) : 61-68. [3] ZHAO F Q, LIU Y, ZHANG Y, et al. A hybrid harmony search algorithm with efficient job sequence scheme and variable neighborhood search for the permutation flow shop scheduling problems[ J] . Engineering applications of artificial intelligence, 2017, 65: 178-199.
[4] MOSHEIOV G, SARIG A, STRUSEVICH V A, et al. Two-machine flow shop and open shop scheduling problems with a single maintenance window[ J] . European journal of operational research, 2018, 271( 2) : 388-400.
[5] MIYATA H H, NAGANO M S, GUPTA J N D. Integrating preventive maintenance activities to the no-wait flow shop scheduling problem with dependent-sequence setup times and makespan minimization[ J]. Computers & industrial engineering, 2019, 135: 79-104.
[6] AGGOUNE R, PORTMANN M C. Flow shop scheduling problem with limited machine availability: a heuristic approach[ J] . International journal of production economics, 2006, 99(1 / 2) : 4-15.
[7] 周炳海, 刘子龙. 考虑衰退的流水车间生产与预防 性维护集成调度方法[ J] . 计算机集成制造系统, 2016, 22(5) : 1272-1278. 
ZHOU B H, LIU Z L. Integrated scheduling method of flow shop production and preventive maintenance considering decline[ J] . Computer integrated manufacturing systems, 2016, 22(5) : 1272-1278. 
[8] ZHANG Z K, TANG Q H, CHICA M. Maintenance costs and makespan minimization for assembly permutation flow shop scheduling by considering preventive and corrective maintenance [ J] . Journal of manufacturing systems, 2021, 59: 549-564.
[9] BOUFELLOUH R, BELKAID F. Bi-objective optimization algorithms for joint production and maintenance scheduling under a global resource constraint: application to the permutation flow shop problem[J]. Computers & operations research, 2020, 122: 104943. 
[10] ABDEL-BASSET M, GUNASEKARAN M, EL-SHAHAT D, et al. A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem [ J] . Future generation computer systems, 2018, 85: 129-145.
[11] LIU Y, YIN M H, GU W X. An effective differential evolution algorithm for permutation flow shop scheduling problem[ J] . Applied mathematics and computation, 2014, 248: 143-159.
[12] XIE Z P, ZHANG C Y, SHAO X Y, et al. An effective hybrid teaching-learning-based optimization algorithm for permutation flow shop scheduling problem[J]. Advances in engineering software, 2014, 77: 35-47. 
[13] BENTTALEB M, HNAIEN F, YALAOUI F. Twomachine job shop problem under availability constraints on one machine: makespan minimization[ J]. Computers & industrial engineering, 2018, 117: 138-151. 
[14] 轩华, 秦莹莹, 王薛苑,等. 带恶化工件的 PFS 调 度的混合遗传算法 [ J] . 工 业 工 程 与 管 理, 2017, 22(3) : 1-6,15. 
XUAN H, QIN Y Y, WANG X Y, et al. Hybrid genetic algorithm for PFS scheduling with deteriorating artifacts[ J] . Industrial engineering and management, 2017, 22(3) : 1-6,15. 
[15] 轩华, 罗书敏, 王薛苑. 可重入混合流水车间调度 的改进遗传 算 法 [ J] . 现 代 制 造 工 程, 2019 ( 2) : 18-23,35. 
XUAN H, LUO S M, WANG X Y. Improved genetic algorithm for reentrant hybrid flow shop scheduling [ J] . Modern manufacturing engineering, 2019 ( 2 ) : 18-23,35. 
[16] SHAHVARI O, LOGENDRAN R. Hybrid flow shop batching and scheduling with a bi-criteria objective [ J ] . International journal of production economics, 2016, 179(3) : 239-258. 
[17] YAZDANI M, ALETI A, KHALILI S M, et al. Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem[ J] . Computers & industrial engineering, 2017, 107: 12-24.

更新日期/Last Update: 2022-08-20