基于改进合同网协议的动态调度计划研究

1.简介

近年来，工业系统正在朝着大规模、复杂和动态的方向转变，传统工业技术在许多关键问题上都受到了严重的挑战。工业生产的关键在于应用于调度和最优化的高效实用的方法。设想一下，一个有明确预定计划和固定处理周期的传统流程，但是在实际加工时，存在许多不确定性的因素，比如，加工周期的变化，产品需求的变化，交付的变化，以及设备的故障和资源、生产流程的变化。这些动态因素的干扰导致了最初的计划不能被有效执行。在对那些变化的不确定反应和时间中，人们开始想到，在基于程序活动下一周期的系统时间的情况下，进行重调度，因此，它具有非常高的研究价值。

Agent具有高度的自主权，在本文中，将运用多个自治的Agent来解决如何有效协调复杂而又动态的调度问题。在调度过程中，Agent之间可以相互磋商和协作，这样就有更高的实时性。这在动态车间调度中有同样的需要。所以本文将从独特的多Agent的交流机制，合作机制和MAS系统的机制开；结合详细描述的动态车间的重调度问题，建立一个总体的两方式派遣，局部自我优化的合同网协议谈判并仿真，证明其有效性。

2.基于MAS模型的调度

在动态的工厂调度环境下，工作车间的问题可以这样描述：在一个处理单元或系统中，有n个作业需要m个机器去加工，每个作业J_i有n_i道工序O_ij（），把所有机器作为一个集合M，那么每一道工序O_ij都可以通过M_ij来进行加工，其中，如果，那么这就是一个完全的柔性问题，如果，那么这是一个带有柔性性质的局部规划问题。

重调度的运算方法是，如果一台机器发生故障，所有的机器都需要按运算方法重新调度，重调度的运算子本质上是变量约束条件下的最优求解问题。

由于重调度模型是对应的从最初的调度模型演变过来的，因此最初的模型也是可以利用的。

S.t. (1)

(2)

(3)

(4)

(5)

(6)

i表示工作的序号，且i_I，j表示级别序号，且jJ={1，}，r_jl表示机器序号，s_ij表示原始调度的开始时间，p_ij表示工作的处理时间。

在上述模型中，（1）式表示调度问题的最优化目标是使C_max最小。（2）式表明操作的时间限制，它说明工件只能在上一阶段的工序结束后才能开始下一阶段的处理任务。（3）式表明如果有两个作业需要同一台机器处理，则这两个作业不能同时进行。（4）式表明工件的加工在开始之后就不能被打断。（5）式和（6）式表明操作开始时，机器的加工范围和时间都是可变的。

那么假定机器r_jdld在[t_b,t_e]时间被打断，则原始的调度就在t_b时刻发生了变化，转变成了动态的重调度。

(7)

S.t.

(8)

(9)

1. 式指的是最大化调整和准备前后的时间和分配给相同机器的总权重。（8）式表示增加的机械故障这一新的约束条件。（9）式表示新的操作应在t_b之后开始。

3.基于MAS模型的动态调度系统

传统的重调度普遍的采用体力劳动方式或者依照确定的再分配规则进行操作。本文将采用基于MAS理论的智能调度系统，主要通过智能机器之间的协作，以达到作业重调度和最优算法的自动化目的。改进后的合同网模型的基本架构是不变的，依然由管理Agent，资源Agent，监督Agent，执行Agent组成。

管理Agent 管理Agent是调度系统的核心，主要负责对授权外发的任务进行评价和调度。具体的任务包括对主机信息和紧急程度的评价，然后将信息提交给资源Agent。管理Agent和其他Agent之间的关系如图一所示。

资源Agent 资源Agent负责接收和处理工厂外部生产任务，并依照最近的生产能力决定是否执行车间任务。分解任务，每个执行Agent都发布投标，并按照协议形成安排计划，然后将结果向监督Agent报告，得到各Agent负责的生产调度反馈。资源Agent的内部图解如图二所示。

监督Agent 监督Agent主要是对管理Agent的后备生产计划进行模拟，并选择一条合适的生产路线回馈给管理Agent，管理Agent必须明确的遵从这一路线。同时，监督Agent也负责监督各Agent的设备是否故障，添加新设备以及出现的紧急任务。监督Agent的内部图解如图三所示。

执行Agent 执行Agent实际上可以看作是一个生产单元。每一个Agent都各自管理好单元的每一部分，负责进行合适的操作管理，设备，调动命令和信息收集。在资源Agent对生产设备的条件是否符合作出评价后，执行Agent收到信息，然后决定是否投标。如果投标，执行Agent将会根据设备情况作出相应报价，反馈出以资源Agent的生产能力是否能完成任务。内部图解如图四所示。

基于不确定因素的自动化集装箱码头自主跨运载体的大规模任务分配调度策略

1.简介

在过去的几十年间，因为集装箱化和世界贸易的持续增长，集装箱的运输频率和生产能力都在稳定增长。相应的，为了提高码头生产效率，降低作业成本，集装箱码头需要尽快的转变以运送更多更大的集装箱。因此，码头都有许多不同种类的场地搬运工具来协助集装箱的搬运，比如集卡（在不同区域之间运送集装箱）和起重机（在码头的小的固定区域内运送集装箱），它们被高效的用于装卸和转运集装箱，这对于现代集装箱码头来说是非常重要的。在集装箱的运输系统中，集卡扮演着一个非常必要的角色，因为它能比起重机更加灵活的在区域内自由移动。自动物料运输工具和机器人的快速发展促进了集装箱码头自动化设备的发展和部署，比如场地搬运工具中的自动导引小车（AGVs）和自动起重机（ALVs）。相对于人工操作的车辆来说，自动物料运输机器人要求高度的协调性和效率性。因此，自动场地车辆的实际操作变成了一个非常必要的课题，并在机器人技术和物流学领域中一直被研究员和工程师们研究。目前，学者们提出了许多算法或者方法，包括两个启发式算法，一个是在高度自动化的集装箱码头中，基于柔性优先权规则的AGV调度算法；另一个是基于混合整数规划模型的小型ALV车队调度算法。同时还有许多不同的算法，如模拟退火算法，蚁群算法，拍卖算法，工作分组和列生成算法等，它们都被学者们用于研究自动化集装箱码头的多功能自主车辆操作。

本文重点在于研究新作业随时到达这种不确定因素下的大规模自动化跨运载体的重调度策略，和自动化集装箱码头的操作指导方针下的分配问题。两个事件驱动的重调度策略已有了长足发展，并与用于解决新作业到达这种不确定事件的自主跨运载体的长期任务分配策略进行了比较：（1）新作业重调度（RNJ）策略（解决在每个计划中只考虑新到达作业的自主跨运载体调度问题）；（2）新作业和未执行作业重调度（RCJ）策略（在先前的调度计划中考虑新作业和未执行作业，以此来解决自主跨运载体调度问题）。评价这两种策略的执行效果需要用到一种多目标成本函数，该函数通过加权因素结合了跨运载体的移动成本，等待成本和完成高优先级作业时的延误成本。在每一个重调度策略中，为了求得小规模计划的调度，都非此即彼的使用了运用列生成算法的界定法和简单拍卖算法。仿真模拟是在Patrick集装箱码头实际示意图的基础上进行的。这些都论证了在大规模跨运载体的调度中，RCJ策略相对于RNJ策略来说具有更好的表现。进一步的证明了大规模跨运载体调度的最优化问题需要更好的拍卖算法，尤其是在长期范围内。

调度策略

3.1RNJ策略

当新任务到达时，RNJ策略只会解决自主跨运载体调度的新任务到达问题，并且保持调度计划不变。假设n_new个新任务在t时刻到达，RNJ策略会令新的任务数量n=n_new来解决自主跨运载体调度的子问题（在下章建模）。注意跨运载体的数量m是不变的，因为在本文中将整个调度中的跨运载体都视为同一组。在新的自主跨运载体调度子问题中，跨运载体v的初始位置会随着之前调度计划v的最后位置而更新，最后位置即为之前调度计划中分配给跨运载体的最后的任务的着陆位置。跨运载体的可利用时间会随着之前调度计划的完成时间而更新，也就是在之前调度计划中跨运载体v在分配最后任务后在着陆位置的服务时间。新的自主跨运载体调度子问题的其他参数（如操作时间窗和跨运载体移动时间）可以在新任务到达信息的基础上更新。那么新的自主跨运载体调度子问题就可以用求解算法（如下章中改进的拍卖算法和列生成算法）解决，得到新任务的新调度计划。

6.结论

在自动化集装箱码头中，为了解决大规模的重调度问题，以及自主跨运载体遇到意外事件（尤其是新作业到达）时的任务分配问题，本文提出并比较了两种重调度策略，RNJ策略和RCJ策略。在每个计划中，为了得到自主跨运载体调度问题的调度计划，我们建立了基于装卸货问题的最优化模型，并且使用了精确的列生成算法或拍卖算法。同时，跨运载体的移动成本、等待成本和完成高优先级任务时的延误成本之和被用来作为解决自主跨运载体的调度问题和评估调度策略表现的目标函数。通过计算和比较的仿真，我们证实了所提出策略的表现，证明了RCJ策略对于达成小的目标成本的优越性，也说明了在每个计划中，对于解决自主跨运载体调度问题的更先进算法的需求。未来的对这方面的研究包括对解决其他意外事件（例如跨运载体故障或延误）的调度策略的改进，对跨运载体调度问题算法的改进，以及对于重调度策略重新规划时间的选择策略的改进。

适用于铁路运输的动态，实时，可重新安排和优化的MAS架构

1.简介

铁路运输服务作为公共服务的保障，需要一丝不苟的规划并且经常提前在时间表中公布出来。时间表中包含列车的出发时间，到达时间，在休息位置的顺序，是没有冲突的。如果在这样一个可行调度的时间或受限空间内发生了一件突发事件，那么它会导致列车延误，有时还会发生列车之间的冲突。冲突是一种安全约束违规，两列或更多列车需要同时占用轨道段。因此，需要修改车站到达和离港顺序的列车时刻表和排序。在重型铁路运输方面，人工调度员对中断的交通进行再排序和再调度。突发事件通过两种不同的方式解决——一种有计划的维护（优先于实际突发事件），即突发事件发生前，将日程表修改为位于实际突发事件之前的站点；以及一种重调度方法（当突发事件发生），在中断位置和发生时刻修改时间表。人工调度员总是采取经验法则进行重调度，这有许多固有的缺点。一个是他们按照标准的排序进行调度，如先来先服务，延迟最大的先服务，更早到达目的地的先服务等，这些并不能有效的解决所有种类的突发事件。第二，对于人工调度员来说，是几乎不可能去预知一个现在的解决方案是否会导致将来的延误或操作领域的额外冲突的。本文提出了一个多智能体系统的模型去对扰乱的铁路交通进行重调度。我们的方法背后的动机是去克服基于人工经验法则调度的限制。本文提出的多智能体系统有两个非常有意义的特点：动态决策和实时决议，接下来将会进行简单论述。

动态决策：调度策略不按照规定排序进程；只要或者每当突发情况发生时，调度的优先次序都取决于不同的情况。

一个小的事件也能引起安全违规或者客观上的质量损失，并且让本来可行的调度计划无效。Corman，D^rsquo;Ariano，Pacciarelli和Pranzo报告说人类专家通过决定分派订单来发现，决定分配和恢复调度计划。人工的决定缺乏对未来影响的分析，缺少一致性和责任性。这样的分派决定很有可能产生死锁，当两辆或更多的列车需要分割轨道时，就容易互相占据对方轨道。

为了防止死锁的产生，维护可行性，一致性和突发事件决策的趋同性，有效的估算是必不可少的。

对于突发事件下不断变化的调度参数，在分派订单的定量应用时，得到可行的，无冲突的重调度计划，和最优化一些绩效目标是非常有效的。

根据Sahin(1999)的报告，分派决策中失败的建模参数和结果使调度目标的偏差最小化。

实时决议：处理措施一定要足够快，让在现实情况，甚至大的问题尺度上的重调度更有效。利用所有可利用的资源，让估算时间最小化。

生成解决方案时，估算一定要快，以在现实的时间解决突发事件。

实际上列车的重调度是一个很大尺度的问题，需要巨大的估算资源。分散的不同种类的资源如果是可移植的和可共同操作的，那么它们可以以一种协调的方式利用起来。可移植性意味着该应用程序能够在不同的平台或操作系统中运行。共同操作性涉及到数据的简便和支撑，还有应用程序在不同估算资源之间的转移。

经常的人工干预对实时的应用程序是不利的。解决方案需要能自我调用。

轨道调度规则要战略性的实施，尽管有时候有必要依据个案进行修订。一个可扩展的计算技术要能容易的修改根本的约

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[138948]，资料为PDF文档或Word文档，PDF文档可免费转换为Word