具有学习效果的两机流水车间调度启发式算法研究

第31卷　第5期2007年10月武汉理工大学学报(交通科学与工程版)JournalofWuhanUniversityofTechnology(TransportationScience&Engineering)Vol.31　No.5Oct.2007

具有学习效果的两机流水车间调度启发式算法研究*

收稿日期:2007-04-24 黄敏镁:女,28岁,博士生,讲师,主要研究领域为预测、决策与信息系统 *国家自然科学基金项目(批准号:60574070;70271033)资助

黄敏镁1)　罗荣桂2)　袁际军3)(华南师范大学公共管理学院1)　广州　510006)(武汉理工大学管理学院2)　武汉　430070)　(湖南大学工商管理学院3)　长沙　410082)

摘要:以最小化时间表长为目标函数,对具有学习效果的两机流水车间调度问题进行研究.由于工序加工时间引入了学习效果,传统的Johnson法则和NEH启发式算法不再适用.针对该问题的NP-hard特性,提出了JNEH和MNEH两种求解问题的多项式启发式算法.计算机数据实验证明了新的启发式算法求解问题的可行性和有效性;表明了JNEH启发式算法和MNEH启发式算法对小规模问题求解的精度更高、稳定性更好;同时证明MNEH启发式算法对求解大规模问题具有比传统算法更好的寻优性能和鲁棒性.关键词:流水车间;学习效果;启发式算法;最小化时间表长中图法分类号:O224;TP391.9

0　引 言近年来一些学者展开了对生产调度领域中的学习效果研究.Biskup对具有学习效果的单机调度研究揭开了对具有学习效果的调度问题研究的序幕[1].随后Mosheiov和Sidney等进一步对学习效果独立于作业和学习效果依赖于作业的单机调度问题和并行机调度问题进行了研究,并提出求解学习效果依赖于作业的单机调度问题的和并行机调度问题的匈牙利法[2-5].传统流水车间调度模型将作业的工序加工时间作为问题的固定且已知的参数,与工序在生产顺序中的重复操作次数(或在加工顺序中所处的位置)相对独立,该类车间的调度问题相对简单,不必考虑工序加工时间的变化对加工任务完成时间的影响[6-7].实践中,如何根据变化的工序加工时间安排不同车型汽车的加工顺序,达到流水车间生产效率的最大化,成为亟待解决的问题.本文将该类问题称为具有学习效果的流水车间调度问题.1　问题描述问题所在的流水车间由m台机器按照n个作业的加工顺序进行布置.假设作业经过每台机器的顺序相同,且每台机器上的作业排序也相同,即为排列排序(permutationscheduling)问题.在第i台机器上加工第j个作业的工序记为:(i,j),i=1,2,…,m;j=1,2,…,n.假设每个作业能在时刻t=0开始加工,工序一旦开始加工便不能中断,即不可中断问题.r表示作业在加工顺序中所处的位置,即工序的重复次数,r=1,2,…,n.pij表示不考虑学习效果的情况下工序(i,j)的正常加工时间.假设工序加工时间的递减规律符合Wright

学习曲线,则位于位置r的工序的加工时间记为:pijr,pijr=pijr󰀁且pij1=pij.式中:󰀁为学习系数,󰀁=lgl/lg2,l为学习率.给定一个调度,cij为工序

(i,j)的完工时间,求解的目标是确定作业排序,最小化调度的时间表长Cmax,由式(1)求得.Cmax=maxj{cmj}ci0=c0j=0,cij=max{ci,j-1,ci-1,j}+pijri=1,2,…,m,j=1,2,…,n,r=1,2,…,n(1) 用LE表示学习效果,则以最小化调度时间表长为目标函数的具有学习效果的流水车间调度问题记为:Fm/LE/Cmax.m=2时F2/LE/Cmax为最小化时间表长的具有学习效果的两机流水车间调度问题.当󰀁=0时,Fm/LE/Cmax简化为传统的流水车间调度问题Fm//Cmax,Garey,JohnsonandSethi已经证明该问题是NP-hard问题[8].因此Fm/LE/Cmax问题具有NP-hard特性.2　求解F2/LE/Cmax的启发式算法对学习效果独立于作业的单机调度问题的研究中Mosheiov证明了最小化时间表长的最优调度可以按照SPT规则得到.MosheiovandSidney证明学习效果独立于作业和学习效果依赖于作业的单机调度问题可以构造为指派问题进行求解并能以复杂性为O(n3)的匈牙利法得到最优解.但是用SPT和匈牙利法均无法对F2/LE/Cmax进行求解.2.1　现有启发式算法2.1.1　Johnson法则　已经证明Johnson法则能求得F2//Cmax问题的最优解,其复杂性为O(nlogn).但是通过下面一个简单的例子可证明Johnson法则不能求得F2/LE/Cmax的最优调度.例1　已知:n=4,m=2,工序的正常加工时间pij(i=1,2,j=1,…,4)由加工时间矩阵表示为P=448151420,本文采用的加工时间为标准化单位时间;采用Wright学习曲线拟合车间中加工时间的变化规律,且学习率为80%,即󰀁=-0.322,则根据pijr=pijr󰀁得到作业所在加工顺序中不同位置的加工时间如表1所列.表1　例1中具有学习效果的工序加工时间j　r=1 r=2 r=3 r=4　i=1i=2i=1i=2i=1i=2i=1i=21453.24.02.83.52.63.22413.20.82.80.72.60.63846.43.25.62.85.12.641200.816.00.714.00.612.8 不考虑学习效果的情况下由Johnson法则求得调度的最优排序为(4,1,3,2),按照此排序考虑学习效果,根据式(1)得到该问题求解的时间表长为28.4,甘特图如图1所示.但通过全枚举方法求得问题的最优作业加工顺序应该是(1,2,4,3),Cmax为26.4,如图2所示.可知Johnson法则无法求得F2/LE/Cmax的最优排序.

图1　Johnson法则求得的解图2　问题的最优解2.1.2　NEH启发式算法　Nawaz,Enscoreand

Ham提出的NEH启发式算法是迄今为止求解静态Fm//Cmax问题的最优启发式算法,其复杂性为O(n2m).采用NEH算法对F2/LE/Cmax进行求解时,用式(1)分别计算求解过程中产生的部分排序的时间表长,其他步骤不变.2.2　求解F2/LE/Cmax的改进启发式算法2.2.1　JNEH启发式算法　本文结合Johnson法则和NEH启发式算法构造了求解F2/LE/Cmax

问题的JNEH启发式算法.步骤如下.

步骤1　置k=1;不考虑学习效果,将n个作业按照Johnson法则进行排序得到初始解O;取O中位于第1位的作业,作为当前解S;将剩下的(n-1)个作业按O中的顺序保留在R中.步骤2　更新k=k+1.步骤3　取序列R中的第k个位置上的作业,将其插入S序列的k个位置中,根据式(1)分别计算k种排序下的Cmax,找出Cmax最小的排序,作为候选解C;置S:=C;将第k个作业从R中移去.步骤4　若R=󰀁或k=n,转步骤5;否则,转步骤2.步骤5　序列S为问题的近似最优解.例2　根据JNEH启发式算法求得例1问题的最优解为(1,2,4,3),调度的时间表长为26.4.2.2.2　MNEH启发式算法　不考虑学习效果时NEH启发式算法赋予作业总正常加工时间最大的工序优先加工的权利.从学习曲线的效果可知:当总正常加工时间越大的作业安排在越后面加工时,其实际加工时间越短.本文基于学习效果的思想产生初始解,并采用NEH的最优化部分调度的

・932・武汉理工大学学报(交通科学与工程版)2007年　第31卷思想改进初始解,构造了改进NEH启发式算法(MNEH).步骤1　置k=1;不考虑学习效果,计算每个作业的正常加工时间之和∑2i=1pij,j=1,…,n,将n个作业按∑2i=1pij递增顺序排列,得到初始解O;取O中的第1个作业,作为当前解S;将剩下的(n-1)个作业按O中的顺序保留在R中.步骤2　更新k=k+1.步骤3　取序列R中的第k个作业,将其插入排序S的k个位置中得到k种部分调度解,按式(1)计算k种排序的Cmax,找出最小者作为候选解C;置S:=C;将第k个作业从R中移去.步骤4　若R=󰀁或k=n,转步骤5;否则,转步骤2.步骤5　排序S为近似最优解.例3　采用MNEH算法也能求得例1问题的最优解,即作业最优加工顺序(1,2,4,3),时间表长为26.4.2.2.3　算法复杂性分析　求解F2/LE/Cmax问题的JNEH算法的复杂性为O(n2m).从上文可知步骤3决定了算法的复杂性,该步骤要分别计算k个部分排序的总完工时间,且k个作业m台机器的部分排序的总完工时间的计算复杂性为O(km),因此步骤3的复杂性为O(k2m),即JNEH算法的复杂性为O(n2m).同理,MNEH启发式算法的复杂性也为O(n2m).3　计算机数据实验为对求解F2/LE/Cmax问题的启发式算法进行性能分析,本文设计了2个实验.第一为小规模实验:由m=2,n=3和4,80%,85%及90%的Wright学习曲线,即󰀁=-0.3219,-0.2345和-0.1520,组成6组实验,每组实验包括100个问题,共600个小规模实验问题.第二为大规模实验:由m=2,n=5,10,15,20,25,30,35,40,45和50,󰀁=-0.3219,-0.2345和-0.1520,组成30组实验,每组实验包括100个问题,共3000个大规模实验问题.工序加工时间通过以下方法产生:令pij1为工序(i,j)排在加工顺序中的第1位时的正常加工时间,由伪随机数发生器在均匀分布的区间[1,99]中随机产生,工序加工时间根据作业在加工顺序中所处不同位置而变化的函数表示为:pijr=pijr󰀁.选取3个指标对算法进行衡量:(1)算法求得100个问题的近似最优解与该问题最优解的总偏差(TRPD),TRPD=∑100i=1(heuristici-besti)/besti.式中:heuristici为

算法求得第i个实验问题的近似最优解,besti为3种算法中求得第i个问题的相对最优解,反映了算法求解的质量;(2)算法达到最优解的次数(No.BS),反映了算法的鲁棒性;(3)算法求解问题的平均计算时间,反映了算法求解的速度.小规模实验中问题的最优解由全玫举方法求得,大规模实验中问题的最优解由各算法求得的最好的近似最优解表示.所有的算法用Matlab编程,在In-telCeleron1.80GHz计算机上实现.小规模实验的运行结果显示:本文提出的JNEH和MNEH启发式算法求得解相对最优解的总偏离指标(TRPD)分别平均为0.2048和0.2207,小于Johnson法则和NEH算法,具有较高的求解质量;JNEH和MNEH算法在600个算例中求得最优解的次数分别为518次和491次,多于Johnson法则(254次)和NEH算法(442次).但是在算法求解的速度方面Johnson法则快于NEH算法、JNEH和MNEH启发式算法,说明后3种算法的复杂性相同(为O(n2m))且较Johnson法则高.同时随着󰀁值的增大,工序加工时间缩短越慢,Johnson法则和NEH算法求解的TRPD指标值减少、精度增强,说明已有算法求解性能受学习率的影响较大,性能不稳定;而JNEH和MNEH算法求解问题的效率受学习率的影响相对较小,具有较强的鲁棒性.大规模实验结果显示:从TRPD和No.BS两项指标看,MNEH算法求解的质量明显优于其他3种算法,所得解与最优解的总偏差仅为0.2856,在3000个算例中约70%达到最优解,说明MNEH算法具有较高的求解精度和较优的寻优能力.从这两项性能指标看,4种算法的性能排序为:MNEH算法>NEH算法>JNEH算法>Johnson法则.从TRPD指标看(如图3所示),MNEH算法的TRPD指标值曲线平稳,说明MNEH算法能排除的影响,求解的稳定性比其他3种算法更强.实验结果也表明随着问题规模的扩大和难度增加,除了Johnson算法以外的3种算法的求解时间显著增加.