随机故障下单机鲁棒调度算法的遗传编程方法_尹文君.pdf
ISSN 1000-0054CN 11-2223/N清华大学学报(自然科学版)J T singhua Univ(Sci&Tech),2005年 第 45 卷 第 1 期2005,Vol.45,No.121/3781-84随机故障下单机鲁棒调度算法的遗传编程方法尹文君,刘民,吴澄(清华大学 自动化系,北京 100084)收稿日期:2003-06-27基金项目:国家自然科学基金资助项目(60004010);国家“八六三”高技术项目(2001AA411020)作者简介:尹文君(1976-),男(汉),江苏,博士研究生。通讯联系人:刘民,副教授,E-mail:。摘要:研究了随机故障环境下具有预测能力的单机鲁棒调度方法。通过插入空闲时段的方法吸收随机故障的扰动,进而对带空闲时段的鲁棒调度启发式,采用基于双子树结构编码的遗传编程体系加以学习。实验表明:所进化的启发式算法的拖期性能明显优于现有启发式,并通过适量插入空闲时段保持了较好的预测性能。这些算法由自适应的组合排序规则和空闲时段计算程序有机构成,并可较好地移植到其他不确定环境中。因此,所提出的遗传编程方法是不确定调度环境下相当有效的机器学习方法。关键词:数学模拟;鲁棒调度;机器故障;空闲时段;遗传编程;机器学习;双子树中图分类号:O 242.1文献标识码:A文章编号:1000-0054(2005)01-0081-04Learning single-machine robust schedulingheuristics subject to stochastic breakdownsusing genetic programmingYINWenjun,LIUMin,WU Cheng(Department of Automation,Tsinghua University,Beijing 100084,China)Abstract:Stability is seldom considered in robust scheduling.T hispaper presents an analysis of the single-machine robust schedulingheuristics subject to stochastic breakdowns to minimize both themean tardiness and the predictability.Idle times were inserted toabsorb disruptions and a genetic programming(GP)system withbi-tree structured individuals was used tolearn the effectiveheuristics.T he results show that the evolved programs give goodtardiness performance with good predictability.The programsintegrate job sequencing with idle-time inserts and give satisfactoryresults even when applied to other environments.Hence the GPmethods are g ood machine learning paradigms for robust schedulingproblems in uncertain environments.Key words:mathematicalsimulation;robustscheduling;breakdown;idle time;genetic programming;machinelearning;bitree鲁棒调度一般以维持高加工性能为目的,而忽略了实际生产对稳定性的需求(如原料准备或下游工序加工等)1 4。对故障环境下的单机鲁棒调度问题,本文采用插入空闲时段的方法以维护稳定性。鉴于带空闲时段的鲁棒调度(robust scheduling withidle time,IRS)算法很难用一般解析法获得,因而通 过 双 子 树 编 码 的 遗 传 编 程 系 统(geneticprogramming,GP)5,6学习不确定环境下的 IRS 初始计划生成方法。所进化的程序将工件排序和空闲时段插入过程有效融合,显示了相当好的拖期性能和预测能力。同时,分析了进化程序的构成特点。1带空闲时段的鲁棒调度描述设调度问题 q 任务总数为 N,已知工件 i(1iN)的投料时间ri、加工时间 pi、交货期di。采用某算法h 制定的初始计划序列为 Sp(q,h)=P1P2PN,其中工件 i 的计划开始时间、完工时间和所插入空闲时段分别为 bpi、cpi和 Ii,则bp Pi=maxrPi,cp Pi-1+IPi,(1)cp Pi=bpPi+pPi.(2)显然,算法 h 制定 Sp(q,h)时要同时确定工件加工顺序和各工件前所插入的空闲时段。加工时按 Sp(q,h)所确定的先后顺序尽早投产。若机台发生随机故障(故障频率和修复周期可由维修记录等事先估计),则采用右移法进行重调度 2,被故障中断的工件在机器修复后继续加工。设Sr=(bri,cri),1iN 为实际作业结果,bri和 cri为工件 i 的实际开工和完工时间。工件i(1iN)的拖后时间定义为:Ti(q,h)=maxcpi,cri-di,0.(3)问题q 的平均拖后时间和稳定度定义为:Tavg(q,h)=1NNi=1Ti(q,h),(4)Davg(q,h)=1NNi=1cpi-cri.(5)对由同类特征问题组成的集合 Q=q,算法 h作用下的性能分别为:TQ(h)=1QqQTavg(q,h),(6)DQ(h)=1QqQDavg(q,h).(7)实际生产一般根据初始计划 Sp(q,h)估计作业性能并为其他部门提供决策参考,又以实际结果 Sr进行最终核算,因而(3)和(4)的拖期指标更贴近实际。式(5)衡量了 Sp(q,h)和 Sr间的差异,反映了算法 h 对故障环境的预测能力,其值越小,预测能力越强,生产线越稳定。2遗传编程遗传编程 GP 借鉴自动编程原理和进化思想,能有效学习特定问题中的计算程序 5,6。由于不同环境下带空闲时段的 IRS 初始计划生成算法较难统一获得,可将其视为计算程序,采用 GP 对各环境下的优化程序加以学习。2.1双子树结构表达考虑到 IRS 计划过程的特点,采用双子树的结构形式表示 prog=ptree,Itree。其中,子树 ptree和 Itree分别对应于时刻 t 工件 i的优先级计算子程序 pri(i,t)和工件加工前所插入的空闲时段计算子程序 Itime(i,t)。每个子树采用深度优先、自左向右的顺序转化为相应的函数输出形式(如图 1)。图 1双子树结构表达示例给定问题 q 和个体 prog,采用 pri(i,t)每次寻找优先级最高的工件,并根据 Itime(i,t)计算该工件前所插入的空闲时段,由式(1)、(2)确定工件计划并更新当前时刻,重复处理生成初始计划 Sp(q,prog)。故障发生时对 Sp(q,prog)重调度而获得实际结果Sr。进而可由式(4)(7)计算环境 Q=q 下 prog的作用性能。树结构使个体的大小和形状灵活可变;双子树则将 IRS 工件排序和插入空闲时段的功能有机融合,两个子树通过 GP 的进化机制在算法空间上协同演化。因而,基于 GP 的学习系统有可能挖掘出高性能的IRS 启发式。2.2输入集和函数集选择下列参数构成输入集:工件数N;工件 i(1iN)的投料时间 ri、加工时间 pi和交货期 di;当前时刻 t;当前未加工任务数 Nr;当前未加工任务的加工时间总和 RPSum与交货期总和 RDSum;故障的平均发生周期 BP和平均修复周期 MP。函数集由简单二元函数组成:加减乘除运算(+、-、%),其中,%为保护性除法,即分母为0时为 1;最小值和最大值函数(min、max);D(x,y)函数,x y 时为 1,否则为 0。2.3GP 配置适应度计算:根据拖期性能(式 6)计算,采用随机采样机制 6以平衡计算效率和学习效果,随机采样子环境规模为学习环境规模的 1/5;选择:采用锦标赛选择,比赛规模为 7;交叉:相同功能的子树间进行树交叉 6,交叉率 0.9;变异:各子树分别进行树变异,变异概率 0.5。种群规模 50,最大迭代数80,子树最大节点数 80。3实验分析每类特征环境分别由学习集 Q 和测试集 T 组成。GP 在 Q 中学习,所进化的个体在 T 中测试和比较。Q 和 T 分别由随机问题按其特征组合而成。问题实例生成方法参考文 2,其中,交货期 di=ri+C pi,CU a,b,(a,b)分别取 D1(0,1,2)、D2(1,3)和 D3(3,5);故障间隔服从均值为 HE(pi)的指数分布,H取三类值 B1(10)、B2(5)和B3(2);维 修 周 期 服 从 均 匀 分 布 B1E(pi),B2E(pi),(B1,B2)分别取 3 组值 M1(0.1,0.5)、M2(0.5,1.5)和 M3(1,3)。对每类故障特征(Bi,Mj)(1i,j 3)和交货期特征 Dd(1d3),分别随机生成 360 个问题实例构成各自的学习集与测试集。当 i 或 j 增大时,机器故障对环境(Bi,Mj)的影响增大;当 d 增大时,环境 Dd所受交货期约束则逐渐减弱。82清 华 大 学 学 报(自 然 科 学 版)2005,45(1)3.1基本性能分析设进化个体和启发式 AT C(2)+OSMH(简称A2O)2在测试环境中的平均拖期量(式 6)为 TGP和TA2O,预测指标(式 7)为 DGP和 DA2O。设$rT=(TGP/TA2O-1)和$rD=(DGP/DA2O-1)。上述因子为负时 GP 个体对应性能优于 A2O,值越小改进越大。GP 个体的性能如表 1 所示。表 1GP进化个体性能类别TGP$rT/%DGP$rD/%B1,M181.4-48.72.3-92.3B1,M284.8-63.69.4-90.2B1,M397.1-73.219.1-90.9B2,M181.5-41.65.6-37.6B2,M298.9-43.719.5-29.2B2,M3119.0-47.939.3-28.2B3,M190.5-36.613.4-9.3B3,M2115.1-34.938.6-7.5B3,M3158.4-31.183.3-6.4D1121.2-46.828.2-54.7D2104.4-49.526.4-54.2D387.3-52.526.2-56.9从表 1 可见,个体的拖期性能大为改善($rT-31.1%),表明 GP 有很强的学习能力;随着故障干扰的增强(比较(B1,M1)和(B1,M3)情形),$rT大多逐渐变小,表明 GP 个体对复杂环境的处理能力相对 A2O 而言逐渐提高,这得益于 GP 基于动态结构的自适应搜索能力。另外,尽管以拖期性能计算适应度,进化个体仍显示了较好的预测能力($rD-6.4%),而且当交货期约束增强时预测指标仍一直稳定在较高的水平。这表明 GP 个体能预测不确定环境特征并适量插入空闲时段从而维持稳定性。3.2可移植性设子环境 Ei中进化的启发式为 prog(i),它在Ej中的测试结果为 Tj(i)。定义$T(i,j)=(Tj(i)/Tj(j)-1).它反映了在环境 Ei中进化的个体应用于其他环境时的性能可接受度。机器故障类环境对应的$T(i,j)见表 2。可以看到,进化程序应用于其他环境时依然显示了很好的测试性能($T(i,j)1.6%),因而其对环境具有较好的鲁棒适应性。对GP 而言,可利用现有子环境下的进化个体改善新环境中的种群组成;也可设计基于各子环境的协同种群以提高GP 效果。从应用角度而言,若环境特征(如故障分布)发生变化,可先采用原有算法制定计划,同时对新环境离线学习,以保证计划调度的平滑过渡。表 2GP 环境鲁棒性因子$T(i,j)%B1,M1B1,M2B1,M3B2,M1B2,M2B2,M3B3,M1B3,M2B3,M3B1,M10.0-1.2-1.5-1.3-1.10.9-1.1-1.1-1.2B1,M20.30.0-0.3-0.01.51.30.10.10.1B1,M30.30.10.00.10.21.10.20.20.2B2,M11.60.2-0.20.00.11.50.10.10.1B2,M2-1.2-1.4-1.4-1.30.0-1.2-1.3-1.3-1.3B2,M30.20.20.30.20.20.00.20.20.2B3,M10.60.1-0.5-0.3-0.3-0.30.0-0.2-0.2B3,M2-0.4-0.10.10.01.3-0.3-0.00.00.0B3,M3-0.5-0.20.20.0-0.1-0.50.0-0.00.03.3进化程序构成特点进化程序的构成特点对 IRS 算法设计和应用具有指导意义。以环境(B1,M3)和(B2,M1)为例,进化个体的约简形式分别为式(8)和式(9):prog(B1,M3)=max ri+MP,2MPpi(MP-ri)-pi,piD(RDSum,max(di,MP)+BP,(8)prog(B2,M1)=1-2(N-1)Nrpi-2di,min(di,Nr,MP-min(di,Nr)-1).(9)式(8)中,工时较小或到达较晚的工件优先级较高(类似 SPT 和 FILO 规则的组合);式(9)中的优先级函数则可理解为 SPT 和 EDD 规则的组合,而且 SPT 的组合权重随着剩余任务数的减少而增强。式(8)中,空闲时段和工件工时成正比,和故障周期83尹文君,等:随机故障下单机鲁棒调度算法的遗传编程方法近似成反比,交货期大的工件空闲时段也长;式(9)中工件交货期较小或维修平均时间较短时,空闲时段也较短。4结论维护生产稳定性是与鲁棒调度相结合的新思路,采用空闲时段可以有效吸收机器故障的干扰。基于双子树编码的 GP 系统能自动挖掘到高性能的IRS 综合求解算法,这些算法对环境特征具有一定的可移植性,并为实际调度提供了有益启示。参考文献(References)1McKay K N,Buzacott J A,Safayeni F R.T he SchedulersKnowledg eofUncertainty M .Amsterdam,North-Holland:Elsevier,1989.171189.2ODonovanR,UzsoyR,McKAYKN.Predictablescheduling of a single machine with breakdowns and sensitivejobs J.International Journal ofProduction Research,1999,37:42174233.3Wu S D,Storer R H,Chang P C.One machine reschedulingheuristics with efficiency and stability as criteria J.Comp utOp s Res,1993,20:114.4Federgruen A,Mosheiov G.Single machine schedulingproblems with general breakdowns,earliness and tardinesscosts J.Op erations Research,1997,45(1):6671.5Koza J R.Genetic Programming M.Cambridge,MA:M IT Press,1992.6BanzhafW,NordinP,KellerRE,etal.GeneticProgramming M .San Francisco,CA:M organ Kauffman,1998.(上接第 51页)实验 1和实验 2可得出,由Rdx(m)=1mmi=1x(i)xT(i)的 K-L 变换是完全可以正确估计到 DS 信号的 PN码序列的,而且可以在较低的信噪比条件下实现估计。这里在PN 码长N=50bit 和 N=500bit,采样率 Sa=8 bit/chip 时,可以较为容易地作到 Gsnr=-20.0dB 的输入信噪比容限,此时相关矩阵的累加平均作用尤显突出。由图 6、7还可以看出,在信噪比较低时,估计 PN 码序列所需要数据组数的均值和标准差在 PN 码较长时会变得更小。4结论在通常情况下,已确知 PN 码的主动解扩可作到信噪比容限为-20.0dB-30.0dB,文 1 曾用带约束的 Hebbian 规则对 PN 码估计作到了接近-10.0dB 的信噪比容限,而本文用相关矩阵累加平均和 K-L 变换方法对 PN 码序列进行估计时可以较为容易地作到 Gsnr=-20.0dB 的信噪比容限,而且在 PN 码较长时估计性能会更好。该方法能较好地解决 DS 通信(尤其是 PN 码较短的民用通信和军用战术通信)的 PN 码序列估计问题,进一步为DS 通信的盲解扩、管理、侦察和干扰,以及 DS-CDMA 通信的侦察和盲多用户检测等奠定了基础。参考文献(References)1Dominique F,Reed J H.Simple PN code sequence estimationand synchronization technique using the constrained Hebbianrule J.Electronics Letters,1997,33(1):3738.2张天骐,周正中.直扩信号伪码周期的谱检测 J.电波科学学报,2001,16(4):518521.ZHANG T ianqi,ZHOU Zhengzhong.A new spectral methodof periodic detection of PN sequence in lower DS/SS signals J.Chinese J ournal of Radio Science,2001,16(4):518521.(in Chinese)3张天骐,周正中.直扩信号的普检测和神经网络估计 J.系统工程与电子技术,2001,23(12):1215.ZHANGT ianqi,ZHOUZhengzhong.DetectionandEstimation of DS/SS Signals by Spectra Analysis and N euralNetworks J.Sy stems Engineering and Electronics,2001,23(12):1215.(in Chinese)4French C A,Gardener W A.Spread-spectrum despreadingwithout the code J.IEEE T rans Communications,1986,34(4):404407.5Dixon R C.Spread Spectrum Systems(second edition)M.New York:John Wiley&Sons Inc,1984.6Anderson T W.Asymptotic theory for principal componentanalysis J.A nn Math Statist,1963,35:12961303.84清 华 大 学 学 报(自 然 科 学 版)2005,45(1)
