基于改进Jaya算法的置换流水车间调度问题研究

doi:10.3969/j.issn.1007-7375.2022.03.017

工业工程 ›› 2022, Vol. 25 ›› Issue (3): 141-150.doi: 10.3969/j.issn.1007-7375.2022.03.017

基于改进Jaya算法的置换流水车间调度问题研究

刘梦伊¹, 薛燕社², 马思奕¹, 张超勇²

1. 河海大学商学院，江苏南京 211100;
2. 华中科技大学机械科学与工程学院，湖北武汉 430074

收稿日期:2020-09-25 发布日期:2022-07-06
通讯作者: 张超勇 (1972—)，男，江苏省人，教授，主要研究方向为智能调度、智能系统优化和可持续制造。 E-mail: zcyhust@hust.edu.cn E-mail:zcyhust@hust.edu.cn
作者简介:刘梦伊(2000—)，女，湖北省人，本科生，主要研究方向为调度算法
基金资助:
国家自然科学基金资助项目(51875429)；广东省重点领域研发计划资助项目(2019B090921001)

An Improved Jaya Algorithm for Permutation Flow Shop Scheduling Problem

LIU Mengyi¹, XUE Yanshe², MA Siyi¹, ZHANG Chaoyong²

1. Business School of Hohai University, Nanjing 211100, China;
2. School of Mechanical Science and Engineering , Huazhong University of Science and Technology, Wuhan 430074, China

Received:2020-09-25 Published:2022-07-06

摘要/Abstract

摘要： 置换流水车间调度问题（permutation flow shop scheduling problem, PFSP）广泛存在于流程和离散制造企业。本文提出一种改进的Jaya算法求解最小化最大完工时间为目标的PFSP。在改进Jaya算法中，设计了基于最优和最差个体的4种个体更新方案，通过4种邻域结构对个体进行局部搜索，并通过多样性控制策略来保证种群的多样性。采用改进Jaya算法分解求解Car、 Rec和Taillard基准问题，并与其他算法进行比较，验证了所提算法的有效性。

关键词: 置换流水车间调度问题, Jaya算法, 局部搜索, 基准问题

Abstract: Permutation flow shop scheduling problem is widely applied in process and discrete manufacturing enterprises. An improved Jaya algorithm is proposed to solve the PFSP with the minimum makespan. In the improved Jaya algorithm, four individual updating schemes based on the best and the worst individuals are proposed, and local search for individuals is carried out through four neighborhood structures. Diversity control strategy is applied to ensure the diversity of population. The improved Jaya algorithm is used to solve the Car, Rec and Taillard benchmark instances, and the experimental results validate the effectiveness of the proposed algorithm.

Key words: permutation flow shop scheduling problem, Jaya algorithm, local search, benchmark problem

中图分类号:

TP18

刘梦伊, 薛燕社, 马思奕, 张超勇. 基于改进Jaya算法的置换流水车间调度问题研究[J]. 工业工程, 2022, 25(3): 141-150.

LIU Mengyi, XUE Yanshe, MA Siyi, ZHANG Chaoyong. An Improved Jaya Algorithm for Permutation Flow Shop Scheduling Problem[J]. Industrial Engineering Journal, 2022, 25(3): 141-150.

参考文献

[1] RUIZ R, STUTZLE T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2007, 177: 2033-2049
[2] GOVINDAN K, BALASUNDARAM R, BASKAR N, et al. A hybrid approach for minimizing makespan in permutation flowshop scheduling[J]. Journal of Systems Science and Systems Engineering, 2017, 26(1): 50-76
[3] 汤可宗, 詹堂森, 李佐勇, 等. 一种求解置换流水车间调度问题的多策略粒子群优化[J]. 南京理工大学学报, 2019, 43(1): 48-53
TANG Kezong, ZHAN Tangsen, LI Zuoyong, et al. Multi-strategy particle swarm optimization for solving permutation flow-shop scheduling problem[J]. Journal of Nanjing University of Science and Technology, 2019, 43(1): 48-53
[4] CHEN C L, HUANG S Y, TZENG Y R, et al. A revised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem[J]. Soft Computing, 2014, 18(11): 2271-2282
[5] 张敏, 汪洋, 方侃. 基于改进区块进化算法求解置换流水车间问题[J]. 计算机集成制造系统, 2018, 24(5): 1207-1216
ZHANG Min, WANG Yang, FANG Kan. Improved block-based evolutionary algorithm for solving permutation flowshop problem[J]. Computer Integrated Manufacturing System, 2018, 24(5): 1207-1216
[6] FERNANDO L R, MARCELO S N, JULIANA K S. An effective constructive heuristic for permutation flow shop scheduling problem with total flow time criterion[J]. The International Journal of Advanced Manufacturing Technology, 2017, 90: 1-4
[7] KARABULUT K. A hybrid iterated greedy algorithm for total tardiness minimization in permutation flowshops[J]. Computers & Industrial Engineering, 2016, 98: 300-307
[8] RAO V R. Jaya: a simple and new optimization algorithm for solving constrained and unconstrained optimization problems[J]. International Journal of Industrial Engineering Computations., 2016, 7(1): 19-34
[9] 潘全科, 高亮, 李新宇. 流水车间调度及其优化算法[M]. 武汉: 华中科技大学出版, 2014.
[10] TASGETIREN M F, LIANG Y C, SEVKLI M, et al. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem[J]. European Journal of Operational Research, 2007, 177(3): 1930-1947
[11] LIU B, WANG L, JIN Y H. An effective PSO-based memetic algorithm for flow shop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37(1): 18-27
[12] 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
[13] MARICHELVAM M K, TOSUN Ö, GEETHA M. Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time[J]. Applied Soft Computing, 2017, 55: 82-92
[14] LAHA D, CHAKRABORTY U K. An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2009, 44(5-6): 559-569
[15] MARINAKIS Y, MARINAKI M. Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem[J]. Soft Computing, 2013, 17(7): 1159-1173

基于改进Jaya算法的置换流水车间调度问题研究

An Improved Jaya Algorithm for Permutation Flow Shop Scheduling Problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	禹春霞, 刘玉茹, 高旭. 面向用户个性化需求的云服务商推荐[J]. 工业工程, 2019, 22(2): 1-9.
[2]	包珊珊, 张敏, 尹健康, 蔡振宇. 考虑半托盘出库的堆垛机复合作业拣选路径优化研究[J]. 工业工程, 2019, 22(1): 90-99.
[3]	郝志刚. 考虑医患满意度和手术成本的日手术排程方法[J]. 工业工程, 2017, 20(4): 49-56,71.
[4]	蔡子维, 杨春燕. 可拓创新方法与六西格玛管理方法的集成研究[J]. 工业工程, 2017, 20(3): 60-67.
[5]	王维军, 罗伟. 基于改进智能水滴算法的冷链物流配送路径优化问题研究[J]. 工业工程, 2017, 20(2): 38-43.
[6]	禹春霞, 李南南. 面向燃气具的用户个性化推荐模型[J]. 工业工程, 2019, 22(6): 57-66.
[7]	芦娟, 夏扬坤, 邹安全, 符卓, 王松, 魏占国, 符瑛. 带装载能力的需求依背包拆分车辆路径问题[J]. 工业工程, 2019, 22(6): 67-73.
[8]	刘洪伟, 胡琪, 徐冉, 王明洁. 基于直线往复单智能RGV系统单工序调度研究[J]. 工业工程, 2020, 23(2): 34-40.
[9]	唐红涛, 方博, 高晓灵, 李香怡, 殷伟铭. 基于GSA-GA神经网络的铸造企业订单准入评价研究[J]. 工业工程, 2020, 23(4): 121-130.
[10]	唐红涛, 杨志鹏, 刘家毅. 考虑工序并行的差异工件批调度研究[J]. 工业工程, 2021, 24(3): 68-76,114.
[11]	杨静宗, 杨天晴, 吴丽玫. 基于ITD-SVD和MOMEDA的故障特征提取方法[J]. 工业工程, 2021, 24(6): 48-56.
[12]	杨静宗, 施春朝, 杨天晴, 吴丽玫. 基于LMD和ABC优化KELM的故障诊断方法[J]. 工业工程, 2022, 25(3): 124-131.