![](https://csdnimg.cn/release/download_crawler_static/19677053/bg1.jpg)
第
29
卷第
6
期
2008
年
12
月
河南科技大学学报:自然科学版
Vo
J.
29
No.6
Dec.
2008
Journal
of
Henan University
of
Science and Technology: Natural Science
文章编号:
1672 - 6871
(2008)
06 - 0049 - 04
求解作业车间调度问题的粒子群优化算法
张慧霞,张炭,高兴宝
(陕西师范大学数学与信息科学学院,陕西西安
710062)
摘要:讨论了作业车间调度问题的数学表达模型,考虑将粒子群优化算法与差异演化算法的优点结合起来,提
出求解作业车间调度问题的新的混合粒子群优化算法,对
7
个标准算例的仿真结果表明了算法的有效性和优
越性。
关键词:作业车间调度;混合粒子群算法;差异演化
中图分类号
:TPI8
文献标识码
:A
。
前言
作业车间调度问题
(Job
Shop
Scheduling
Problem
,简称
JSSP)
,具有很强的工程背景,在现实生活中
也有广泛的应用,它是一个典型的
NP-
难组合优化问题,应用启发式算法求得其近似解成为现实的解
决方案,如邻域搜索法,模拟退火法
SA[I]
禁忌搜索法
TB[2]
遗传算法
GA[3
1
粒子群算法
[
4
斗]等,也被
应用到调度问题中,井且取得了较好的效果。然而粒子群算法的寻优能力主要来自粒子之间的相互作
用和相互影响,粒子本身没有变异机制,从而
PSO
容易陷入局部最优解,为了克服这个缺点,人们对粒
子群算法做了许多改进口斗]。本文在算法的寻优过程中,通过评价粒子聚焦的程度,从而引人差异演化
变异机制[
10]
增加了粒子群的多样性,改善了搜索全局最优解的能力。
1
作业车间调度的数学模型
作业车间调度问题是要在台机器上加工
n
个工件,每个工件有
m
个工序,加工必须满足:
(1)一台机器一次只能加工一个工件的一个工序;
(2)
每道工序必须在指定的机器上加工给定的时间段
ti/
i = 1 - n ,j = 1 -
m)
;
(3)
按照加工工艺的规定,每道工序必须在它前面的工序加工完毕后再加工;
(4)
每道工序从开始到结束,不会被另外的工序所中断。
T.;
表示第
i
个工件的第
j
个工序在对应的机器上的加工时间。调度的目的是在满足约束的条件下
寻找工序在机器上的排列(即由台机器上加工的工序的排列)
,使得所有机器的完工的最长时间最短,
即优化的目标函数为
minl
max(
T
ι)
I
1 , 2
,…,
m
、、
.J
1
,
t
飞
其中
T
i
表示机器的完工时间。
2
粒子群
PSO
算法
2.1
粒子群算法原理
粒子群优化算法
(Particle
Swarm
Optimization
,简称
PSO)
是最新的进化算法之一,它是基于迭代模
式的优化算法。最初由
Kennedy
和
Eberhart
提出,用于求解连续非线性函数优化问题,而后被广泛应用
于神经网络训练,任务指派和排序问题,官具有容易执行且计算高效的优点
[11
-13]
。
在粒子群算法中,随机产生的解(称为粒子)作为初始种群,在每次迭代过程中,粒子带一个动态调
基金项目:国家自然科学基金项目
(60671063)
;陕西省科学技术计划项目
(2
∞
6A02)
作者简介:张慧霞(J
982 - )
,女.河南源filJ人,硕士生;高兴宝(1
966
-
),男,陕西陇县人,教授,博士生导师.主要从事主要从事鼓
优化理论与算法,进化计算,神经网络的研究
收稿日期
:2008
-
03
- 10