生产运输调度算法研究

卓雪雪 朱苍璐 郭杰 钱鹏

【摘  要】生产调度问题一直备受社会关注，尤其是制造业，因此，经典调度问题被研究学者提出，即实现一台机器加工一个工件的功能。随着社会对产品的需求量不断增加，实现一台机器同时加工多个工件的批调度问题被相继提出，其中差异工件尺寸调度问题最为复杂。论文研究的生产运输调度算法的复杂度超过了以上所有的批调度问题，涉及批调度和产品交付2个阶段，这是一个强NP难问题，深入研究具有重大意义。

【Abstract】The problem of production scheduling attracted much social attention， especially in manufacturing industry. Therefore， the classical scheduling problem is proposed by researchers， that is， realizing the function of one machine processing one workpiece. As the society's demand for products continues to increase， the batch scheduling problem to realize the simultaneous processing of multiple workpieces by one machine has been proposed one after another， among which the scheduling problem of different workpiece sizes is the most complex. The complexity of the algorithms of production and transportation scheduling studied in this paper exceeds all the above batch scheduling problems， involving two stages： batch scheduling and product delivery. This is a strong NP hard problem， and in-depth research is of great significance.

【關键词】平行批处理机;不同尺寸的工件;蚁群优化算法

【Keywords】parallel batch processing machine; workpieces of different sizes; ant colony optimization algorithm

【中图分类号】F273;TP18                                             【文献标志码】A                                                 【文章编号】1673-1069（2021）11-0124-04

1 引言

国内外研究学者首先提出了经典调度问题，即单机调度问题，如Tang[1]研究了改进的差分进化算法用以获得更好的解。但是随着社会的发展，单机调度问题不能满足社会的需要，随后平行机批调度问题被提出。Chang等[2]在研究了模拟退火算法处理平行批处理机调度问题。生产制造阶段固然重要，然而从企业利益角度出发，产品交付、最小化运输成本也非常重要。例如，Koh等[3]研究了订单的加工、包装以及交付的整个流程，最小化分销成本。Ghazvini等[4]研究了单机加工单车交付的问题。在本文中，研究了工件尺寸不同的平行机调度问题，同时，研究了加工完成的工件的交付问题。这种2个阶段结合的问题很少被研究，因此，本研究的集成调度具有重要意义。

2 研究内容

3 算法研究

3.1 下界算法

本文提出的下界算法主要是为了与启发式算法进行性能比较。下面详细介绍该算法过程：

算法1：下界算法（LB）

①将每个工件Jj单位化，即把每个工件分成若干个单位大小的工件，每个单位工件的权重为wj/sj。因此，得到一个新的单位大小的工件集合，称为JU。

②把工件集JU中的单位工件按照wj/sj的值降序排序，得到一个有序的工件集。

③把有序的工件集JU按照批的容量的s进行分批，得到批的列表BU。

④调用DLV（BU）求出目标值。

下界算法中的第4步提到的DLV（B）算法是本文研究的调度算法的第2个阶段，即运输。该算法具体步骤如下：

算法2：DLV（B）

①计算每个批Bki中工件权值之和，同时存储于Wki中。

②计算每个批Bki的完工时间，同时存储于Cki中。

③BD←0，TWD←0。

④l←1到d。

h←BD+1;当（Cki≤VTl）且（h-BD）≤VNl×V时开始循环。

TWD←TDW+Wki×VTl;h←h+1。

循环结束。

⑤输出目标值TWD。

下面通过一个例子对此算法进行详细说明，假设有5个工件，p=1表示工件加工时间为1，VT1=1，VT2=2表示有2次发车，VN1=2，VN2=1表示2种车辆数，V=1表示每辆车1次只可以运输1个批。S=5表示机器的容量为5。工件单位化，这里举例说明，如果工件Jj的尺寸为2，权值为3，则对其单位化之后，分成2个工件尺寸为1的工件，同时，工件的权值按单位化的比例进行分配，单位化的2个工件的权值各为1.5。例中便对这12个单位化的工件按照wj/sj的值进行降序排。然后根据机器尺寸S=5进行分批。

3.2 启发式算法

文中的启发式算法用来与元启发式算法作性能对比。下面详细介绍该算法的步骤：

算法3：启发式算法（H）

①根据工件的比值wj/sj对工件降序排序。

②根据最佳适应分配原则（BFF）对工件进行分批。

③调用DLV（B）获得解，并输出目标值。

把上文例子中的5个工件用启发式算法进行分批，分批结果是批B1是满批，而B2和B3不满，造成空间浪费，影响了算法的性能。

3.3 两种基于ACO的算法

本文主要介绍ACO算法与MMAS算法以及启发式算法H，三者进行性能对比，在元启发式算法中，信息素对构建解很重要。

3.3.1 信息素

文中，当前批Bki和候选工件Jj之间的信息素，记作τj，ki，定义为式（1）。

（1）

为有效探索蚁群的搜索空间，信息素更新尤为重要，信息素更新公式定义为式（2）：

τg，j（t+1）=（1-ρ）·τg，j（t）+mg，j（t）·Δτg，j（t）       （2）

3.3.2 启发式信息

根据本文研究的问题，为寻找更优解我们优先加工权值大的工件，但是也要考虑尺寸，如果工件的尺寸过于大，那么这个工件是不适合优先加工的，因为此工件的wj/sj的权值不一定是最大的。当然，如果2个工件的wj/sj的权值相同，我们要优先对尺寸小的分批。本文设计了3个独立的启发式信息，定义如下。

η1=wj/sj         （3）

η2=1/sj         （4）

（5）

3.3.3 候选列表

如果不构建候选列表，蚂蚁就需要不停地搜索下一个即将被调度的工件，这样会浪费很多时间，因此，这里我们为蚂蚁构建一个候选列表，节约时间，其构造如下：

（6）

3.3.4 解的构建

元启发式算法中解的构建至关重要。第一，每只蚂蚁为自己创建一个空批，随后选工件入批，这些工件来自候选列表，而且第1个被选中的工件是随机的且没有被蚂蚁调度的，每选择一个工件入批就要及时更新候选列表。第二，蚂蚁开始选择即将入批的第2个工件，入批的第2个工件至最后1个工件都是根据状态转移概率的大小进行选择的。直到候选列表中所有的工件被选完。在蚂蚁选择工件入批的过程中，会判断当前批是否已满，如果当前批已满，则构建新批，只有把全部工件都完成调度方可得到完整的解决方案。重复以上步骤，直到每只蚂蚁都完成了最大迭代次数的解的构建。算法如下所述。

算法4：CL算法

①初始化TB←[1，2，…，n]。

②当TB≠[0，0，…，0]。

每只蚂蚁构建一个空批Bki。每只蚂蚁随机选择一个没有被调度的工件Jj放到批Bki中，然后更新向量TBj←0，根据式（2）生成当前批的候选列表Lki。当Lki≠？准开始循环。

蚂蚁根据概率Pj，ki从候选列表Lki中选择Jj加入当前批;

（7）

更新向量TBj←0;Lki←Lki＼{Jj}。

③计算出目标值，得出解决方案。

3.3.5 局部优化

此局部优化算法是基于每只螞蚁的每个解决方案进行工件交换以及对交换工件后的批进行排序，优化解的质量，从而保证权值较大的工件优先发车，第一时间运输到客户手中。首先，检查优先发车的批与后面发车的批中是否存在权值相同，但是尺寸不同的工件。假设存在这样的工件，在保证不超出批的容量情况下，把尺寸小的工件交换到优先发车的批中，此时一定要注意，大尺寸的工件被置换到后面发车的批中不能超过此批的容量，否则不予置换。第一步的作用是可以为优先发车的批空出更多的剩余空间。其次，在第一步的基础上把后发车的批中的合适工件移动到优先发车的批中，且不超出每个批的剩余空间。最后，根据批权值从小到大排序置换工件的批，最终确保权值大的批优先送到客户手中。具体算法描述如下：

算法5：LO算法

3.3.6 HACO算法

HACO是一种迭代搜索算法，假设蚁群有20只蚂蚁，迭代100次，在第一代循环时就会生成20个解，其中每个解都会进行局部优化，得到新的批序列后进行运输，最后得到运输结果值。在这20个运输结果值中挑选一个最好的作为当代最优解，即第1代全局最优解。然后用第1代中的最优解对信息素进行更新，开始第2代循环，按照以上过程循环100代，最后从得到的100个全局最优解中选择一个最好的作为最终的解。算法过程如下：

算法6：HACO算法

①参数初始化。②t←0。③如果t

3.3.7 MMAS算法

MMAS算法是在ACO算法的基礎上，从3个方面进行改进。第一，为了使蚂蚁能够更好地探索，从而构建更好的解，把信息素初始化为最大值;第二，除了最优解之外，不允许其他任何解更新信息素;第三，信息素过高或者过低有可能发生搜索停滞，造成构建的解陷入局部最优，而不是全局最优，因此，为信息素设定一个范围。

由于2个蚁群算法求解过程的很多步骤是一样的，所以这里只描述二者不同的步骤：

③如果目标值在D代没有改进，则把信息素的值改为τmax。

4 仿真实验与结果分析

4.1 实验设置

本文列举2组实例N1M1P1、N1M1P2进行实验验证，其中，N1M1P1随机生成10个算例，N1M1P2同样随机生成10个算例，假设工件数为N1=100，机器数为M1=2，工件加工时间分为2种，第一种P1=3，第二种P2=5。

4.2 实验结果及分析

对启发式算法H、蚁群算法HACO、最大最小蚂蚁算法三者进行性能对比，图1得到的是加工时间P=3的实验对比结果，图2得到的是加工时间P=5的实验对比结果，从2个图中得出以下结论：第一，工件加工时间从3延长到5，3个算法的性能几乎没有变化，因此，时间对算法的性能影响较小;第二，3个算法中，启发式算法H的性能最差，ACO算法的性能远远优于启发式算法，尽管运行时间大于启发式算法，但是在可接受的合理范围内，与蚁群算法相比MMAS算法性能较好，相应的运行时间有所增加;第三，2个实例证明2个蚁群算法可以构建出更好的解，这是启发式算法无法做到的，图中也证明了MMAS算法性能优于HACO算法的性能，HACO算法的性能远远优于启发式算法H的性能。

5 结语与展望

本文主要研究的是2个阶段的批调度算法，不同于以往研究学者，或者只研究批调度阶段，或者只研究产品运输阶段，而是根据现实社会的需要把2个阶段结合起来，为企业节约成本，促进利益最大化。在此提出了3个算法，即启发式算法H、蚁群算法HACO、最大最小蚂蚁算法MMAS，并通过实例证明MMAS算法构建的解的性能最好，优于蚁群算法HACO，启发式算法相比前两者性能明显不足。

当然相较于社会的快速发展，本文的研究是不够的，我们可以考虑工件加工时间不同，机器加工时间不同，车容量不同，且涵盖发车延迟的问题研究。

【参考文献】

【1】Lixin Tang，Yue Zhao，Jiyin Liu.An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production [J]. IEEE Trans-actions on Evolutionary Computation，2014（5）：209-225.

【2】P.Y. Chang，P. Damodaran，S. Melouk.Minimizing makespan on parallel batch processing machines[J].International Journal of Production Research，2004，42（19）：4211-4220.

【3】Shie-Gheun Koh，Pyung-Hoi Koo，Jae-Won Ha，et al.Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families[J].International Journal of Production Research，2004，42（19）：4091-4107.

【4】Fariborz Jolai Ghazvini，Lionel Dupont.Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes[J].International Journal of Production Economics，1998，55（3）：273-280.