![](https://csdnimg.cn/release/download_crawler_static/18695119/bg1.jpg)
第
36
卷第
1
期
2010
年
1
月
北京工业大学学报
JOURNAL
OF
BEljING
UNIVERSITY
OF
TECHNOLOGY
Vo
l. 36
No.l
Jan.
2010
基于离散蛙跳算法的零空闲流水线
调度问题求解
王亚敏
1
,
2
冀俊忠潘全科
2
(1.北京工业大学多媒体与智能软件技术北京市重点实验室,北京
100124;
2.
聊城大学计算机学院,山东聊城
252059)
摘
要:针对零空闲流水线调度问题,提出了一种新的离散化蛙跳求解算法.该算法借助蛙跳算法优化机理,采
用基于工件序列的编码方式和新的个体产生方法扩展了传统蛙跳算法的求解模型,并结合简化邻域搜索算法给
出了
3
种改进策略.仿真实验表明了所提算法及策略的有效性.
关键词:零空闲流水线调度;离散蛙跳算法;邻域搜索
中图分类号:
TP
18
文献标志码
:A
文章编号:
0254
-0037(2010)01
-0124
-07
车间调度问题的求解及其优化技术是制造业实现生产过程合理化、自动化、集成化的基础和关键.其
中,零空闲流水线调度(
no
_ idle
flow
shop
,记为
NIFS)
是一类组合优化问题
[I
J
;
Baptiste
等
[2J
提出了解决
NIFS
问题的分枝限界法;
Kalczynski
等
[3J
提出了解决
NIFS
问题的构造式启发方法;
Bzraz
等
[4J
提出了有效
的改进贪心算法;一些基于离散粒子群优化算法[町、差分进化算法
[6J
等相继被提出;
Eusuff
等[7]首次提出
了蛙跳算法(
shuffled
frog
leaping
algorithm
,记为
SFLA)
,并应用于水管网络扩充中管道尺寸最小化问题的
求解.由于蛙跳算法能结合生物种群的遗传行为和群落间信息交流的社会行为,是解决组合优化问题的
有效工具
[8J
本文提出了基于离散蛙跳算法的
NIFS
问题的求解方法.采用基于工件序列的编码方式和新的个体
产生方法扩展了传统蛙跳算法的求解模型,提出了解决
NIFS
问题的蛙跳算法,并给出了
3
种提高性能的
改进策略.
1
NIFS
问题描述及邻域搜索算法
1.
1
NIFS
问题描述
n
个工件在
m
台机器上流水加工,每个工件在机器上的加工顺序相同,同时,约定每个工件在每台机
器上只加工
1
次,而在同一机器上加工的相邻工件之间没有等待时间,且机器之间存在元限缓冲区.在巳
知各工件在各台机器上所需加工时间的前提下,问题的求解目标是得到满足上述约束条件的可行调度,使
得最大完工时间最短.
文献
[5J
提出了通过完工时间差或开工时间差来计算最大完工时间的方法.给定单个工件的排序
作=
1
1T
1
,叭,…,7T
n
~
,而
1T'
(
i)
= 1
1T
1
,叭,…,矶|和
71(ij
=
1
1T
i
,1T
i
+
1
,
…,作
i
表示其中的
2
个部分排序.
令
F(
1T
'(i)
小
j
+
1)
表示排序作
e
(
i)
中机器
j
和
j+1
的完工时间差
,
E(
71
(i)小
j
+
1)表示排序矿(
i)
中机
器
j
和
j+1
的开工时间差,而
p(
1T
i
,j)表示工件
1T
i
在机器
j
上的加工时间.
如图
1
(a)
所示,当从前往后依次增加工件时最大完工时间
F(
τ'
(1
)小
j
+
1)
= p (
1T
1 ,j + 1 ) , j = 1 ,2
,…
,m
-1
、
l/
喃自
A
'''飞
收稿日期:
2008
-0
5-26.
基金项目:北京市自然科学基金资助项目
(4083034)
,北京市教育委员会科技发展资助项目
(KM
200610005020).
作者简介:王亚敏(1
979
一)
,女,山东精泽人,讲师.