博弈论在调度中的应用文献综述
2020-05-04 21:17:57
| 1、 目的及意义 1.1目的及意义 随着传统的车间作业环境、柔性制造系统到复杂的分布式制造系统、面向服务的网络化制造环境团的发展，制造系统变得越来越复杂，系统的动态性和不确定性更加突出，使得解决复杂制造环境下的调度问题变得越来越困难。 在网络化制造过程中，生产模式已经从“制造”转变为“按订单生产”，在生产过程中，客户主动参与制造过程中的制造工作也受到了压力。不同制造业岗位之间的交货期竞争正成为流程规划和调度中需要解决的焦点问题。为了达到快速交付市场的目的，生产出不同岗位的最佳工艺方案，正成为企业在激烈的全球市场竞争中生存的关键问题 相比于传统的调度问题，新制造模式的调度具有一些新特征：以用户需求为导向；分布式的制造资源；用户需求之间的竞争性。有限的分布式资源和订单（客户）之间的竞争约束，是当前工业环境中要解决的主要矛盾。博弈论是处理理性决策者间合作与冲突的数学理论和方法。制造环境下，用博弈论解决调度问题已有部分研究者在探索。多种合作的和非合作的N人博弈被研究和提出。不同于大多数的智能优化算法研究，博弈论的优点在于能够很好的协调多客户在有限资源情况下的平衡关系。智能工厂中，为了使得复杂多样的制造任务能够有序进行，把车间划分为多个制造单元。实际生产中，每个单元内同时进行多个制造任务，每个任务的所属的订单不同，所以各个任务之间有着竞争关系。当制造单元内异常发生时，就需要对单元内的任务进行重调度。此时，单元内有限的机床、物料和工人等资源必然会影响各任务的完成时间。如何重新规划各个具有竞争关系任务的完工时间，是单元内重调度的难点和重点。本研究拟以智能算法与非合作博弈理论相结合，研究单元重调度问题，旨在帮助企业实现缩短交货期、降低库存成本和提高客户满意度。 1.2国内外的研究现状分析 调度问题的研究始于20世纪50年代，最经典的调度模型建立通常是利用数学规划方法进行的车间调度问题描述。例如Wanger[1]就将车间调度问题归纳为一个整数线性规划模型进行研究;Blazewics等[2]采用了数学规划方法建立模型，并且细致分析了单台、多台并行机床、流水车间和作业车间调度问题的不同表达形式;Christian Artigue等[3]人提出了一种整数线性规划和约束规划混合的调度方法来解决车间调度问题;Cemal Ozguven等[4]人提出了一种混合整数规划方法，将问题转化为一个等价的网络问题，建立了两个混合整数规划模型。近年来智能调度方法成为解决实际调度问题最有效的途径和最有前途的研究方向之一。目前已有的调度成果大多是解决单目标或同构多目标调度问题，对异构多目标调度问题研究较少，关于多任务车间作业调度问题使用的方法以进化算法为主，如遗传算法、蜂群算法、粒子群优化算法、蚁群算法等。 Ponnambalam等[5]通过运用多任务GA算法来解决Giffler and Thompson算法在车间调度中无法解决的冲突操作问题。Lei等[6]通过在多任务进化算法中引入个体密集距离理念，以解决多任务JSP问题。 Arroyo等[7]则通过将精英策略、并行多任务局部搜索等融入多任务进化算法，用于解决车间作业调度问题。Pan等[8]人在人工蜂群算法的基础上提出了离散人工蜂群算法(Discrete Artificial Bee Colony, DABC)算法，结合有效的局部搜索方法和自适应策略，达到最小化总加权延迟的目标。Tasgetiren等[9]人提出的算法中融合了离散人工蜂群算法和迭代贪婪算法，以最小化序列流水车间调度问题的总完工时间为目标;通过对比实验验证了算法在解的质量和CPU时间两个评价指标上的性能。Pan等[10]人为解决文中提出的以最小化完工时间为目标的混合车间调度问题，以离散人工蜂群算法为框架设计算法，并辅以多重优化策略。Wang等[11]人采用人工蜂群算法解决弹性车间调度问题，该问题模型同样以最小化完工时间为目标。为了避免算法陷入局部最优，文中在初始化、雇佣蜂和观察蜂等阶段分别采取了相应的策略，对比实验结果验证了算法的有效性。 另有一些其他方法，如一些研究者尝试将博弈论的方法运用到网络化制造环境下的任务调度问题中，在考虑一些诸如机器加工费用、任务物流费用、库存费用、拖期惩罚等制造成本下，研究怎样合理分配与利用资源，使各项作业能够快速并且均衡地达到最优。如Gordon V等[12]考虑了如何在due date内安排调度;Mosheiov G等[13]提出了最小化加工时间规则，最小完工时间规则和最小交货期规则，但是并未把三种分配规则结合起来对同一个调度进行优化，Sakawa M等[14]在遗传算法解决JSSP中考虑了加工时间和完工时间的冲突却没有把二者联系到相同问题上进行分析。因此，为了使各加工作业符合实际，更好地处理不同任务间的竞争，同时，让所得解更符合利益均衡而达到时效性最优，Zhou等人[15]基于博弈论思想，通过建立一个具有完全信息的非合作博弈模型，把各项制造任务作为来源于不同客户的局中人，运用遗传算法寻找Nash均衡点来处理工艺规划和作业分配中的竞争。虽然得到了该模型的Nash均衡点，但获取速度相对较慢，而且对于大规模加工作业的问题，遗传算法交叉及变异算子设计较为复杂，一定程度下影响了获得Nash均衡点的速度。周艳平等人运用合作博弈模型来研究流水车间调度问题[16]，把客户间的合作方式建立成一个联盟，通过加工任务的重新排序来确定联盟间的共同利益，以优化客户线性成本为指标，提出了机器加工时间关联加工工序的模型。这种处理方法是通过逐一分析联盟收益函数来确定最终的排序的，在处理多任务和机器的问题上类似于分支定界法，计算量大且费时较多，不适用于现代企业柔性作业调度的需求。
|
2. 研究的基本内容与方案
{title}| 2、基本内容和技术方案 2.1设计（论文）主要内容： （1）文献阅读：了解新制造模式下调度方法的研究背景和发展趋势；学习博弈论和智能算法的相关知识，思考如何将博弈论运用于调度算法之中。 （2）整体设计：以工业制造车间为场景，以场景中的制造单元为研究对象，针对单元中多任务的调度问题进行研究，提出解决方案并进行仿真实验。 （3）撰写毕业论文：不少于15000字及200字以上的摘要。参考文献20篇以上，其中近三年的外文文献不少于5篇。 2.2基于博弈理论的车间实时调度实现
图2.1实施优化策略的程序 （1）机器组和任务池的形成 此步骤的目的是在合理的制造环境中形成一组机器和相应的任务池。首先，根据加工能力和特点将机器分为不同的组。例如，g = {g1, g2，…，gn是一组不同的机器组，g1代表车床组，g2代表铣削组等。当一些机器在一个组中进行处理时，这个组中的所有机器都将在对应的任务池中竞争处理任务。 第二，根据不同的制造过程的类型形成多个任务池，并将每个任务的第一个未加工的生产过程进行挑选并放入相应的任务池中。例如，e代表车床工作的任务池，而f代表铣削的任务池。因此，基于所提出的方法，机器组和任务池是完全匹配的。 （2）实时调度策略的实现 该步骤包括使用实时状态信息实现调度策略。根据机器组和任务池的配对结果，一些进程被分配到最优机器上。如果机器暂时无法完成任务，分配给机器的进程称为虚拟进程，并将被放回任务池中。否则，这个过程被称为一个真实的过程，并将被添加到机器的处理队列中。同时，将属于下一个制造步骤的新流程添加到相应的任务池中。在完成所有处理任务之前，机器将不断地发送新任务的请求。当特殊事件(如机器故障和订单的变化)发生在实时调度工作车间时，通过改变玩家或游戏策略可以及时消除异常带来的影响。 2.3问题描述： 在某作业车间中，包含m台设备，客户提交n个待加工任务，每个任务包含多道工序，加工同一工序的设备有多台，工序的加工时间和加工费用随机床的性能而变化;任务的库存费用与存储时间成正比，任务的调度不仅受设备资源限制，而且受成本(包括加工成本、存储成本、和拖期惩罚成本)的影响，任务调度的目标是各任务的完成时间和成本的综合目标值最小.设定的假设条件为:①当某个任务的某道工序在某台设备上加工时，在完成之前不能被中断;②所有的任务机会均等，不存在优先权;③不同工序不能同时在某台设备上加工;④各任务的加工工序和加工时间已知，且不随加工排序的改变而改变，任务的装卸时间在加工时间内计算;⑤不考虑运输时间。 根据数学模型和假设条件，竞争驱动的作业车间任务调度目标就是寻求使得每个制造任务均能达到综合目标值最小、利益均衡的调度结果。 2.4建模思路： 博弈论通常可以描述为五个方面，G=lt;P,S,I,U, Ngt;即博弈的参与者，博弈策略，信息，参与者的收益，以及博弈的均衡等五个要素，这些要素确定一个博弈时所必须要设定的。博弈论就是利用上述因素来系统地研究各类的博弈问题，并寻求各博弈参与者在选择最优策略情况下博弈的解，即是均衡。 本文将采用非合作博弈理论对某一车间进行多目标调度建模。首先对车间的博弈要素进行分析如表1-1所示。 表1-1
基于以上的分析本文的建模思路是:将客户提交的订单任务映射为非合作 博弈的局中人(P)，并将可选的机器设备映射为可行性方案集合(S)，使各订单任务的完成时间和成本的综合指标函数映射为收益函数(U)。
其中:N为局中人(制造任务)集;任务包含道工序;为J的第I道工序;为的收益函数; 在描述收益函数的表达式中，给出如下定义:①为的在上的加工时间，;②为的在上的开始加工时间;③为的完工时间;④为的加工费率;⑤为拖期的一次性惩罚金额，为拖期一次性惩罚金额外的单位拖期时间惩罚费率;⑥为提前完工的单位时间库存费率;⑦, ,分别为的交货期、提前时间、拖期时间，且有
基于以上定义，可得出的加工成本为 = 的拖期惩罚费用和提前完工库存费用(假设这两项费用分别为滞后时间和提前时间的线性函数)为 = = 据此得出的总成本为 == = 调度以各制造任务的完工时间和成本构成的多目标综合指标的优化为目标，由于时间和成本的取值处于不同的归一化的范围，所以需对时间和成本 进行归一化处理.根据对生产率和成本的要求分别确定权重系数，实现多目标优化问题向单目标优化问题的转化，进而得出的收益函数为
式中:为时间权重系数;为成本权重系数，并受如下约束
式中：i，x=0，…，n-1;j=0,…，；y=0，…， 基于非合作博弈模型，作业车间任务调度问题就转化为针对相关约束的N ash均衡点求解，即满足 , 式中为的最优策略，为的可行方案(对应于J，的可选加工设备)集。令M为面向N的所有可选加工设备的集合，记为M= { }，据此得出 ;M 2.5求解方法： 利用博弈演化算法求解 (1)博弈结构G 博弈结构以每个工件作为一个博弈主体I.(i=0, 1，…，n)，以工件的每一个工序调度作为一个策略，同时对应一个解，同一策略(即一个确定的排序)下，各主体的效用“相等，u即为适应值Z的值。 (2)初始局势So 算法以随机生成一个所有工件的排列作为开始，并获得初始解。 (3)行为算子a 博弈论有个基本假设，即参与博弈的各个主体(I.)具备经济理性，也即始终追求自身效用的最大化，因此最优策略即为主体在当前演化局势中能使 得效用值取最优的对策.最优策略通过行为算子a比较该主体所有可能策略在当前局势下的不同效用求得。 所有博弈主体(即排列中的工件)以某种特定的顺序(本文中采用工件在所有设备上加工时间的方差从大到小的顺序)与排列中的其他博弈主体互相交换位置，如果交换后的新排列的适应值优于当前排列的适应值则进行交换，否则保持原来的排列。 （4）局势演化算子C 各主体通过顺序最优反应动态达到的某个均衡状态，从而得到一个局部最优解，随后对这个均衡施加一个扰动，扰动过程通过局势演化算子C对处 于均衡状态中的各主体施加随机扰动，使之偏离原均衡状态，然后再由各主体的顺序最优反应动态恢复到新的均衡状态，不断重复这样的扰动恢复过程直到搜寻到更优的解。 对于每个博弈主体((I.)产生一个随机数r (0lt;rlt;1)，若:大于扰动概率P，则该博弈主体与另一随机选取的博弈主体交换位置，否则维持原位置不变，这样就得到了一个扰动后的新局势I'，通过改变扰动概率P的大小，可以调节算法全局搜索能力与局部搜索能力的大小。 （5）停止准则T 称扰动后达到均衡状态为一代，T为预设的一个最大代数，当已运行的代数t达到T时，算法停止。 整个算法的流程如图2.2所示:
图2.2算法的流程 2.6仿真 MATLAB可将各个功能模块的功能集中于一个易于使用的操作环境，具有功能强大、操作简单、易于编程的特点，本文计划利用MATLAB编写模型相关算法得到数值计算结果，并利用anylogic验证计算结果。 |
4、参考文献
[1] H.W. Wanger. An Intergerlinear programming model for machine scheduling[J]. Naval Research Logistics Quarterly, 1959, 6:131一140
[2] J.Blazewicz, M. Dror，J. Weglarz. Mathematical programming formulationsfor machine scheduling:a survey[J]. European Journal of Operational research,1991, 51(3):283-300.
[3]Christian Artigues, Michel Gendreau. Solving anintegrated employee timetabling and job-shopscheduling problem via hybridbranch-and-bound[J]. Computersamp;Operations Research,2009(8):2330-2340.
[4]Cemal Ozguven, Yasemin Yavuz. Mixed integer goal programming models for the flexible job-shopschedulingproblems with separable and non-separable sequence dependent setup times[J].AppliedMathematical Modelling,2012(2):846-858.
[5] Ponnambalam S.G. Ramkumar, V Jawahar N. Amultiobjective genetic吨orithm for job shop scheduling[J]. Production Planning and Control, 2001,8(12): 764-774.
[6] Lei Deming, Wu Zhiming. Efficientmufti-objective evolutionary algorithm for job shop scheduling[J]. ChineseJournal of Mechanical Engineering (English Edition), 2005, (18):494-497.
[7] Arroyo German, Martin Domingo, Luzon Maria. Astochastic approach to simulate artists behaviour for automatic felt-tippedstippling}J}, CEC 2010, 2010: 24-27.
[8] Pan Q, Fatih Tasgetiren M, Suganthan P N andChua T J. A discrete artificial bee colony algorithm for the lot-streamingflowshop scheduling problem}J}.Information Sciences, 2011, volume 181:2455-2468.
[9] Tasgetiren M F, Pan Q, Suganthan P N and Chen AH, A discrete artificial bee colony algorithm for the total flowtimeminimization in permutation flow shops[J]. Information Sciences, 2011, volume181:3459-3475.
[10] Pan Q, Wang L, Li J and Duan J. A noveldiscrete artificial bee colony algorithm for the hybrid flowshop schedulingproblem with makespan minimization[J]. Omega, 2014, volume 45: 42-56.
[11] Wang L, Zhou G, Xu Y, Wang S and Liu M. Aneffective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. The International Journal of Advanced ManufacturingTechnology, 2012, volume 60: 303-315.
[12] Gordon V, Proth J M, Chu C. A survey of thestate-of-the-art of common due date assignment and scheduling research[J].European Journal of Operational Research, 2002, 139: 1-25
[13] Mosheiov G, Oron D. A note on the SPT heuristicfor solving scheduling problems with generalized due dates[J].Computersamp;Operations Research, 2004, 31: 645-655
[14] Sakawa M, Mori T. An efficient geneticalgorithm for job-shop scheduling problems with fuzzy processing time and fuzzydue date[J]. Journal of Computersamp;Industrial Engineering, 1999,36(2):325-341
[15] Zhou G H, Jiang P Y, Zhang G H. Gametheoretical framework for process plan decision of jobs in networkedmanufacturing[C]. Proceedings of the IEEE International Conference on Automationand Logistics, Jinan, China, 2007, 1868-1873
[16]周艳平，顾幸生.一类流水车问调度问题的合作博弈[J].化工学报，2010,61(8):1983-1987
