随着“中国制造2025”的提出，以及云计算、互联网和大数据等信息技术的发展，大规模定制化和多品种小批量的生产模式逐渐成为主流。在这种以个性化为主的生产模式下，产品种类繁多，工艺流程复杂，合理的车间调度方案对于提高生产效率至关重要。在传统的柔性作业车间调度问题研究中通常不考虑工件的转移时间，导致这种调度结果并不是理论最优调度结果，对于实际生产的指导存在不足。AGV（automatedguidedvehicles）是一种高柔性、高可靠性及高效率的先进物流装备，在数字化车间中负责实现工件的转移［1］。在这种情况下，机器的调度和AGV的调度会相互影响，所以AGV和机器集成调度问题越来越受关注。
土耳其学者Ulusoy等［2‐4］于1993年首先将AGV和机器集成调度作为研究对象，在不考虑AGV路径冲突的前提下，应用遗传算法求解调度问题，并建立了标准算例库。Abdelmaguid等［5］在Ulusoy的基础上提出一种精英保留策略，研究了6种交叉操作和3种变异操作的最佳组合以及交叉和变异最优概率范围。Zheng等［6］针对该问题，建立了混合整数线性规划模型，以最大完工时间为优化目标，提出禁忌搜索算法结合12种邻域结构求解该模型。Deroussi等［7］提出一种混合粒子群遗传算法用以解决柔性制造系统中AGV和机器集成调度问题，包含了一种基于AGV的解决方案。刘二辉等［8］提出一种改进花授粉算法求解AGV和机器集成调度问题，并研究了AGV数量对调度结果的影响。
以上研究为了将问题简化，都聚焦于AGV和机器的调度，着力于解决AGV和机器的任务指派、任务执行时序问题，将AGV的行驶道路设定为单道单向，并且不考虑潜在的路径冲突。当AGV的行驶道路为单道双向时，系统的运行效率将会得到提高，但路径冲突也会随之增加。路径冲突如果不解决，就会出现AGV碰撞以及路径被死锁等问题，打乱调度计划甚至造成生产系统瘫痪。因此，在AGV和机器集成调度问题中，考虑AGV路径冲突具有重要的现实意义。Said‐imehrabad等［9］建立了一个由车间调度和无冲突路径组成的数学模型，提出一种二阶段蚁群算法，首先解决AGV的分配问题，然后再解决AGV的路径冲突问题。Shi等［10］考虑AGV运行时间、停车和转弯的影响，提出一种两阶段调度策略，首先通过Dijkstra算法规划路径，然后考虑AGV之间的约束关系并通过遗传算法对结果进一步优化。Lyu等［11］提出一种改进遗传算法求解柔性作业车间AGV和机器的集成调度问题，通过Dijkstra算法为AGV规划无冲突的最短路径，并把AGV数量当做变量研究最大完工时间的变化，若在算法中采用主动解码，其结果将会更优。
AGV和机器集成调度问题已经被证明是NP难问题的叠加［7］，这类问题的解空间庞大且复杂，精确算法难以在可接受的时间内求得最优解，启发式算法更适合求解此类问题。鲸鱼优化算法是Mirjalili等［12］于2016年模仿座头鲸独特捕食行为提出的仿生算法，和其他智能优化算法相比，具有结构简单、参数少、搜索能力强且易于实现等优点，在航路规划［13］、港口拖船调度［14］及选址问题［15］等离散优化问题中的应用越来越多。
综上所述，传统的作业车间调度研究不考虑工件转移时间，无法满足当前生产模式转变所带来的新需求。同时，目前对于AGV和机器集成调度问题的研究大多不考虑路径冲突，与实际生产情况不符，而考虑路径冲突的研究大多采用分阶段的策略进行求解，并非真正意义上的集成调度。鲸鱼优化算法作为一种启发式算法在离散优化领域取得了一定的成功，但在调度领域的应用不多。为了实现无冲突路径的AGV和机器集成调度，笔者首先以最大完工时间为优化目标，建立数学模型；然后，为了求解该模型，将鲸鱼优化算法应用在集成调度领域，对于鲸鱼优化算法存在的不足，提出针对性的改进方法，即基于时间窗和Dijkstra的离散型鲸鱼优化算法；鲸鱼优化算法作为算法迭代的整体框架，基于时间窗的Dijkstra算法用于算法解码过程中AGV的路径规划；最后，通过标准算例对比实验和柔性算例实验验证了所提算法的性能。
1问题描述及数学模型
1.1问题描述
假设有n个需要加工的工件，m台用于加工的机器，k台用于运输工件的AGV。每一个工件有ni道工序，每道工序至少可由一台机器加工，选择不同的机器加工时间一般不同。每台AGV可以在任意两台机器以及仓库之间运输工件，运输的路线一般是起点和终点之间可行的最短路径，运输时间取决于运输路线的长度以及路途中的冲突状况。AGV完成一个运输任务分为空载和负载两个阶段，空载阶段AGV需要从当前位置行驶到工件当前所在的位置；负载阶段AGV将工件从当前位置运输到加工机器所在位置。
已知条件有：AGV数量、各机器的位置、所有工序可选择进行加工的机器及对应的加工时间、任意两节点之间的距离（当不可通行时为无穷大）。要求在满足一定的约束条件的情况下达到优化目标的目的，具体可分为以下几个子问题：为每一道工序分配机器和AGV；为各机器安排加工任务序列和各加工任务开工时间；为各AGV安排运输任务序列和各运输任务开始时间。此外，为了简化问题，存在以下假设：
1）在开始时刻，所有AGV和工件都在仓库，AGV随机出发，有先后顺序。
2）每台AGV均可运输所有工件且一次只能运输一个工件。
3）AGV的行驶速度恒定不变。
4）每台加工机器的工件缓冲区无限大。
5）AGV完成运输任务后可以停靠在机床旁边，不需要返回仓库。
6）每台机器一次只能加工一个工件且一旦开始加工就不会中断。
7）加工准备时间以及装卸工件的时间算在加工时间中。
8）所有路段同一时刻只允许一台AGV通过，且任意路段可容纳AGV的车身，不存在AGV占用两个车道的情况。
9）同一个工件的工序有先后约束，不同工件之间的工序无约束。
10）不考虑AGV故障、电量等因素，也不考虑机器故障。
11）所有工件都增加一道虚拟工序，加工时间为0，加工机器的位置为仓库位置，便于处理将工件运送回仓库。
1.2 数学模型
根据以上说明 ，在建立模型之前 ，对引入的符号和变量做如下说明 ：
- 最新
- 最热
只看作者