基于智能算法的制造系统通用作业调度方法

　第42卷第10期　2008年10月

上海交通大学学报

J

OU RNAL OF SHAN GHA I J IAO TON G UNIV ERSIT Y

Vol. 42No. 10　

Oct. 2008　

　　文章编号:100622467(2008) 1021608205

基于智能算法的制造系统通用作业调度方法

胡燕海1,2, 　严隽琪1, 　马登哲1, 　叶飞帆2

(1. 上海交通大学CIM 研究所, 上海200240; 2. 宁波大学工学院, 宁波315211)

摘　要:通过生产实际情况分析, 提出了制造系统通用作业调度问题(U SP ) 概念, 开发了混杂蚁群

算法(HACO ) , 对U SP 进行求解, 并与采用遗传算法所得解进行了对比. 算例研究采用75×20个标准算例, 以工件的加工流程时间最小化为目标函数, 分别运用运算代数和解集收敛度为结束条件. 计算结果表明, 在计算代数相同时, HACO 算法更容易使解域集中; 在得到同等收敛度时, HACO 算法的计算时间更短.

关键词:通用作业调度问题; 智能算法; 遗传算法; 蚁群算法中图分类号:TP 182; F 273　　　文献标识码:A

Universal Shop facturing System

Algorithm

2, 2

, 　YA N J un 2qi , 　M A Deng 2z he , 　Y E Fei 2f an

112

(1. Instit of CIM , Shanghai Jiaotong University , Shanghai 200240, China ;

2. Faculty of Engineering , Ningbo U niversity , Ningbo 315211, China )

Abstract :The concept of universal shop scheduling problem (U SP ) was proposed based on t he analysis of a real p roduction system. A hybrid ant colony optimization (HACO ) was developed to be applied to t he U SP. The result s were compared wit h t hose of genetic algorit hm. The numerical experiment s make use of several benchmark instances who se scale is up to 75×20. Minimizing makespan is taken as t he objective f unction. Bot h termination conditions of comp utation generation and solution convergence are tested for t he comp utation. From t he numerical experiment s , it can be seen t hat when t he comp utation generation is kept t he same , HACO will make t he solutions more convergent , and when t he convergency is kept t he same , HACO will consume less time.

Key words :universal shop scheduling p roblem (U SP ) ; intelligent algorit hm ; genetic algorit hm ; ant colo 2ny optimization ; sequencing

　　一个实际制造系统中往往包含多种基本作业方式. 如某造船企业的钢板处理与切割中心, 钢板先以一定工艺顺序进行去绣、喷丸、校形等处理; 然后, 以

收稿日期:2007211224

随意顺序到相关工作站进行尺寸检测、板材编号; 再到等离子、火焰等各种切割设备以混杂流水车间方

式进行切割. 按照传统的方法, 上述钢板处理与切割

基金项目:国家自然科学基金资助项目(50575137) ; 浙江省自然科学基金资助项目(Y607470) ; 宁波市自然科学基金资助项目

(2008A610036)

作者简介:胡燕海(19662) , 男, 浙江岱山人, 博士, 主要从事生产计划与调度、知识计算方法等研究. E 2mail :[email protected]. cn.

严隽琪(联系人) , 女, 教授, 博士生导师.

　第10期

胡燕海, 等:基于智能算法的制造系统通用作业调度方法　　

1609

中心内将包含开放作业调度问题(也称自由作业调度问题) (Open Shop Scheduling Pro blem , OSP ) [1]、异顺序作业调度问题(Jo b Shop Schedu 2ling Pro blem , J SP ) [2]和混杂流水作业调度问题(Hybrid Flow Shop Scheduling Problem , HF 2SP ) [3]等基本作业方式, 并分别进行调度.

为改进调度效果, 人们将一个制造系统内并存的多种传统基本作业问题组合成一个多作业问题进行分析. 目前, 已有学者对由OSP 与J SP 或OSP 与流水作业调度问题(Flow Shop Scheduling Prob 2lem , FSP ) 组合成的混合作业调度问题(Mixed Shop Scheduling Problem , MSP ) [426]进行了研究. 本文将OSP 、J SP 和H FSP 3种作业方式构成一个整体进行处理, 并称其为通用作业调度问题(U niversal Shop Scheduling Problem , U SP ) , 其实质为MSP 问题的扩展. 还提出了用于U SP 问题的混杂蚁群算法(Hybrid Ant Colony Optimizatio n , HACO ) , 并与遗传算法(Genetic Algorit hm , GA ) 进行了对比. 计算结果表明, HACO 度和解的收敛性两方面均较有优势.

于某一工件, 其具有先后工序约束关系的作业之间存在单向弧; 其在OSP 中的各作业由于不存在工序约束, 故用双向弧表示该工件在OSP 中的可能顺序关系. 同一阶段中的设备对于不同工件存在双向弧, 表示各个工件在该阶段上的可能顺序关系; 不同工件不同阶段的作业如果均已就绪, 则它们之间存在双向弧, 以实现不同阶段之间的联系. 作业调度是寻找出起始弧、结束弧各一条, 并将上述双向弧转化为单向弧, 即确定双向弧的一个指向, 使这些弧线与单个工件各作业之间表示工序约束关系的单向弧构成一条代表调度方案的路径. 　　通用作业计划的约束条件与4种基本作业计划的普遍约束条件相同, 即假定设备之间存在无限缓冲区, 工件在每台设备上的加工不可中断, 一台设备同时只能加工一个工件, 设备上加工, .

, (1) t max =max (max t ij )

式中, t ij 为j 工件在i 阶段的加工完成时间.

1　问题描述

　　为便于描述问题, 2工件6阶段的U SP 例子进行说明, 其非连接图模型如图1所示. 图中:工件在1、2阶段的作业方式为J SP ;3、4阶段为OSP ;5、6阶段为HFSP. 在J SP 方式中, 工件1的作业顺序为阶段2至阶段1, 工件2反之; 在H FSP 方式中, 第6阶段存在2台平行机. 图1中:N 代表非连接图的起点; F 代表终点; 节点中数字的整数部分表示各工件在不同阶段的作业; 小数部分表示平行机号; 椭圆内包含多个代表平行机作业的节点, 表示这些作业属于同一阶段

.

2　优化算法

　　U SP 问题的求解为N P 问题, 需要采用启发式方法或智能算法. 本文提出了一种HACO 算法求解U SP , 并通过算例对比其与GA 算法的优化效率及收敛性. 2. 1　混杂蚁群算法

ACO 算法已应用于求解旅行商问题、二次分配问题、车间作业计划等, 取得了较好的效果. 但在应用中也发现, 其存在停滞现象, 即搜索到一定程度后, 所有个体所发现的解完全一致, 而陷入局部收敛[7]. 本文提出将GA 算法的交叉、变异算子结合到ACO 算法中, 以突破局部收敛, 构成HACO 算法. 2. 1. 1　HACO 算法过程

(1) 起点N 放置h 个蚂蚁, 在从i 节点到j 节点的路径(i , j ) 上设置相同的初始信息素τij (0) .

(2) 用启发式规则确定t 时刻k 蚂蚁(k =1, 2, …, h ) 在路径(i , j ) 上的启发信息ηij (t ) .

(3) 计算t 时刻k 蚂蚁在i 节点处选择路径(i , j ) 的寻径概率,

αβ

j ∈allowed k

αβ

τ() η() k

6[is t ][is t ]

P ij (t ) =

s ∈allowed k

图1　USP 非连接图模型

Fig. 1　Disjunctive model for USP

　　始于N 点的起始弧指向J SP 中各工件的第1个作业, 同样, 各工件最后一个在并行机上的作业用结束弧指向终点F , 起始弧、结束弧均为单向弧. 对

0其他

(2)

α、β分别为控制信息素及启发信息相对重要式中:

程度的2个参数, 计算前给定; 可行路径集allowed k 包含t 时刻k 蚂蚁从i 节点出发的所有可能路径.

(4) 用轮盘赌方式选择i 节点处k 蚂蚁前进的路径.

(5) 当i 节点处k 蚂蚁前进的路径确定后, 可

能节点到终点F 的单向路径; 各作业方式内部各节点之间的所有可能单、双向路径.

2种作业方式交界处节点之间路径为前一作业方式最后节点通往下一作业方式所有可能节点的单向路径, 需要等到蚂蚁完成前一种作业方式的寻径后方可确定. 此时, 需在allowed k 中增加前一种作业方式最后节点通往下一作业方式所有可能节点的路径:①若下一作业方式为OSP , 则在allowed k 中增加前一种作业方式最后节点通往OSP 所有节点的路径; ②若下一作业方式为J SP , 则在allowed k 中增加前一种作业方式最后节点通往代表J SP 各工件第1个工序节点的路径; ③若下一作业方式为FSP , 则在allowed k 中增加前一种作业方式最后节点通往代表FSP 第1个设备节点的路径; ④若下一作业方式为HFSP , 则在k 中增加前一种作FSP 第1个设备或并.

1种作业方式, 最后一个作业F 的路径以及各种作业方式内部各节, 存在如下约定:

(1) 对于OSP , 若其为第1种作业方式, 则始于起点N 的单向路径指向所有节点; 若其为最后一种作业方式, 则止于终点F 的单向路径源于所有节点. OSP 内部所有节点之间存在双向路径.

(2) 对于J SP , 若其为第1种作业方式, 则始于起点N 的单向路径指向代表各工件第1个工序的节点; 若其为最后一种作业方式, 则止于终点F 的单向路径源于代表各工件最后一个工序的节点.

(3) 对于J SP ,allowed k 中应避免出现死锁路径, 因此, 当k 蚂蚁在J SP 中开始寻径后, 对于每个节点, 找出构成死锁的路径, 并将该路径从k 蚂蚁的allowed k 中删除.

(4) 对于FSP , 若其为第1种作业方式, 则始于

能其他节点的某些路径不再可行(如J SP 中的“死锁”路径) , 在k 蚂蚁的allowed k 中删除这些不能选择的路径, 但仍保留其信息素值, 以供其他蚂蚁及后续计算使用.

(6) 当所有蚂蚁回到终点F 后, 各进行一次变

异和交叉操作. 交叉过程为:先随机确定一对父代路径, 并随机选择2个交叉点. 然后交换2父体中在所选交叉点之间的部分路径, 这部分被称为交叉段. 将父体1的交叉段不变地复制到后代2中, 同样也将父体2的交叉段不变地复制到后代1中. 父体1中的其他路径按原有顺序保留到后代1中, 对父体2进行同样操作. 变异操作采用逆转变异方式, 操作过程为:确定1条父代路径中的2, 2将列. 重新计算经交叉对应的目标函数值. 如果有所优化, 则替换父代路径.

(7) 判断是否满足结束条件. 若满足, 输出计算

结果, 计算结束; 反之, 更新各路径的信息素, 转步骤(2) . 信息素更新方式为

τ(t +1) =ρτ(t ) +

　

k =1

k

Δτij 6

h

(3)

ρ为[0, 1]之间的常数, 1-ρ表示在t ～t +1式中:

k τ时刻信息素的挥发率; Δij 为第k 个蚂蚁从t ～t +1时刻在路径(i , j ) 上的信息量增量,

Δτ=

k

ij

L k

蚂蚁k 经过路径(i , j ) 其他

(4)

Q 为常量, 表示蚂蚁完成一次完整的路径搜索所释

起点N 的单向路径指向代表第1个设备的节点. 若其为最后一种作业方式, 则止于终点F 的单向路径源于代表最后一个设备的节点. 由于所有工件在流水线上的加工顺序一致, 故可将流水线视为一个虚拟设备. 对应每个工件, 用一个虚拟节点代表该虚拟设备. allowed k 中虚拟节点之间存在双向路径.

(5) 对于H FSP , 先将并行机视为单台设备, 则其变为FSP ,allowed k 中的路径与FSP 相同. 当蚂蚁寻径到某并行机时,allowed k 中增加通往各台同类设备的单向路径. 2. 2　遗传算法

　　GA 涉及编码方法和选择、交叉、变异、进化等

放的信息素总量; L k 为蚂蚁k 在路径(i , j ) 上的花费占其路径总花费的比例.

2. 1. 2　可行路径集的确定　allowed k 的确定方法

如下:在allowed k 中通过节点的路径限制, 体现工件加工流程的内在约束关系. 在蚂蚁开始寻径前, 对每个蚂蚁都有相同的初始化allowed k . 该初始化的allowed k 中列出了除各种作业方式交界处节点之间

路径以外的其他所有可能路径, 包括从起点N 到第1种作业方式各可能节点, 最后一个作业方式各可

遗传操作. 对染色体进行选择操作时, 选取适应值优于平均值的染色体放入交叉池用于交叉操作, 以期保持优质基因片段, 尽快收敛. 对实施交叉、变异操作后的子代染色体计算适应值, 若其优于父代染色体值, 则用子代染色体取得父代染色体, 实现种群的进化.

2. 2. 1　编码方法　染色体按作业编码, 采用十进制

紧前作业及紧后作业的位置a 、b, 在(a , b ) 间随机确定一个不同于s 的位置s 1, 将c s 移动至s 1位置, 而

将(a , b ) 间的其他基因依次前移或后移, 即实现变异操作. 如果(a , b ) 间只有一个基因位置s , 则随机产生新的整数s , 直至满足要求. 按这一方法进行变异操作后, 染色体中的编码必然满足工件的工序约束关系.

一个变异操作的例子如下. 一条父代染色体为A , 第1次随机产生位置对应的基因编码为9, 与其存在工序约束关系的紧前作业编码为7, 紧后作业编码为11. 1, 在这2个编码之间随机确定一个不同于9的编码, 设其为4, 将编码9移致编码4所在位置, 得到子代染色体A ′,

A =[[1**********]. 2]A ′=[31572811. 11012. 2]

整数与实数相结合的混合编码方法. 其中, 工件在

H FSP 中的平行机上的作业按实数编码, 其整数部分代表作业号, 小数部分代表平行机号. 对于平行机数≤10的情况, 用于编码的实数保留一位小数; 平行机数>10、≤100的情况, 用于编码的实数保留2位小数; 依此类推. 对于m 个阶段加工n 个工件的U SP 问题, 定义在第i (i =1, 2, …, m ) 阶段加工工件j (j =1, 2, …, n ) 的作业编号为n (i -1) +j. 因此, 染色体中所有基因的整数部分为自然数(1, 2, …, m ×n ) 的一个排列, 代表U SP 一种调度方案所有作业的顺序关系. 图1所示问题的一个可行方案对应的染色体为

A =[[1**********]. 2. 2. 2　交叉操作　、J SP . 在[1, m ×n]范围内随机产生一个整数, 其代表一个作业, 确定与该作业存在工序约束关系的其他作业的基因位置. 进行交叉操作时, 将这些基因原位保留, 去除另一条染色体的上述编码基因, 将剩余的基因按顺序填入前一条染色体的空位上. 根据该交叉操作方法得到的染色体必然满足作业的工序约束关系. 一个交叉操作的例子如下. 2条父代染色体分别为A 、B , 随机产生的整数为5, 与作业5存在工序约束关系的其他作业为1, 3, 7, 9, 11. 在2条父代染色体中保留代表这些作业的基因位, 将一条染色体中的其他基因按顺序插入另一条染色体的空位, 交叉操作后得到子代染色体A ′、B ′:

A =[24681012. 2]

　

　

　

　

3reC 系列标准算例的数据[8]进行研, . 假定各算例中阶段1、2组成J SP , 阶段3、4组成OSP , 其余组成HFSP , 其中, 最后阶段包含2台同类设备. 各工件在J SP 的加工顺序为:奇数序的工件(1,3,5, …, n -1) 从阶段1到阶段2; 偶数序的工件反之. 算例的优化目标为其工件加工流程时间t max 的最小化. 分别采用本文提出的2种算法进行计算, 计算结束条件分别为运算代数G 及解集收敛度σ. 采用运算代数为结束条件时, 对各算例确定分别用2种算法计算的运算代数、种群数等参数, 使算例计算结果稳定时, 它们的运算时间基本相等. 若采用解集收敛度为约束条件, 则需计算每代所有解的收敛度, 当其小于等于设定值时, 运算结束. 解集收敛度计算如下:

3

t max -t max

σ=(5) ×100%

t max

3

式中: t max 为每一代运算所有解目标函数平均值; t max 为每一代运算所有解目标函数最佳值.

通过调整GA 的种群规模、参与交叉操作的染色体数量、变异概率以及HACO 算法的蚁群数量、寻径概率计算式中各参数的指数、信息素更新速度等, 本文试算得到用GA 计算80代或用HACO 算

B =[24861012. 1]

　

A ′=[24861012. 2]

　

　

　

　

B ′=[24681012. 2]

2. 2. 3　变异操作　变异操作采用单亲染色体基因

移位的方法实现. 在每一代所有染色体中按一定概率P c 选择染色体进行变异, 以突破局部搜索领域,

避免早熟. 按概率随机选取一父代染色体并随机产生该染色体中一个基因位置s , 设其对应的编码为c s . 在染色体中找出与该编码存在工序约束关系的

法计算60代后, 每代计算的近优解基本稳定, 且GA 与HACO 算法的计算时间基本相当. 因此, 本文分别以80代和60代作为GA 和HACO 算法运算代数结束条件. 对于收敛度结束条件, 本文设定σ≤1‰. 算例计算结果如表1、2所示.

1612

上　海　交　通　大　学　学　报

表1　以运算代数为结束条件的运算结果

第42卷　

问题.

后续研究可包括用于MSP 、U SP 等问题的新算

法及其算法结构、计算复杂度、算法收敛性等方面的理论分析以及实例研究等. 参考文献:

[1]　Liaw C F. Scheduling two 2machine preemptive open

shop s to minimize total completion time [J].Comput 2ers and Operations R esearch , 2004, 31(8) :134921363. [2]　夏蔚军, 吴智铭, 张　伟, 等. 微粒群优化在Job 2shop

T ab. 1　R esults of taking calculation generation as criterion 算例

reC09reC15reC21reC27reC33reC39

规模

(20, 10) (20, 15) (30, 10) (30, 15) (50, 10) (75, 20)

GA

3

t max

3 t max

3

t max

HACO

3 t max

[***********]7311166

2323. 72762. 33382. 84082. 26474. 111167. 8

[***********]7111164

2323. 22761. 53381. 34080. 76471. 411165. 6

调度中的应用[J].上海交通大学学报, 2005, 39(3) :

3812385.

XIA Wei 2jun , WU Zhi 2ming , ZHAN G Wei , et al. Application of particle swarm optimization in the job 2shop scheduling problem [J].Journal of Shanghai Jiaotong U niversity , 2005, 39(3) :3812385.

[3]　Lina H T , Liao study in a two 2stage hy 2

brid and dedicated machines Journal of Production E conomics , () :1332143.

]Ferrell W , Sale J , Sams J , et al. Evaluating simple

scheduling rules in a mixed shop environment [J].Computers and I ndustrial E ngineering , 2000, 38(1) :39266.

[5]　G iaro K , Kubale M. Compact scheduling of zero 2one

time operations in multi 2stage systems [J].Discrete Applied Mathematics , 2004, 145(1) :952103. [6]　Su L H , Chou F D , Ting W C. Minimizing makespan

in a two 2stage system with flowshop and open shop [J].

Computers

&Industrial

E ngineering , 2005,

49(4) :5202536.

[7]　张宗永, 孙　静, 谭家华. 蚁群算法的改进及其应用

[J].上海交通大学学报, 2002, 36(11) :156421567. ZHAN G Z ong 2yong , SUN Jing , TAN Jia 2hua. Appli 2cation of the improved ant colony algorithm [J].Journal

of

Sh anghai

Jiaotong

U niversity ,

2002,

36(11) :156421567.

[8]　Beasley J E. Flowshop1[EB/OL ].(2006209) [20072

07].http

://www. brunel. ac. uk/depts/ma/research/.

表2　以收敛度为结束条件的运算结果

T ab. 2　R esults of taking convergency as criterion 算例

reC09reC15reC21reC27reC33reC39

GA

3

t max

HACO

t c /s

3t max

t c /s

[***********]7311167

54. 465. 279. 782. 5146. [***********]165

26. 730. 641. 6775. 35

　　由表1可见, 在一定运算时间内, 对于较小规模算例, GA 也能得到较好的近优解; 但对于较大规模算例, HACO 算法的寻优效果更佳. 由表2可见, 对于各算例HACO 算法更容易使解域集中, 即获得相同的收敛度时, HACO 算法的运算时间t c 更短.

4　结　语

　　本文针对实际制造系统, 提出了U SP 的概念, 并分别采用GA 和HACO 算法对U SP 进行了求解. 计算结果表明, HACO 算法在寻优效果和解的收敛性两方面均较有优势. 本文方法也可用于各加工阶段都存在平行机的U SP 情况. 此外, 本文所研究的U SP 问题也可望应用于制造系统之外邮政、计算机处理器、网络路由等其他领域的U SP 作业调度

上海交通大学学报

国家期刊奖百种重点期刊　　中国高校精品科技期刊

欢迎投稿　欢迎订阅