2001年8月系统工程理论与实践第8期 文章编号:100026788(2001)0820097205
用模糊调度系统求解动态Job Shop问题
万国华
(深圳大学管理学院,广东深圳518060)
摘要: 研究工件加权拖期总和最小化的动态Job Shop调度问题Λ提出了一个模糊调度系统,用以动
态地选取启发式调度规则以求解该问题Λ特别地,该系统具有从模糊规则和以前经验中学习的能力Λ
各种不同条件下的仿真实验表明该模糊调度系统是有效的Λ
关键词: 动态Job Shop调度;启发式调度规则;模糊系统
中图分类号: T P391.9 文献标识码: A α
U sing Fuzzy Schedu ling System fo r
So lving a D ynam ic Job Shop P rob lem
W AN Guo2hua
(D epartm en t of Info rm ati on and System sM anagem en t,Shenzhen U n iversity,Shenzhen518060,Ch ina)
Abstract: T h is paper concern s w ith the dynam ic j ob shop schedu ling p rob lem to
m in i m ize to tal w eigh ted tardiness is studied.A fuzzy system app roach is p ropo sed to
dynam ically gu ide the selecti on of dispatch ing ru les fo r differen t p rob lem in stances by
learn ing from fuzzy ru les and p revi ou s so lu ti on s.Several experi m en ts are designed and
conducted in differen t scenari o s to evaluate the effectiveness of the fuzzy schedu ling
system again st the traditi onal dispatch ing ru les.P reli m inary experi m en tal resu lts
indicate that the fuzzy schedu ling system is efficien t and effective.
Keywords: dynam ic j ob shop;dispatch ing ru le;fuzzy system
1 引言
生产调度的目的是合理地安排工件的加工时间以优化某一个或几个调度目标Λ在现代制造业中,生产调度已不仅是一个战术问题,而已经成为一个战略问题了[1]Λ然而,生产调度问题通常非常复杂,特别是在动态环境和带复杂调度目标时Λ由于该类问题一般是强N P2难的问题,因此解决此类问题的通用方法是使用启发式调度规则;然而单纯的启发式调度规则远不能令人满意[1,2]Λ为提高启发式调度的性能,人们使用了多种方法,例如遗传算法[3,4],神经网络[5],机器学习[2]等以动态地选取启发式调度规则Λ本文提出一个求解调度目标为最小化工件加权拖期总和的动态Job Shop问题的模糊系统,它集成了启发式调度规则和专家的调度知识来解决问题Λ模糊系统的优点在于它能综合利用以前的运行和仿真中得来的数值结果以及从经验和观察中得来的调度知识,并且易于实现[6]Λ
2 问题的描述和常用生产调度规则的讨论
2.1 问题的描述
在过去的十几年中,调度目标为最小化工件加权拖期总和的动态Job Shop调度问题引起了人们的广泛关注[1,7]Λ该问题可描述如下:n个工件,每个均由多个操作组成并随机地来到一个m个机器的车间等待
α
89系统工程理论与实践2001年8月
加工Ζ工件i(i=1,…,n)共有m i个加工次序已确定的操作,其加工时间是p ij,j=1,…,m iΖ对工件i,其拖后一个单位时间的惩罚是ΞiΖ本问题的目标是最小化如下定义的工件的加权拖期总和:
6n
Ξi(C i-d i)+
i=1
这里C i和d i分别是工件i的完工时间和交工时间,x+=m ax(0,x)Ζ
2.2 常用启发式调度规则的讨论
众所周知,调度目标为工件加权拖期总和的动态Job Shop调度问题是强N P2难的问题Λ其典型的求解方法是使用启发式调度规则[1]Λ这些规则可分为二类[7]:1)一遍规则和,2)多遍规则Λ所谓一遍规则指的是一次即可完成调度过程的规则Λ大多数规则均可归于此类,例如先到先服务FCFS(first com e first served),最早交工期优先EDD(earliest due date first),加权的最小加工时间优先W SPT(w eigh ted sho rtest p rocessing ti m e first),关键比例CR(critical rati o)[1,7]Λ所谓多遍规则指的是在调度的第一遍中先建立一个初始解,然后在随着时间对初始解进行不断的调整Λ那些迭代的规则如A TC(apparen t tardiness co st),COV ER T(co st over ti m e),瓶颈动力学BD(bo ttleneck dynam ics),邻域搜索法等均属此类Λ大多数启发式调度规则都广泛用于实际的j ob shop调度[1]Λ然而从本质上来说调度规则的目的是寻找较优解而非最优解,因而通常有很大的改进余地[1]Λ以下介绍一些常用的启发式调度规则,它们将用于模糊系统中求解我们的问题Λ
1)简单调度规则:
先到先服务FCFS(F irst Com e F irst Serve):先到达加工机器的工件先加工Λ
最早交工期优先EDD(Earliest D ue D ate):交工期最早的工件先加工Λ
加权的最小加工时间优先W SPT(W eigh ted Sho rtest P rocessing T i m e):加权的加工时间最小的工件先加工Λ
关键比例CR(C ritical R ati o):机器的空闲时间与操作的剩余加工时间之比值最小的操作先加工,直至该工件的交工期Λ
修正的操作交工期M OD(M odified Operati on D ue D ate):修正的操作交工期最早的工件先加工Λ剩余工作量最多优先MW KR(M o st W o rk R em ain ing):剩余的加工工作量最多的工件先加工Λ
2)复合调度规则:
复合调度规则是一遍规则组合而成,通常是多遍规则,它们包括:
W COV ER T(W eigh ted Co st OV ER T i m e):把W C T ij(t)值最大的操作ij先加工,这里W C T ij(t)=Ξi, p3ij[1.0-(d i-l ij-t)+ (k3l ij)],而l ij是估算的时间提前量(lead ti m e),t是调度的时刻,k是待选择的参数Λ
A TC(A pparen t T ardiness Co st):把W C T ij(t)值最大的操作ij先加工,这里A C T ij(t)=Ξi, p3ij exp[-U ij(t)],而U ij(t)=(d i-l ij-t)+ (k3p avg),p avg是所有工件的平均加工时间Λ
CR+SPT::该规则是CR和SPT的组合Λ它赋予每一个等待加工第j个操作的工件一个新的交工期d ij=m ax{t+CR ij(t),t+p ij},然后按新的交工期动态地调度交工期最早的操作Λ
S R PT+SPT:该规则是S R PT和SPT的组合Λ与CR+SPT类似,它赋予每一个等待加工第j个操作的工件一个新的交工期d ij=m ax{t+S R p t ij(t)3p ij,t+p ij}=m ax{t+(CR ij(t)-1)3p ij,t+p ij},然后按新的交工期动态地调度交工期最早的操作Λ
3)瓶颈动力学调度规则BD(Bo ttleneck D ynam ics)
BD是在文[1]中提出的,它非常类似于A TCΛ它把B D ij(t)值最大的操作ij先加工,这里:
B D ij(t)=Ξi3U ij(t) (6m j q=j R k(q)(t)3p iq)
而R k(q)(t)是机器k(q)在t时间的资源价格Ζ
关于瓶颈动力学规则的详细讨论,可参阅文献[1]Λ在本文的模糊系统中,将使用一些简单调度规则,
并将与一些复合调度规则和瓶颈动力学调度规则进行比较Λ
3 求解动态Job Shop 问题的模糊系统
如前所述,人们曾使用过神经网络,机器学习等方法来动态地选取调度规则以求解Job Shop 调度问题Λ这些方法的一个主要缺陷是难以同时利用数值结果和专家知识如IF 2TH EN 规则,而模糊调度系统却具有这样的特性[6]Λ以下将先讨论Job Shop 调度问题的一些基本特征,然后提出一个模糊调度系统用以动态地选取调度规则,以提高简单调度规则的性能Λ
3.1 动态Job Shop 问题的特征
如文献[2,5]及其它文献中的讨论,以下所述为Job Shop 调度问题中对调度规则的选取有重要作用的特征:?系统的平均利用率,它衡量车间中机器使用效率的指标;
?工件交工期的松紧程度,它衡量车间中所有工件的交工期紧迫还是松散Λ
?机器的相对负荷,是机器的平均利用率与系统的平均利用率之比;
?竞争因子,指的是瓶颈机器的平均数量;
?变化系数(C .V .),它是在特定机器上的操作加工时间的标准差与全部操作的平均加工时间的百分比Λ其它因数如机器和工件的数量对调度规则的选取则不大重要[2]Λ在我们的模糊系统中将利用上述特征来决定调度规则的选取Λ
3.2 动态Job Shop 问题的模糊系统求解
模糊调度系统的目的在于为特定的调度问题提供合适的调度规则以求解该问题Λ如图1所示,该系统有三个模块组成:
1)仿真结果模块:本模块存储典型的仿真结果和运行结果Λ所有这些结果均用于模糊系统的训练Λ2)模糊推理模块:本模块是整个系统的核心部分Λ在训练之后,它将用于在调度过程中动态地选取最好的启发式调度规则Λ
3)启发式调度规则库:本模块存储调度的专家知识Λ通常这些专家知识以模糊IF -TH EN 的形式表示Λ
3.3 模糊系统
所谓模糊系统,指的是直接利用模糊逻辑工作的系统Λ通常有三种典型的模糊逻辑系统,即纯模糊系统,T akagi 和Sugeno 的模糊系统以及带模糊器和模糊消除器的模糊系统[6]Λ其中带模糊器和模糊消除器的模糊系统基本结构如图2所示
Λ
图1
模糊调度系统的体系结构图2 带模糊器和模糊消除器的模糊系统
带模糊器和模糊消除器的模糊系统有许多良好的性质Λ第一,它适用于输入和输出为数值的系统Λ第二,它为利用模糊IF -TH EN 规则提供了一个框架Λ第三,模糊器和模糊消除器选择的自由使得模糊推理可以更有效地进行Λ第四,不同训练方法的选择有很大的灵活性Λ因此,模糊调度系统为有效选取模糊规则进行工件调度提供了一个有效的框架Λ
本文中的模糊调度系统的工作原理如下Ζ首先,通过仿真得出不同车间状况下最好的简单调度规则,用向量((x 1,…,x 5),y )表示Ζ此处(x 1,…,x 5)表示的是车间状况的五个特征及调度规则的编号Ζ然后,根据专家知识和对系统的观察,找出一些调度规则,例如:
规则1 IF 工件的交货期较松,TH EN 使用EDD 规则Λ
规则2 IF 工件的交货期较紧,TH EN 使用SPT 规则Λ
99第8期用模糊调度系统求解动态Job Shop 问题
规则3 IF机器的工作量比较均衡,TH EN使用M OD规则Λ
规则4 IF存在瓶颈机器,TH EN对该瓶颈机器使用M DD规则,对其它机器使用M OD规则Λ因为本系统中的模糊规则数量不太多,故采用最近邻域法训练比较合适[6]Λ其训练算法如下Λ?首先,采用中心模糊消除器,乘积规则和单子模糊器的模糊系统可用如下数学公式表示:
这里:N仿真结果的个数,x=(x1,…,x5),x l=(x1,…,x5)l,而y调度规则的编号Ζ
y=f(x1,…,x5)=6N
l=1
y l exp(- x-x l 2 Ρ2) 6N
l=1
exp(- x-x l 2 Ρ2)
?从第一个结果向量((x1,…,x5)1,x1)开始,在(x1,…,x5)1建立一个聚簇中心(x1,…,x5)10,并令A1(1)=y1,B1(1)=1Ζ选择一个聚簇半径rΖ
?对第k个向量((x1,…,x5)k,y k),k=2,3,…继续上述过程Ζ假设已有M个聚簇,其中心是(x1,…,x5)k’,k’=1,…,MΖ计算(x1,…,x5)k到这些中心的欧氏距离并找出最小的一个Ζ
?如果该最小距离比r大,则把(x1,…,x5)k作为一个新的聚簇Ζ否则把它归入距之距离最小的聚簇Ζ?该模糊到达系统在第k步时的数学表达式如下:
f(x1,…,x5)=6M
l=1
A l(k)exp(- x-x l 2 Ρ2) 6M
l=1
B l(k)exp(- x-x l 2 Ρ2)
如果没有用x=(x1,…,x5)k建立一个新的聚簇,则A lk(k)=A lk(k-1)+y k,B lk(k)=B lk(k-1)+ 1,这里l k是最近聚簇的数量;否则,M加1,A l(k)=A l(k-1),B l(k)=B l(k-1)
?在模糊系统中按如下方法加入模糊规则:
f(x)=Αf L(x)+(1-Α)f k(x)
这里f L(x)是用模糊IF2TH EN规则构造出的模糊系统[6],而Α∈[0,1]是加入新的模糊规则所用的权重Ζ在本模糊调度系统中,该权重设为0.4,亦即系统中数值仿真结果比模糊规则略为重要Ζ对于该算法的详细讨论,可参考文献[6]Ζ在训练之后,模糊调度系统即可用于动态实时的调度Job Shop系统了Λ
4 实验及仿真结果
4.1 仿真实验中的Job Shop模型
在本仿真实验中使用的Job Shop模型是一个典型的有八台机器的Job Shop(参见文献[8])Λ工件按Po isson过程到达并可即刻加工Λ每个工件的操作的数量是1-8之间的均匀分布,而工件的路径亦是等可能地到达未经过的机器Λ仿真中使用的车间有三类:1).在单一类型车间中,所有工件的加工操作均为15个,每个操作的加工时间均从均匀分布U[1,30]中随机产生Ζ2).在比例类型车间中,工件的操作个数s i (i=1,…,n)从均匀分布U[5,25]中随机产生,而每个操作的加工时间从均匀分布U[s i 3,5s i 3]随机产生(注意工件的每个操作的加工时间是相关的,或说是成比例的)Ζ3).在有无瓶颈的单一类型车间中,瓶颈机器共有三台,其速度最多比平均速度慢20%Ζ同时还有三台快速机器,其速度最多比平均速度快30%Ζ工件的拖期权重从均匀分布U[1,2s i]中随机产生Ζ车间的负荷由工件的到达率决定Ζ在仿真实验中,车间的负荷有三种,即:60%,80%和90%Ζ交货期均匀分布于0到最大完工时间,其平均值是工件平均的加工时间的6(或3)倍,用于表示相对松(或紧)的交货期Ζ
这些组合包括3种车间类型,2类交货期和3类车间利用率,产生出18不同的问题Ζ在实验中,每种问题有2000个工件等待加工Ζ
4.2 仿真结果及讨论
本系统的仿真用系统仿真语言S I M AN[9]并辅以C语言子程序完成Λ仿真的结果如图3和图4所示Λ图3所示为机器利用率对模糊调度系统(FSS)性能以及三类调度规则(BD,A TC和S R PT+SPT)性能在001系统工程理论与实践2001年8月
二种不同情况下(即无瓶颈车间和有瓶颈车间)的影响,而图4所示为工件交货期对模糊调度系统性能以及三类调度规则性能在二种不同情况下(即无瓶颈车间和有瓶颈车间)的影响
Λ
图3 车间利用率对FSS
和调度规则性能的影响
图4 交货期的松紧对FSS和调度规则性能的影响
从仿真结果可以看出:
?本模糊调度系统的性能远好于启发式调度规则或它们的组合Λ
?本模糊系统在车间的高利用率和交货期紧的条件下,性能尤其好于启发式调度规则或它们的组合,这是由于系统能够学习的缘故Λ
5 结束语
本文提出了一个求解最小化工件加权拖期总和的动态Job Shop问题的模糊调度系统,用以动态地选取启发式调度规则Λ描述了该调度问题的主要特征和系统从模糊规则和以前经验中学习的机理Λ各种不同条件下的仿真实验表明该模糊系统是有效的,它比简单的复合调度规则以及瓶颈动力学规则的性能都好Λ当然,进一步的研究可以在此模糊系统中加入更复杂、更有效的调度规则,也应该提取更多的模糊规则加入其中以进一步提高系统的性能Λ
参考文献:
[1] M o rton T E,Pen tico D W.H eu ristic Schedu ling System s[M].N ew Yo rk,N Y:John W iley and
Son s Inc.,1993.
[2] Shaw M J,Park S,R am an N.In telligen t schedu ling w ith m ach ine learn ing capab ilities:the
inducti on of schedu ling know ledge[J].IIE T ran sacti on s,1992,24(2):156-168.
[3] A ytug H,Koeh ler G J,Snow don J L.Genetic learn ing of dynam ic schedu ling w ith in a si m u lati on
environm en t[J].Compu ters and Operati on s R esearch,1994,21(8):909-925.
[4] Do rdo rf U,Pesch E.Evo lu ti on based learn ing in a j ob shop schedu ling environm en t[J].Compu ters
and Operati on s R esearch,1995,22(1):25-40.(下转第129页)
101
第8期用模糊调度系统求解动态Job Shop问题
遗传模糊算法在短期负荷预测中的应用 提出了一种基于模糊逻辑原理的负荷预测方法，使用遗传算法对系统参数进行训练。在以往的模糊逻辑系统建立过程中,其主要参数（如模糊推理规则和隶属函数等）需要依靠运行人员经验或专家知识来确定，而本文利用遗传算法，通过对样本数据的自学习过程来获取系统参数。在遗传算法中，将推理规则与隶属函数参数的确定结合在一起，从而确定系统参数的最优组合，由此建立起一个较合理的模糊负荷预测系统。仿真实验结果表明，该方法能够达到满意的预测精度，具有良好的实用前景。 关键词：短期负荷预测；模糊逻辑系统；遗传算法 APPLICATION OF GENETIC-FUZZY ALGORITHM FOR SHORT TERM LOAD FORECASTING OF POWER SYSTEM Xiong Hao ；Luo Ri-cheng (Electrical Engineering School ,Wuhan University, WuHan 430072, China) ABSTRACT: A novel approach based on fuzzy logic system (FLS) is introduce d to short term load forecasting (STLF).Traditional methods to choose membership functions and fuzzy control rules used to be done by means of integrating experien ce from experts in professional fields and technologic faculty. In this paper, howeve r, a genetic algorithm based approach is developed to optimize parameters of mem