英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
自动化集装箱码头多AGV调度问题
摘要：基于自动化集装箱码头装卸系统中的调度性能问题，本文提出了一个动态多辆自动导引小车（AGV）调度的方案。在多AGV调度中，AGV装卸作业时间和特定任务的优先级顺序是调度处理时主要的限制。把这些考虑到实际中，为了作业时间和码头起重机装卸时间的标准偏差尽可能减少，对于动态多AGV调度方案模型，本文采用遗传算法来解决，并且通过数学时间证明了此方案的有效性。希望本文提出的这个模型能够对于离散生产系统的多任务调度有重要意义。
关键词：自动化集装箱码头；动态调度；多AGV调度；遗传算法
1 引言
近几年集装箱码头的自动化是一个非常受欢迎的研究领域。米等在2015年一起提出了用以自动识别货船的一个船舶识别算法，也在2014年提出了一个快速人工监测算法来监控自动化集装箱码头的无人监视区域。米等在2015年对于自动化集装箱码头人工监测的进一步研究也有非常重要的意义。赵等在2015年提出了一个基于工作流的车载任务控制系统。这个研究提供了对自动化集装箱码头管理和设计的硬件和建模支持。在装卸过程中研究的另一个重要领域就是算法的问题。
水平运输装卸过程连接着码头和货物堆场作业，这个过程的效率非常直接的影响到集装箱码头的整个装卸效率。而水平运输的关键点就是调度的问题。
基于触发机制，多AGV和多运货卡车的调度可以区分为静态调度和动态调度。静态调度假设任务下达时间和小车行驶时间是确定的或者是可以被精确预测出来的；因此，整个调度可以被提前计算出来。动态调度假设任务下达时间和小车行驶时间都不能被精确预测，动态调度在大部分自动化集装箱码头更加符合实际情况。因此，调度是在装卸操作工程中按顺序执行的。
在集装箱码头装卸系统中，静态调度能够创建一个不同序列的整体协调安排用以提高总体作业效率。Dkhil等在2013年研究了自动化集装箱码头中装卸装备的联合调度问题来使作业时需要的AGV最少。Rashidi and Tsang基于最小流动模型在2011年提出了一个AGV调度算法模型。在自动化集装箱码头中最小化总延迟时间和AGV总行驶时间的方面，Kim和Bae在2004年提出了一种静态AGV调度的整数规划模型。张等基于固定的码头起重机装卸序列在2005年改善了一种小车调度模型，用以最小化码头起重机的等待时间。李和谭考虑到码头起重机和货物堆场的作业能力，在2010年对于大型运输码头提出了一种AGV调度的混合型整数规划模型。陈和卢针对集装箱码头中码头起重机、货物堆场以及AGV的联合调度在2013年提出了一种约束优化模型。Angeloudis和Bell在2010年提出了一种滚动策略来解决在不确定的情况下AGV的调度问题，在这种策略中，安排一个给定时期的计划需要根据前一个时期的执行情况来进行。Mossi等和Le等在2012年建立了一个针对同一种集装箱码头的跨运车调度模型，通过不同的算法来解决此问题。Nguyen和Kim对AGV调度问题建立了一种混合整数规划模型，用以最小化作业延迟和AGV总的行驶时间。
在动态调度中，当一个新的任务下达或者一个任务已经完成的情况下，需要触发一个新的调度过程来分配小车去执行未分配的任务。Jing和De联合码头起重机平衡任务序列和最近的一次调度，在2006年时提出了一种新的调度策略；利用仿真技术这个策略已经被证明其有效性。基于滚动策略，Jing在2010年提出了一种动态小车调度模型，并用遗传算法解决了此问题。Chen和De在2008年提出了一种多目标模糊决策方法，来解决在面对面操作模式下的动态小车调度问题，并给出了一个小规模的数学模型。Zheng和De在2006年针对多个码头起重机之间小车调度的问题提出了一种联合的动态优化方法。Briskorn等根据自动化集装箱码头中的实际库存改善了一种实时调度方法，来解决多台码头起重机之间的AGV调度问题。Briskorn和Hartmann在2006年利用仿真技术发现，把AGV的工作完成时间考虑到系统之中，能够改善集装箱码头的总装卸效率。Grunow等考虑到一台AGV只能同时装载两个20英尺集装箱的能力，在2005年提出了一种动态调度方案；Grunow在2006年也利用仿真技术比较了静态调度和动态调度之间的差别。De Koster等在2004年使用仿真技术比较了在集装箱码头中不同的动态调度方法，发现考虑了行驶距离的装卸过程比其他的调度方法要更优。
以上对于集装箱码头小车调度方法的研究，可以总结出以下几点：
- 静态调度不适合集装箱码头的小车调度。一个集装箱码头是一个有许多不确定因素的大型分立式系统，这些不确定因素直接影响到集装箱码头的装卸过程。静态调度在装卸操作之前进行所有任务的分配，所以这种调度方案不能适用于情况京城变化的场合。
- 整体最优化很难实现。以前大部分的研究都专注于一次给单一的小车分配任务，这种情况经常实现的是局部的最优化。在动态多AGV调度领域的研究非常稀少。
发展研究动态多AGV调度方案能够避免陷入局部最优。为了分配接下来的任务，动态多AGV调度需要精确的预测出装卸作业时的时间消耗。因为相比于传统集装箱码头中的货运卡车，自动化集装箱码头中的AGV受到的干扰更少，因此对于一台AGV正在进行的当前任务，切实可行地预测出剩余装卸时间也更加容易。在本文中，我们根据先前的研究，发展了一种动态多小车的调度方案，能够全面优化码头起重机的效率和更好的平衡码头起重机的工作序列。
2 问题描述
1 概述
动态多AGV调度问题是指在某一特定时刻同时给多台AGV分配任务，以此来优化装卸效率和调度平衡问题。
2 AGV工作序列
在实际情况中，一台AGV的调度需要以AGV的工作序列为基础，而工作顺序的排列又以当前任务的完成时间为基础。表1显示了一个AGV工作序列的例子。
表1 AGV工作序列例子
|
AGV |
剩余任务 |
当前任务完成时间预估 |
|
1 |
0 |
0 |
|
2 |
1 |
80 |
|
AGV |
剩余任务 |
当前任务完成时间预估 |
|
3 |
1 |
120 |
|
4 |
1 |
223 |
|
5 |
1 |
340 |
|
6 |
2 |
621 |
剩余的任务有一个顺序，因此，多AGV调度必须是动态的，并且是基于工作顺序的。为了做到这些，任务分配时间和配分配的AGV数量必须是已知的。
至于传统单台AGV的调度，为了避免AGV能力的浪费，任务分配时间需要是AGV完成其当前所有任务的时间。因为在AGV工作序列中当前任务完成时间是被预估出来的，在工作台上更低的多AGV预估时间往往会出现更多的错误。为了避免在调度前分配多余的AGV，命令去执行新任务的AGV应该是只有一个或者没有剩余任务的AGV。在表1的例子中，1-5号AGV在此时是可以被调度的。
3 动态多AGV调度的特性
在动态多AGV调度算法中对多台AGV同时分配任务时，AGV的装卸时间与传统单AGV调度会有所不同，这两种调度方法会依次影响到码头起重机的装卸时间。
图1显示了AGV装卸时间的组成部分。
AGV剩余任务作业时间
AGV从当前位置到码头起重机的行驶时间
AGV等待时间
作业时间
图1 动态多AGV调度中AGV作业时间的组成
另外，在调度过程中也要考虑到任务的先后顺序。事实上，集装箱码头的装卸过程中的任务序列是在装卸之前被确定好的。因此，必须要满足下列限制：
- 任务必须按顺序分配；
- 一个任务只有在它的前一个任务已经被安排的情况下才能被分配。
表2显示了一个带有前导任务的码头起重机的任务序列。图2显示了对于此任务序列的一种可行的调度方案。AGV所有作业时间的影响在图2中可以清楚的观察到，表示在调度方案中码头起重机的作业完成时间。
表2 码头起重机任务序列
|
任务序列 |
前置任务 |
|
1 |
/ |
|
2 |
1 |
|
3 |
2 |
码头起重机当前任务完成时间
AGV剩余任务作业时间
AGV从当前位置到码头起重机的形式时间
AGV等待时间
作业时间
剩余任务 任务1 任务2 任务3 任务
t
AGV1
AGV2
AGV3
时间
图2 动态多AGV调度甘特图
考虑到问题的这些特性，对于n台AGV在t时刻调度问题的解决方法，就是找到一种调度算法，这种算法使完成时间最短，也使满足实际限制的多台码头起重机的作业时间的标准偏差最小。图3显示了对于7台AGV调度问题的可行方案。
图3 解决AGV调度问题的可行方案
3 建立模型
1 模型假设
我们需要做出下列几条假设：
- 码头起重机对于每个任务的作业时间仅与任务本身相关，而与作业时的设备无关；
- 装卸设备没有任何故障。
2 自适应均衡
- 脚标
：代表各台AGV，，是所有AGV的数量；
：代表各码头起重机，，是所有码头起重机的数量；
：代表各任务，，是所有任务的数量，而且。
- 参数
：数值为或，指示是否是最好的工作序列，代表是，代表不是；
：第台AGV剩余任务的作业时间；
：第台码头起重机剩余任务的作业时间；
：第个任务的装卸和时间；
：数值为或，指示是否是的前置任务，代表是，代表不是；
：数值为或，指示任务是否已经被分配给码头起重机。
- 决策变量
：数值为或，指示任务是否已经被分配给AGV ，代表是，代表不是；
：任务的开始时间；
：任务的前置任务的完成时间；
：任务的准备时间；
：任务的完成时间。
任务的完成时间由（任务的前置任务的完成时间）和（任务的准备时间）所决定。等于和中较大的一个。有两种不同的情况：当任务有一个前置任务时，是前置任务的完成时间；当任务没有前置任务时，是执行任务的码头起重机完成当前任务的时间。这些关系可以由下列等式表示：
（1）
（2）
（3）
（4）
3 目标函数
为了建立目标函数，我们要考虑到：
- 最小化完成时间
（5）
- 最小化码头起重机作业时间的标准偏差
（6）
当是每台码头起重机所有任务的平均完成时间时
（7）
总的目标函数为
（8）
在（8）式中的和是两个子任务的权重，并且。实际上，操作流水线式更加重要的一环，所以加重的权重比（使得）更加符合实际情况。
4 约束条件
在此系统中下列几条约束条件需要得到满足：
资料编号：[10849]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
- 一台AGV能分配且仅能分配一个任务； 全文共6751字，剩余内容已隐藏，支付完成后下载完整资料
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
