• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2022, Vol. 58 ›› Issue (6): 295-308.doi: 10.3901/JME.2022.06.295

• 交叉与前沿 • 上一篇    

扫码分享

基于混合遗传算法求解分布式流水车间逆调度问题

牟健慧1, 段培永2, 高亮3, 彭武良4, 丛建臣5   

  1. 1. 烟台大学机电汽车工程学院 烟台 264005;
    2. 烟台大学计算机与控制工程学院 烟台 264005;
    3. 华中科技大学机械工程与科学学院 武汉 430074;
    4. 烟台大学经济管理学院 烟台 264005;
    5. 山东理工大学机械工程学院 淄博 255001
  • 收稿日期:2021-03-13 修回日期:2021-09-25 出版日期:2022-03-20 发布日期:2022-05-19
  • 通讯作者: 段培永,男,1968年出生,博士,教授,博士研究生导师。主要研究方向为人工智能。E-mail:duanpeiyong@sdnu.edu.cn
  • 作者简介:牟健慧,女,1983年出生,博士,副教授,硕士研究生导师。主要研究方向为车间调度优化与理论分析。E-mail:mjhcr@163.com;高亮,男,1976年出生,博士,教授,博士研究生导师。主要研究方向为智能优化调度。E-mail:gaoliang@hust.edu.cn;彭武良,男,1973年出生,博士,教授,硕士研究生导师。主要研究方向为生产管理、项目调度。E-mail:wliang.p@ytu.edu.cn;丛建臣,男,1963年出生,工程技术应用研究员。主要研究方向为人工智能。E-mail:jchcong@tianrun.com
  • 基金资助:
    国家自然科学基金(52175487,62073201)、山东省自然科学基金(ZR2021ME223,ZR2019MEE093)、山东重点研发(2019JZZY010445)、烟台市科技创新发展计划(2022GCCRC158)和烟台市科技计划(2021XDHZ077)资助项目。

Hybrid Genetic Algorithm for Distributed Flow Shop Inverse Scheduling Problem

MU Jianhui1, Duan Peiyong2, GAO Liang3, Peng Wuliang4, Cong Jianchen5   

  1. 1. School of Mechatronics and Automotive Engineering, Yantai University, Yantai 264005;
    2. School of Computer and Control Engineering, Yantai University, Yantai 264005;
    3. School of Mechanical Engineering and Science, Huazhong University of Science and Technology, Wuhan 430074;
    4. School of Economics and Management, Yantai Universty, Yantai 264005;
    5. School of Mechanical Engineering, Shandong University of Technology, Zibo 255001
  • Received:2021-03-13 Revised:2021-09-25 Online:2022-03-20 Published:2022-05-19

摘要: 分布式调度是智能制造的新模式,急需新的调度方法来应对动态多变的市场需求。针对分布式置换流水车间问题,采用逆调度方法优化,通过最小调整加工参数,使得尽可能保证原排序的情况下调度最优。以最小化调整加工时间为目标,建立流水车间逆调度数学模型,针对逆调度问题特征,在遗传算法的框架下提出一种混合遗传优化算法。首先,基于逆调度参数可调的特征,提出基于工序的小数机制双层编码方案,能够实现参数的调整,保证可能解;提出改进启发式方法和基于规则的方法相结合的混合初始化方法;其次,采用适合问题特征的交叉、变异操作执行搜索;为协调全局搜索与局部搜索能力,设计局部搜索策略和学习机制的双种群协同搜索策略。为验证算法性能,基于问题实例采用三种算法进行比较,并且进行统计分析,其结果表明所提算法能更有效求解分布式流水线逆调度问题。

关键词: 分布式调度, 逆调度, 流水车间调度, 混合遗传算法, 种群协同

Abstract: Distributed scheduling is a new mode of intelligent manufacturing, which is in urgent need of new scheduling methods to meet the Dynamic and changeable market demand. To solve the distributed permutation flow shop problem, the inverse scheduling method is used to optimize the job shop scheduling by minimizing the processing parameters. Aiming at minimizing the adjusted processing time, a mathematical model of flow shop reverse scheduling is established, and a hybrid genetic optimization Algorithm is proposed under the framework of genetic algorithm. Firstly, based on the characteristics of the inverse scheduling parameters, an improved operation-based decimal mechanism double coding scheme is proposed, which can adjust the parameters and ensure the possible solution. Secondly, a hybrid initialization method is adopted by improving the NEH heuristic method and the rule-based method, in order to coordinate the ability of global search and local search, the local search strategy and the double-population cooperative search strategy with learning mechanism are designed. In order to verify the performance of the proposed algorithm, three algorithms are compared and analyzed based on the problem examples. The results show that the proposed algorithm can solve the distributed pipeline inverse scheduling problem more effectively.

Key words: distributed scheduling, inverse scheduling, flow shop scheduling, hybrid genetic algorithm, population coordination

中图分类号: