基于改进BPSO算法求解一类作业车间调度问题

Solving a Class of Job-Shop Scheduling Problem based on Improved BPSO Algorithm

针对某一大型机械厂结构车间的作业调度问题(JSP),考虑技术工人操作熟练度影响因素,以及离散型并行生产的特点,建立新的符合实际生产情况的数学模型,提出利用离散二进制粒子群(BPSO)算法来解决如何安排m位工人加工n个结构件,以达到加工时间最短的一类JSP调度问题,并依据求解的特殊性对该算法进行了改进.制定新的初始粒子产生策略,保证在可行解空间内开始进行寻优;引入"记忆库"、修改Sig函数和加入判断条件,确保粒子每次更新后都满足模型中的等式约束.通过实例验证,证实该算法是有效的,并能够得到较好的结果.同时,该数学模型在离散制造业中也具有广泛的应用价值.

Analyzing the special job shop scheduling problem of a large-scale machine shop, considering workers＇ operational qualification and characteristics of discretely concurrent production, a novel mathematical model has been proposed to meet actual production. In addition, an improved Binary Particle Swarm Optimizer （BPSO） algorithm has been developed for solving the problem how to arrange m workers to process n structures, in order to optimize the minimum completion time of the jobs. In this improved BPS0, a new method of making initial particles has been presented for searching optimum particle in the feasible dimensional problem space. Besides, importing memory base, modifying Sig function and considering constraint condition have used in algorithm for making updated particles to meet the constraint equation of mathematical model. Algorithm examples research demonstrates that the improved BPS0 algorithm is effective and can achieve good results. Moreover, the mathematical model has wide application in discrete mamffacture.