多工艺路线的作业车间模糊调度优化
潘全科 副教授潘全科1 朱剑英2
1.聊城大学计算机学院，聊城,252059
2.南京航空航天大学机电学院，南京,210016
摘要：对具有模糊加工时间和模糊交货期的多工艺路线的作业车间调度问
题进行了研究；以最大化平均满意度为调度目标，建立了作业车间模糊调度的数学模型，提出了一种基于遗传算法的全局优化的调度算法；设计了包含工序及其
usually
加工机床信息的染色体编码，对染色体的解码方法、交叉方法和变异方法进行了研究。仿真结果表明，该算法是可行的，与其他同类研究相比，有一定的优越性。
关键词：作业调度；模糊加工时间；模糊交货期；遗传算法
中图分类号:TP278 文章编号:1004—132Ⅹ(2004)24—2199—04
An Efficient Algorithm for Job Shop Scheduling Problems with Fuzzy Processing Time ,Fuzzy Duedate and Alternative Machines
Pan Quanke 1 Zhu Jianying
2
1.Liaocheng Univercity ,Liaocheng ,252059
2.Nanjing University of Aeronautics and Astronautics ,Nanjing ,210016
A bstract :By considering the impreci or fuzzy nature of the data and functional sameness of machines in real world problems ,job -shop scheduling problems with fuzzy processing time ,fuzzy d
uedate and alter -native machines were formulated .A genetic algorithm w as propod to maximize the average agreement in -dex for solving the fo rmulated job -shop problems .Reprentation bad on operation and machine was de -signed .Then crossover operation ,mutation operation and decoding operation for the designed reprenta -tion w ere explored .As illustrative numerical examples ,both 4×6and 6×6job -shop scheduling problems w ith fuzzy processing time and fuzzy duedate were considered .The results of the ex amples show that the procedure is not o nly available and efficient ,but also superio r to the method of M asatoshi .
Key words :job shop scheduling ;fuzzy processing time ;fuzzy duedate ;genetic algorithm
收稿日期:2004—02—03
基金项目：国家自然科学基金资助项目(59990470)
0 引言
调度模型中，一般假设有精确的加工时间和交货期，并且工件只有一条工艺路线。事实上，生产系统中存在很多不确定因素，如机器故障、工人劳动能力变化、原材料的差异、刀具磨损和环境参数变化等，人们只能根据统计规律得到加工时间的概率分布。顾客对交货期的要求也是一个变化范围，在某
一时刻交货顾客的满意度最高，偏离这一时刻满意度变小。这样，用模糊数表示加工时间和交货期更加符合实际。同时，生产车间往往有多台功能相近的机床，因而工件也就有多条工艺路线，至于采用哪条路线可在调度时选择。Nasr 等[1]的研究表明，考虑工件有多条工艺路线，能增加调度的灵活性，提高生产率。目前，虽有少数学者对单工艺路线的模糊调度问题进行了研究[2～5]，但他们把加工时间和交货期的分布函
数假设为特殊的函数，没有得到一种通用的算法。
本文研究了多工艺路线的模糊调度问题，建立了模糊调度的数学模型，提出了一种基于遗传算法的通用模糊调度算法，仿真结果证明了该方法的可行性和优越性。
1 加工时间、交货期及模糊操作
1.1 模糊加工时间
研究表明，加工时间大多为图1所示模糊数，记作 x =(α,m ,β)，隶属度函数为
μ(x )=
0 x ≤α
f (x ) α<x ≤m
g (x ) m <x ≤β0 x >β
(1)
函数f (x )和g (x )均为严格单调函数，故存在反函数f -1
(x )和g -1
(x )，容易证明，多个f -1(x )或g -1(x )之和仍存在反函数。1.2 模糊操作
设有两个模糊数 x 1和 x 2，分别用(α1,m 1,
图1 工序加工时间的模糊分布
β1)和(α2,m 2,β2)表示，根据模糊扩张原理，定义模糊数的加法和取大。
(1)模糊加法 模糊加法用来计算完工时间。若 x 1和 x 2之和为 x ，记为 x = x 1+ x 2，则
(α,m ,β)=(α1+α2,m 1+m 2,β1+β2)
(2)
μ(x )=
0 x ≤α
[
the gilroyf -11(γ)+f -12(γ)]-1
α<x ≤m [g -11(
γ)+g -12(γ)]-1
m <x ≤β0 x >β
(3)
模糊数加法如图2所示。
图2 模糊数加法
(2)模糊取大 取大操作(用“∨”表示)用于确定开工时间。若 x 1和 x 2取大结果为 x ，记为 x = x 1∨ x 2，则
(α,m ,β)=(α1∨α2,m 1∨m 2,β1∨β2)(
4)μ(x )=
saturday[f -
forecasts11(γ)∨f -12(
γ)]-1
[g -11(γ)∨g -12(γ)]-1
kattun>星期五英文 x ≤α
α<x ≤m
m <x ≤βx >β
(5)模糊反取大如图3所示。
图3 模糊数的取大
1.3 模糊交货期
顾客对交货期的要求往往是一个时间段，在该时间段内满意度为1，偏离该时间段，则满意度变小，如图4所示，记 d =(d 1,d 2,d 3,d 4)，其隶属度函数为
μ(x )=0 x ≤d 1f (x ) d 1<x ≤d 2
1 d 2<x ≤d 3
g (x ) d 3<x ≤d 40 d 4
<x
(6)
1.4 满意度指标
图4 模糊交货期
满意度为工件模糊完工时间隶属度函数和模糊交货期隶属度函数的交集所围成的图形面积与模糊完工时间隶属度函数形成的图形面积之比[2]，见图5。用公式表示如下:
AI =
area ( x ∩ d )
area ( x )
(7)
式中,area ()为取面积函数。
图5 满意度
2 调度模型
本文的调度问题可描述如下：给定一个工件
集合和机床集合，工件包含多道工序，工序的加工机床有多台，但只能选择其中的一台来加工，并且一台机床在同一时刻只能加工一道工序。工序的加工时间和工件交货期都是一个模糊数。调度就是把工序分配给机床上某个时间段，使平均客户满意度最大。
其数学模型如下：调度目标
y =max (
∑
n
i =1url是什么意思
AI i
n
)(8)
同一工件的两工序之间有
c ijk ≥
c i (j -1)k + t ijk r i + t ijk
j >1j =1
(9)
如工序o m n 先于o ij 在机床k 上加工，则
c ijk ≥ c mnk + t ijk
(10)如工序o ij 先于o m n 在机床上加工，则
c mn k ≥ c ijk + t mnk
(11)
式中,AI i 为工件i 的满意度;o ij 为工件i 的工序j ; c ijk 为o ij 在机床k 的模糊完工时间; t ijk 为o ij 在机床k 的模糊加工
时间;r i 为工件i 到达车间的时间;n 为工件的数量。
除了少数小规模调度问题存在多项式算法外，大量调度问题属于NP 难题，近年来发展起来的遗传算法对这类问题的求解具有较为显著的优
势[6,7]。本文以遗传算法为工具对上述调度问题进行了研究，得到了一种新的调度算法。
3 基于遗传算法的调度算法
3.1 调度问题编码
编码问题是设计遗传算法的首要和关键问题。遗传算法的编码必须考虑染色体的合法性、可行性、有效性及对问题解空间的完全性。本文设计的染色体编码见表1。染色体的基因由工件及机床组成。不同位置的工件解释为同一工件的不同工序。如第一次出现的“B”为工件B的工序0，第二次出现的“B”为工件B的工序1等。容易看出，基因的任意排列都对应可行调度，并且基因的所有排列对应整个解空间。
表1 染色体的基因型
工件B C A B C C A B A 机床022022202 3.2 种群初始化
随机产生N个染色体，并按照文献[2]的方法保证初始种群的相似度小于0.8。
3.3 染色体解码
按照下面方法把染色体解码为调度:
(1)令机床的模糊空闲时间m k=0,k为机床编号,k=1,2,…,m。
(2)在未调度工序中找到排在染色体字符串最前面的工序o ij，计算模糊完工时间。
c ijk=(c i(j-1)k∨m k)+t ijk j>1 (r i∨m k)+t ijk j=1
(3)调整机床的空闲时刻m k=c ijk。
(4)重复(2)、(3)，直到调度完所有工序。
(5)按式(7)计算满意度并求平均值。
快速学习3.4 适应度计算
为了克服种群进化过程中的未成熟收敛和随机漫游现象，提高遗传算法的优化搜索性能，适应度f的计算如下[8]:
f=ag+b
式中,g为染色体的平均满意度,a、b为系数。 a、b的设定要使g的平均值等于f平均值，且f
最大值等于g平均值的2倍。
3.5 遗传操作
针对本文的染色体，笔者设计了两种变异方法，即逆转基因变异和机器变异。逆转基因变异就是将随机选择的两个逆转点之间的基因逆向排序。机器变异就是将随机选择的基因中的机器替换为其他可用的任意一台机器。遗传操作过程见图6(图中P c为交叉概率,P m为变异概率)。可以看出，经过遗传操作后，新种群中染色体的适应度比原种群中的大。
图6 遗传操作过程
4 计算机仿真
4.1 算例验证
工件各工序的加工时间、机床及交货期见表2，其中加工时间和交货期都是三角模糊数。令种
表2 工件的加工信息单位:h 工件工序机床0机床1机床2机床3机床4机床5交货期
A 0(1,2,3)(2,3,4)(3,4,5)---
1-(2,3,4)-(1,2,3)(3,4,5)-(5,7,8) 2(0.5,1,2)(3,4,5)(4,5,6)---
0(2,3,4)-(4,5,6)-(1,2,3)-
B 1(3,4,5)(2,3,4)--(5,6,7)-(9,11,14) 2--(3,4,5)-(6,7,8)-(10,11,12) 0(4,5,6)(5,6,7)----
C 1-(3,4,5)-(2,3,4)(4,5,6)-(15,17,19) 2--(12,13,14)-(8,9,10)(11,12,13)
0(8,9,10)-(6,7,8)(8,9,10)--
D 1-(5,6,7)-(3,4,5)-(4,5,6)(10,14,18) 2(0.5,1,2)-(2,3,4)--(2,3,4)
群规模为50，交叉率为0.8，变异率为0.05。迭代20次得到最大平均满意度为0.75，对应的染色体见表3。精确时间的调度问题是模糊调度的特例，如果工序加工时间等于模糊数的“核”(即隶属度为1时的加工时间)，把表3的染色体解码就得到图7的调度甘特图。由文献[9]知，这是最优的调度甘特图。4.2 结果比较
笔者验算了文献[3]中6个工件6台机床的例子，结果得到最大平均满意度为0.83，优于文献[3]中给出的结果0.69，对应的染色体见表4。图8是令各工序加工时间等于模糊数的“核”，由表4染色体解码得到的调度甘特图。
表3 最佳调度对应的染色体
工件B D A C A B A
C B C
D D 机器
4
2
1
3
1
3
2
4
3
图8 加工时间隶属度为1时的调度甘特图
图7 加工时间隶属度为1时的调度度甘特图
表4 最佳调度对应的染色体
工件D E F B B A F D E D E B 机器554010544332工件C D F B A E D A A B D E 机器210542015321工件C B A F E A F C F C C C 机器会计人
5
4
4
1
3
2
4
comeacross3
3
1
5 结论
本文系统地研究多工艺路线的作业车间模糊调度问题，建立了模糊调度的数学模型，并以遗传算法为基础提出了一种全局优化的混合调度算法。该算法在染色体的编码、变异、交叉算子的设计上具有较高的效率，有效地防止了非法染色体的产生。仿真结果表明，该算法是可行的，有一定的优越性。本文主要针对作业车间调度问题，但该算法也可推广到其他类型的调度问题上。
参考文献:
[1] Nasr N ,Elsayed E A .Job Shop Scheduling with A l -ter native M achines .International Journal of P roduc -tion Rearch ,1990,28(9):1959～1609
[2] Sakaw a M asatoshi ,T etsuya M ori .An Efficient Ge -netic Algorithm for Job -shop Scheduling with Fuzzy Processing and Fuzzy Duedate .Computers &industri -al engineering ,1999,36:325～341
[3] T sujimura Y ,Gen M ,K ubota E .Solving Job -shop
Scheduling P roblem with Fuzzy P rocessing T ime Using Genetic Algo rithm .Journal of Japan Socie
ty fo r Fuzzy T heory and Systems ,1995,7(5):1073～1083[4] Ishii H ,T ada M .Sing le M achine Scheduling Problem
with Fuzzy Precedence Relatio n .European Journal of Operational Rearch ,1995,87:284～288
[5] 耿兆强，邹益仁.基于遗传算法的作业车间模糊调
度问题研究.计算机集成制造系统———CIM S ,2002,8(8):615～620
[6] Cheng R ,Gen M ,T sujimura Y .A tutorial Surv ey of
Job -shop Scheduling Problems Using G enetic A lgo -rithms ,part Ⅱ:Hybrid Genetic Search Strategies .Computers &I ndustrial Engineering ,1999,35:343～364
[7] Cheng R ,Gen M ,T sujimura Y .A tutorial Surv ey of
Job -shop Scheduling Problems Using G enetic A lgo -rithms ,Par t Ⅱ:Hybrid G enetic Search Strategies .Computers &I ndustrial Engineering ,1999,35:343～364
[8] 陈国良，王煦法，庄镇泉.遗传算法及其应用.北京:
人民邮电出版社,1996
[9] 潘全科.智能制造系统多目标车间调度研究:[博士
学位论文].南京：南京航空航天大学,2003
(编辑 郭 伟)
作者简介：潘全科，男,1971年生。聊城大学计算机学院副教授、
博士。主要研究方向为智能制造系统和生产自动化。发表论文10余篇。朱剑英，男,1937年生。南京航空航天大学机电学院教授、博士研究生导师。
