多目标粒子群算法求解混合多处理机任务作业车间调度问题研究  

Research on Multi-objective Particle Swarm Algorithm for Solving Hybrid Job-shop Scheduling with Multiprocessor Task

作　　者：吕媛媛 樊坤[1] 瞿华[1] 周浪 LV Yuan-yuan;FAN Kun;QU Hua;ZHOU Lang(School of Economics and Management,Beijing Forestry University,Beijing 100083,China)

机构地区：[1]北京林业大学经济管理学院,北京100083

出　　处：《小型微型计算机系统》2022年第1期218-224,共7页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(71502015)资助;北京市社会科学基金项目(16GLC059)资助。

摘　　要：混合多处理任务作业车间调度(Hybrid Job-shop Scheduling with Multiprocessor Task, HJSMT)是作业车间调度和多处理机任务调度的混合调度问题,即每个工件由多个工序组成且每个工序都需要一组机器同时进行加工.目前对HJSMT研究较少且集中于单目标问题,因此针对多目标HJSMT问题,本文以最小化最大完工时间和最小化总拖延时间为目标建立双目标HJSMT模型,提出一种新的改进多目标粒子群算法(IMOPSO)对其求解.该算法以IPOX交叉和多轮变异策略更新粒子;根据动态邻域思想设计新的外部种群寻优机制(EPOM)寻找每一代较优解,结合个体拥挤距离删减并维护外部种群.采用5-Job与10-Job两个算例分别进行仿真实验,结果表明IMOPSO算法在选取邻域粒子数量为2时求解效果最好,并且通过与NSGA-II算法进行对比,验证了IMOPSO的有效性.Hybrid Job-shop Scheduling with Multiprocessor Task(HJSMT)is a hybrid scheduling problem of job shop scheduling and multi-processor task scheduling, that is, each workpiece is composed of multiple processes and each process requires a group of machines to process at the same time.At present, there are few studies on HJSMT and most of them focus on single-objective problems.Therefore, for the multi-objective HJSMT problem, this paper establishes a double-objective HJSMT model with the goal of minimizing the maximum completion time and minimizing the total delay time and proposes a new Improved Multi-Objective Particle Swarm Optimization(IMOPSO)to solve the model.The algorithm updates particles with IPOX crossover and multi-round mutation strategies.According to the dynamic neighborhood idea, a new External Population Optimization Mechanism(EPOM)is designed to find the best solution for each generation, and then combined with the crowding-distance to delete and maintain the external population.Two examples of 5-Job and 10-Job are used to carry out simulation experiments.The results show that the IMOPSO algorithm has the best solution effect when the number of neighboring particles is 2,and the effectiveness of IMOPSO was verified by comparison with NSGA-II algorithm.

关 键 词：双目标 多处理机任务 作业车间调度 粒子群算法 混合车间调度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]