改进粒子群算法求解车间作业调度问题  

An Improved Particle Swarm Optimization Algorithm for Job Shop Scheduling Problem

作　　者：葛晶 高广宇 王虔翔 Ge Jing;Gao Guangyu;Wang Qianxiang(Department of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081)

机构地区：[1]北京理工大学计算机学院,北京100081

出　　处：《现代计算机》2022年第13期39-44,50,共7页Modern Computer

摘　　要：车间作业调度问题给出了一组作业和一组机器,每台机器一次最多只能处理一项工作,每个作业由一系列操作组成,每个操作都需要在给定机器上以给定长度的不间断时间段内进行处理,目的是求解最优的加工顺序,使调度的总完工时间最小。本文使用的方法是粒子群优化算法,思想来源于鸟类的群体觅食行为,属于群智能算法的一种,但是该算法存在局部搜索能力差,易陷入局部极值的问题。本文借鉴交叉变异的思想对其进行改进,实验证明本文方法明显优于标准粒子群算法,在给定用例取得了最优测试结果。Given a set of jobs and a set of machines,the Job Shop Scheduling Problem(JSSP)is an optimization problem,in which jobs are assigned to resources at particular times,with the objective of that minimizes the total completion time of the scheduling.The proposed algorithm is based on the Particle Swarm Optimization(PSO)algorithm,the idea of which comes from the group foraging behavior of birds and belongs to a kind of swarm intelligence algorithm.But the PSO algorithm is easy to fall into local optimum in high-dimensional space and has a low convergence rate in the iterative process.In this paper,we propose an improved PSO algorithm for JSP,borrowing the idea of Crossover-Mutation.Finally,it experimentally proves that the proposed method is significantly better than the standard PSO algorithm,and the optimal results are achieved in the given use cases.

关 键 词：车间作业调度 粒子群优化算法 群智能算法 交叉变异 

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