一种基于q学习的flow shop问题调度算法研究-李国昊.pdf

《一种基于q学习的flow shop问题调度算法研究-李国昊.pdf》由会员分享，可在线阅读，更多相关《一种基于q学习的flow shop问题调度算法研究-李国昊.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第21卷第5期2016年】o月工业工程与管理Industrial Engineering and ManagementV0121 No5Oct2016文章编号：10075429(2016)05002305一种基于Q学习的Flow shop问题调度算法研究李国昊1，李文超2(1江苏大学管理学院，江苏镇江212013 52江苏大学汽车与交通工程学院，江苏镇江212013)摘要：两台机器以上的Flow shop调度问题是一个强NP难的问题，目前为止尚未出现求解该类问题的有效算法。本文结合针此类问题的邻域操作特征，基于强化学习思想提出一种具备学习能力的调度算法。算法以Q学习作为4)1I练方法，通过持续

2、的离线训练学习该类问题寻优搜索知识，从而提高其调度寻优能力。算法采用高斯核函数支持向量机对Q函数进行拟合，以此克服在Q学习过程中遇到状态过多难题。数值仿真结果显示所提算法对Flow shop问题具有很好调度寻优能力。关键词：调度；Flow shop；Q学习；支持向量机中图分类号：C935 文献标识码：AA Scheduling Algorithm Based on Q-Learning for Flow Shop ProblemLI GUOha01。LI Wen-cha02(1School of Management，Jiangsu University，ZheNiang 212013，Chi

3、na；2School of Automobile and Traffic Engineering，Jiangsu University，Zhenjiang 212013，China)Abstract：The flow shop problem with more than two machines is a strong NP difficultproblem，and there is yet no valid scheduling algorithm for itA scheduling algorithm withlearning capacity is proposed on the b

4、asis of reinforcement learning by the use of its neighboroperation featuresBy using Q-learning as training method，the algorithm can obtain theknowledge of optimization for this kind problem to increase its searching ability in optimizationprocessThe approximation of Q function is realized by the uti

5、lity of the support vector machine(SVM)with a Gauss kernel function tO solve the problem of overmuch state during the Q-learning processThe results of numerical simulation show that the proposed algorithm possessesexcellent performance on scheduling and optimizationKey words：scheduling；flow shop；Q l

6、earning；support vector machine引言生产调度问题一直是管理科学领域以及制造自动化领域内的热点研究问题，对于该问题研究极具现实意义，对于提高制造企业的生产效率起着关键作用。Flow shop问题是生产调度领域内的一个经典问题，该问题自被提出以来一直深受诸多研究者关注。对于该问题研究早期多集中于精确算法，如分支定界法卜3I，这些方法对于小规模问题比较有效，收稿日期：20160424；修回El期：20160531基金项目：江苏省社会科学基金资助项目(14GLB008)；江苏省高校自然科学研究资助项目(13KJB460005)作者简介：李国吴(1975一)，山东平度人，副教

7、授，博士，主要研究方向为，Email：guohaolee126corn。一23万方数据第21卷 李国昊，等：种基于Q学习的Flow shop问题调度算法研究但对于大规模问题则非常耗费计算时间。自从1976年该问题被证明为强NP难后4，对于该问题研究大多集中于以寻找近优解为目标的智能启发式算法。如Ahmadizar所提蚁群搜索算法51；Li和Yin设计带变异策略的人工蚁群算法61；Li等为混合Flow shop问题设计了一种遗传算法73；Pan等为有限缓冲区的Flow shop问题设计了一种混沌协调搜索算法。上述算法对于大规模问题展现良好搜索性能，能够在较短时间内获得问题的最优解或近优解，但由于

8、算法结构是固定的，其搜索|生能得不到改善。鉴于上述问题，近来有一些研究者提出了有学习能力的智能搜索算法，其主要特征是通过离线学习训练获得问题特征及搜索规律，从而提高算法搜索性能。如“和Yin提出一种具备学习能力的差分进化算法91；Xie等提出一种基于教学原则的具备可变邻域的文化算法1 0I。研究者发现强化学习(Reinforcement learning)对于调度问题显示了较好学习效果，已被用于该领域研究。如Li等针对命令决策系统提出了一种命令调度算法11I，该算法以Q学习为基础。因为Flow-shop的解的数目随着问题规模变大而迅速增加，这样使Q学习所属的状态空间相应急剧增加，因此传统Q学习

9、方法难以适用于该问题。对于这一问题，我们通过提取问题的关键参数来代表系统的状态特征，通过具高斯核函数支持向量机对Q函数进行拟合，从而避免Q函数学习过程中遇到的状态过多问题。本文结构如下：第1部分为Flow shop问题模型，第2部分为算法理论根据及算法实现过程，第3部分为算法数值仿真结果的分析与比较，第4部分给出我们的结论及评价。2 Flow shop问题模型作为一个经典调度问题，Flow shop由m台机器和以个工件组成。要求对行个工件进行调度，使得某些性能指标如任务最大完工周期(make-span)达到最优。工件在机器上加工时，需满足：(1)工件按相同次序通过台机器；(2)每台机器工件加工

10、次序相同；(3)各道工序加工时间是确定的；(4)每台机器同时只能加工一个工件；(5)每个工件同时只能由一台机器加工。该问题一个可行调度用排列03一(1)，(i)，(孢)表示，(i)(i一1，2)为排在第i个一24一位置上待加工的工件。以()表示调度所对应的make-span，II表示可行调度方案的集合，则最优调度方案为。(CO。)一min(Cr。() (1)以夕j，表示工件(歹)在第i台机器上加工时间，则所有工件在所有机器上的加工时间用一mX咒矩阵P()表示，即P(叫)一(户训)。，P州)表示该矩阵的第i行第J列元素。3算法理论依据及实证本文所提算法涉及到强化学习中Q学习和支持向量机的理论，因

11、此在本部分先对其进行简单介绍，然后介绍算法实现步骤。31 强化学习强化学习作为机器学习的一种方法，目前已被应用于诸如控制系统、调度管理等多个领域。Q学习是强化学习的一种重要方法，其主要理论如下：在当前状态S，如果采取策略丌，则对应期望回报由值函数矿(s)表示12。矿(s)一E办斗门 (2)i=0对于最优策略丌的值函数，表示如下：u+(s)=maxo”(s)V SS (3)状态S，转移到状态S，其最优值函数间关系为12373。(si)一max(r(&，口)4-托(S)，i一1，7 (4)可通过Q学习方法实现对最优可(s)的求取，系统在状态Si采取动作a的q因子为：q(s：，口)一r(s：，n)4

12、-托+(s，) (5)式(4)可写为训+(s：)一maxq(si，n)，i一1，扎 (6)q(s。，n)通过下式求得13：蚕f+1(5i，口)一百(si，以)4-礓(品，n)(r(5i，n)4-托+(st)一西。(5i，乜) (7)理论上一定条件下式(7)中蚕(si，a)可收敛于q(sj，a)E13，但由于Flow shop问题解空间太大导致状态过多，该方法不可行。因此，我们用支持向量机对q(s：，n)进行拟合。32支持向量机支持向量机能够将输入向量映射到一个高维线性特征空间，使复杂模型在高维空间以线性方万方数据工业工程与管理 第5期式展现，具备很好泛化性能。其基本理论为对于样本集合：X一(五

13、，d，)l i一1，竹)，d与z间存在函数关系。通过将z映射到高维空间实现d的估计，即Y一wjg，j(x)=扩妒(z) (8)J一0通过引入松弛变量专，F，其在高维空间分类约束优化问题表示为13Lp(硼，丰，F)一c(毫+。fd，一W丁p(x：)+elW丁9(z。)一di+F，(9)式中，C、为常数。该优化问题可引入Lagrange函数求解，由此得到d的拟合函数：y(z)一(12：一a 7，)志(z，z：) (10)式中，12，口7。是Lagrange乘子，k(z，z。)是内积核函数13。内积核函数可以有多种形式，由于Gauss核函数具备良好性能，因此本文中我们采用Gauss核函数。33 Fl

14、ow shop特征抽取任何一个具体Flow shop问题，调度叫和加工时间矩阵P(叫)可以表示其状态，但这种表示不适合学习系统，需要抽取问题主要特征，使同规模Flowshop问题具备相同表示形式。方法如下：(1)加工时间矩阵P(co)归一化。归一化矩阵为P(co)一(乡州，)。，按下式计算：芦(叫)一寺哗L (11)P叫，乙JJ 脚Lj)(2)特征表示。状态特征参数定义如下：工件指标t一(，)。1t，一P州) (12)机器指标n一(n。)。：记ac。为第i台机器完工时间，有：口。一aci一P的) (13)机器空闲为av一m蚤口z (14)#一机器空闲均方差为ad一(土m费(口：一2)v2 )i

15、工件等待tw，记幻为第歹个工件完工时间，有：tw一(tc，一tj) (16)。J=1等待均方差为甜一(1。2(纪，一tj)一tw)2)。 (17)则对Flow shop问题，其特征可由向量5C表示为贸()一(f，口，n训，ad，tzv，以) (18)34动作表示在Q学习过程中，状态转换由动作实现，结合Flow shop问题，动作其实就是对可行解实施交换操作，其量化定义如下。定义1在可行解为叫时，将叫中第厂位置工件(厂)和第g位置工件co(g)交换位置的操作定义为对状态叫采取动作，记为sw(f，g)(厂，g(1，卵)，厂g)，其值为删(加)一臼每盥 (19)在状态00采取动作SW(，g)后，系统

16、状态转换为“，表示为7一(1)，叫(厂一1)，叫(g)，(c，(，+1)，(g一1)，(厂)，叫(g+1)，co(n) (20)35算法实现算法由两部分组成，分别为学习训练模块和调度模块。学习模块通过离线学习不断提高支持向量机对q函数的拟合能力，调度模块通过调用学习后的支持向量机计算当前状态下采取各个操作对应q函数值，并选取q函数值最大的操作以获取新的可行解，若新的可行解优于当前解，则继续迭代重复该过程，否则所得即为最优解。图1为算法调度模块的流程图。学习模块通过对(7)式迭代，从而调整支持向量机参数，提高对q函数拟合度。其中每，(S。，a)由式(10)逼近函数获得。逼近的误差为匈，(s：，n

17、)=r(si，n)+托+(sJ)一面，(sl，n)(21)其中，r(s：，以)一C。(咄)Cm。(呜)u(st)一maxO(5，)。每次迭代的q函数的目标值表示如下q尸(s。，口)一r(s。，口)+yv。(St) (22)在迭代过程中，适当改变逼近函数参数，以缩短误差。学习模块的算法流程图参见图2。一25万方数据第21卷 李国昊，等：一种基于Q学习的Flow shop问题调度算法研究图1调度模块流程图4仿真计算我们通过数值计算从两个角度对算法性能进行了测试：一个方面是从算法搜索寻优性能；另一个是算法的离线学习性能。后者是前者的基础，只有学习到一定正确知识，算法搜索寻优能力才能提高。算法寻优性能

18、测试通过对一些典型算例计算，比较所提算法与其他算法间性能差别；算法学习能力测试通过改变算法学习参数和训练算例规模，分析算法性能变化。算法用Matlab70编写程序实现，仿真计算的计算机主要参数为：CPU，Core i5；内存，2G。所提算法在训练过程中进行了有限度的离线学习，通过比较可知当支持向量机的各个参数的值为表1中所示时算法的学习和求解效果最好，故支持向量机各参数值按表1设定如下：一26一图2学习模块流程图表1各主要参数取值N1 Nz C 算例数目我们通过改变学习过程中的迭代次数和训练样本数量来测试算法学习能力变化对其搜索准确度和搜索效率影响。表2数据是在学习过程迭代次数和规模为2010

19、0的训练算例逐步增加的条件下所得求解精度数据。训练算例按文献14方法随机产生。数据显示对于同一问题随着学习迭代次数增加万方数据工业工程与管理 第5期其make-span在逐步降低，说明学习过程越充分，算法求解能力越强。表2训练算例数目和迭代次数变化与Make-sp锄间关系图3所示为算法求解所需时间随迭代次数变化趋势，训练算例规模为20200，横坐标为迭代次数，纵坐标表示求解所需平均时间。由图可知随着迭代次数和训练算例增加，算法求解所用时间总体是下降的(除个别点外)。这也说明随着学习过程更加充分，算法的求解效率也逐步提高。我们将所提算法(记为LLXS)的求解精度与求解Flow shop问题的知名

20、算法RyE x53，TSGW16以及近期算法ODDE9|，HTLBO10做了比较，结果如图4所示。图中横坐标表示典型算例规模，分别为T1：2020，T2：5010，T3：5020，T4：10010，T5：10020，T6：20020以及T7：50020，纵坐标是make-span。由图4可知当问题规模较小时算法LLXS的求解精度略低于其他几种算法，但当问题规模逐步变大时，这种差别逐步缩小，对于个别算例，甚至达到其他几种算法精度。而且值得一提的是，我们所提算法求解效率较高，其求解时间随着问题规模增加基本上是线性增加的，增加数量有限jI一l 5 training satnples争10 train

21、ing satnplesO-5 training satnples，Q ，O图-算法求解精度比较5 结语本文针对Flow shop调度问题提出了一种基于Q学习的具备学习能力的调度优化算法。算法能够从离线训练过程中学习样本算例相关知识，并将该知识应用于调度优化搜索。算法以支持向量机对Q函数进行拟合，从而避免了在学习过程中遇到的状态过多问题。仿真计算结果表明所提算法与其他算法相比虽然在求解精度方面略有不足，然而算法的求解效率方面比较高。而且其求解精度可以通过离线学习不断提高，因此比较适合于实际应用。参考文献：13 Swart彬Optimal elimination methods in the m

22、X n flow-shopscheduling problem EJ3Operations Research，1973，21(6)：1250125923越民义，韩继业同顺序mX n排序问题的一个新方法fJ科学通报，1979，24(18)：8218243Carlier J，Rebai L Two branch and bound algorithms for thepermutation flow-shop problemJEuropean Journal ofOperational Research，1996，90(1)：2382514GareyMR，JohnsonDS，SethiRThe c

23、omplexity offlow-sbopand joh-shop schedulingJMathematics of OperationsResearch，1976，1(2)：1171295Ahmadizar FA new ant colony algorithm for make-spanminimization in permutation flow shopsJComputersIndustrial Engineering，2012(63(：355-3616Li X，Yin M A discrete artificial bee colony algorithm withcomposi

24、te mutation strategies for permutation flow shopscheduling problemJScientia Iranica Transactions E：Industrial Engineering 2012(19)：192119357Ii Z，Huang G Q，Luo HHybrid flow shop assemblyscheduling for one-of-a-kind production-CIn：Proceedings ofInternational Conference on Computers and IndustrialEngin

25、eering Hong Kong：Curran Associates Inc，2013：784803(下转第41页)一27一。一w难瞰0一Y忧孔蚁一吖一一著妻量xLH5O，2兰u5、&llrl铊粥万方数据工业工程与管理 第5期51李铁克，王柏琳等待时间受限的两阶段流水车间调度问题性质研究EJ管理工程学报，2011，25(1)：88 936刘志，董明，李永林等待时间受限的并行批处理调度问题研究J1。工业工程与管理，2014，19(6)：1171237Mazdeh M M，Rostami M A branch andbound algorithm fortwo-machine flow-shop

26、scheduling problems with batchdelivery costsJInternational Journal of Systems Science：OperationsLogistics，2014，1(2)：941048王柏琳，李铁克启发式算法求解等待时间受限的两阶段流水车问调度问题J管理工程学报，2014，28(2)：18219091王晶，姚辉，王艳亮，等有限等待流水车间调度邻域搜索算法J工业工程与管理，2010，15(3)：55 59101 Li T，Li YConstructive backtracking heuristic for hybridflowshop

27、 scheduling with limited waiting timesWirelessCommunications，Networking and Mobile Computing，2007WiCom 2007International Conference oil IEEE，2007：66716674C1Shanghai：IEEE，2007111 Liu S，Cui J，Li YHeuristic、tabu algorithm for hybridflowshop scheduling with limited waiting time，ComputationalIntelligence

28、 and Design，2008ISCID08InternationalSymposium oncWuhan：IEEE，2008r12Attar S F，Mohammadi M，Tavakkoli Moghaddam R，et a1Solving a new multiobjective hybrid flexible flowshop problemwith limited waiting times and machine-sequence-dependentsetup time constraintsJInternational Journal of ComputerIntegrated

29、 Manufacturing，2014，27(5)：45046913杨开兵，刘晓冰带调整时间的多目标流水车问调度的优化算法J工业工程与管理，2008，13(5)：卜514TavakkoliMoghaddam R，Azaridsh M，Sadeghnejad-BarkousaraieA Solving a multi-objective job shop scheduling problem withsequence-dependent setup times by a Pareto archive Pea()combinedwith genetic operators and WSEJThe

30、International Journal ofAdvanced Manufacturing Technology，2011，53(58)：73375015Benders J FPartitioning procedures for solving mixedvariables programming problemsJNumerische mathematik，1962，4(1)：23825216Dantzig G B，Wolfe PDecomposition principle for linearprogramsJOperations research，1960，8(1)：1011111

31、71、Slyke R Mwets R I；shaped linear programs withapplications to optimal control and stochastic programmingJ1SIAM Journal on Applied Mathematics，1969，17(4)：63866318Birge J R，Louveaux F vA muhicut algorithm for tw(stagestochastic linear programsJ1European Journal of OperationalResearch，1988，34(3)：3843

32、928Pan Q K，Wang I。，Gao I。A chaotic harmony search algorithmfor the flow shop scheduling problem with limited buffersJApplied Soft Computing 2011(11)：5270 52809Li x，YinL An opposition-based differential evolutionalgorithm for permutation flow shop scheduling based ondiversity measureJ1Advances in Eng

33、ineering Software 2013(55)：1031101 Xie Z P，Zhang Z Y，Shao X Y，et a1An effective hybridteaching-learning based optimization algorithm for permutationflow shop scheduling problemJAdvances in EngineeringSoftware 2014(77)：354711Li X，Wang J，Sawhney RReinforcement learning for jointpricing，1eadtime and sc

34、heduling decisions in make-to-ordersystemsJEuropean Journal of Operational Research 2012(221)：99109123 Mitchell T M Machine learningMBeijing：China Machine(上接第34页)1 1 1 Yu s，Pan QA rescheduling method for operation time delaydisturbance in steelmaking and continuous casting productionprocessJJournal

35、of Iron and Steel Research，International，2012，19(12)：334112Mao K，Pan Q K，Pang X，et a1An effective Lagrangianrelaxation approach for rescheduling a steelmaking-continuouscasting processJControl Engineering Practice，2014(30)：67 7713Dong Y H，Jang JProduction rescheduling for machinebreakdown at a job s

36、hopJInternational Journal ofPress，200313Haykin SNeural networks：a comprehensive foundationM2ndBeijing：China Machine Press，2004143 Taillard EBenchmarks for basic scheduling problemsJEuropean Journal of Operational Research 1993(64)：278 285151 Reeves C R，Yamada TGenetic algorithms，path relinking，andth

37、e flow shop sequencing problemJEvolutionaryComputation 1998(6)：456016Grabowski J，WodeckiL A very fast tabu search algorithm forthe permutation flow-shop problem with make-span criterionJComputers and Operations Research 2004(31)：18911909173陈华，孙启元基于TS算法的直线往复2一RGV系统调度研究J3工业工程与管理，2015，20(05)：808818何华，何

38、正文，刘人境基于资源共享的延迟惩罚最小化的多项目调度优化J工业工程与管理，2015，20(06)：6975Production Research，2012，50(i0)：2681269114王晶，郑亚楠考虑机器故障的炼钢连铸重调度模型与算法设计J冶金自动化，2015，39(2)：283415王柏琳，李铁克，张春生等基于动态约束满足的考虑连铸机故障的炼钢连铸调度算法口计算机集成制造系统，2011，17(10)：21852194161侯东亮，李铁克基于动态约束满足的炼钢连铸重调度算法J计算机应用，2012，32(12)：35533557171侯东亮，李铁克考虑新任务插入的炼钢一连铸重调度模型与算法J1工业工程，2012，15(5)：33 38万方数据