分支定界算法求解带有释放时间的单机双代理调度问题

梁建恒, 薛含钰, 白丹宇, 苗蕴慧

(1.沈阳化工大学 经济与管理学院，辽宁 沈阳 110142; 2.大连海事大学 航运经济与管理学院，辽宁 大连 116026)

0 引言

本文研究带有释放时间的单机双代理调度问题，其中来自两个不同代理的工件需要在同一台机器上加工，目标是求得一个可行调度，使得两个代理的最大完工时间之和极小化。与经典的调度模型不同，双代理调度模型从客户的角度考虑优化目标。例如，富士康工厂同时为苹果和三星两家公司代工组装不同型号的手机，为了使两个公司各自制定的目标都尽可能最优化，采用双代理调度模型安排生产是最好的方案之一。

考虑到该问题具有NP困难性，即在多项式时间内无法求得问题的最优解，因此采用近似与精确算法分别求解不同规模问题。针对大规模问题，提出了优势代理优先启发式算法并证明了其渐近最优性。针对小规模问题，提出了分支定界算法进行最优求解。为了提高算法性能，加快求解速度，设计了基于释放时间的分支策略和基于可中断的问题下界。随机数值测试验证了分支定界算法的有效性。

本文的其余部分组织如下：第一节为文献综述，简要介绍相关研究结果，第二节建立了整数规划模型，第三节分析了启发式算法的渐近最优性，第四节介绍了分支定界算法，第五节为数值实验结果，最后得出本文结论。

1 文献综述

为了方便起见，本文采用由Graham等[1]提出的三参数表示法描述调度问题。最初，Agnetis等[2]在生产调度模型中引入了多代理模式。据作者所知，目前多代理调度问题按照机器类型分类主要有三种形式：单机多代理，并行机多代理及流水车间多代理。本文主要针对单机多代理调度问题进行综述。

2 混合整数规划模型

Nx={1,2,…,nx}，代理x∈{a,b}。

Y=充分大的正数。

单机双代理调度问题整数规划模型：

约束条件：

(1)

(2)

(3)

(4)

(5)

(6)

约束(1)和(2)确保每个工件在给定排序中具有唯一性。约束(3)保证工件满足设定的加工要求。约束(4)是工件加工顺序的约束，排在后面的工件都必须等排在前面的工件完工才能开始加工。约束(5)限制加工先后顺序和每个相邻工件的连续关系。约束(6)设定0-1变量和非负限制。

3 启发式算法渐近分析

ADA启发式：

将两个代理中的工件分别采用先到先加工规则进行排序，选择其中目标函数值较小的代理作为优势代理。一旦机器出现空闲时，在所有可用工件中优先选择优势代理中的工件进行加工。若无工件可用，则保持机器空闲直至有工件释放。

证明请参见文献[12]中关于算法1最优性的证明过程。证毕

定理1对于带有释放时间的单机双代理极小化最大完工时间和问题的实例，有

ZADA-ZPADA

证明对于给定的序列，其中最后完工代理的目标值与序列无关，因此优势代理会引起可中断与不可中断排序之间的差异。显然，干扰工件必定是非优势代理中最后中断的工件。令a代理为优先代理，将干扰工件表示为jb，那么

(7)

ZOPT表示最优目标值。

ZADA-ZOPT≤ZADA-ZPADA

(8)

根据定理1，得出(8)式中最后一个不等号成立。将不等式两端同时除以n并取极限，有

(9)

整理(9)可得定理结论。证毕

4 分支定界算法

分支定界算法是一种基于枚举思想的优化算法，通过系统搜索解空间求得最优解。分支定界算法的性能主要取决于其分支策略和下界的效果，用以剪掉更多的分支节点加快计算速度。通常分支定界算法包括深度优先和广度优先搜索方法。本文主要采用深度优先搜索来寻找搜索树上的有效节点。根节点Ø在第0层上表示一个空集合，剩余的每个节点位于τ层部分序列为π(τ)=([1]，[2]，…，[τ])，工件[j]在机器上第j个位置加工，1≤j≤τ，1≤τ≤n。下面分别给出有效的分支策略、下界和算法框架。

4.1 分支策略

显然，如果人为延迟可用工件的开始加工时间，则会引起可行解的目标函数值恶化。基于此思想，可以得到以下性质。

性质1假设已经排好了j-1个工件的加工顺序，接下来准备加工工件jx。若存在工件qx满足

则剩下的工件会被延迟加工且目标函数值将会变大，式中N′表示未排序工件的集合，1≤j≤n，x∈{a,b}。

证明显然，工件qx可以在工件jx之前加工而不延迟工件jx的开始加工时间。否则N′中工件的开始加工时间会被延迟，目标函数值会变大。证毕

证明(i)的结论可直接由先到先加工规则求解1|rj|Cmax问题的最优性求得。(ii)可通过工件交换得出结论。证毕

因此，结合性质1和2可以给出分支定界算法的分支策略，即：若j-1工件已经排在搜索树中的j-1层，当且仅当满足分支规则时，工件jx∈N被删除。在分支的过程中，该规则可以有效地删除多个节点，并显著降低计算量。

4.2 有效下界

在分支定界算法中，剪支的多少主要取决于下界的有效性。若某节点的下界不小于当前最好上界，则剪掉该节点，节省运行时间。设计下界是分支定界算法的核心。下面介绍下界的计算规则。

(10)

4.3 算法框架

(1)初始化：设置变量的初始值，节点层次τ=0，未排工件集合N′=N，分支节点集合G0=Ø，加工序列π=Ø。按照ADA启发式计算初始上界ZUB。

(7)结束：算法终止，当前的上界对应的序列就是最优解。

5 计算结果

本文通过一系列数值仿真验证所提出算法的性能。算法采用C语言编写，Visual Studion 2010 编译。实验使用的电脑配置为：Intel(R)Core(TM)i5- 4590(3.3GHz)CPU，4.00GB内存，460GB硬盘，操作系统为Windows 7(64位)旗舰版。每次实验中，工件的加工时间与释放时间分别通过离散均匀分布[1,10]与[0,5n]随机生成，其中需要保证至少有一个工件的释放时间为0。

分支定界算法是基于枚举的搜索方法，只适用于求解小规模问题。本文测试的问题规模分别为15,20,25,30个工件，每种问题规模下进行5次独立实验，共20组实验。为了说明分支定界算法的优良性能，对于同一问题实例，分别采用分支定界算法和CPLEX软件进行求解，记录各自的运行时间和最优值。若半小时(1800s)内无法求得最优解，则输出当前最好解进行比较，实验结果详见表1。

表1 分支定界实验结果

表1中的数据分别为分支定界算法和CPLEX求得的(当前)最优值和CPU时间。实验结果表明分支定界算法能够在0.1秒内最优求解50%的实例，CPU时间范围是[0.003,82.462]秒。另一方面，CPLEX能够在[1,5]秒内最优求解15%的实例，CPU时间范围是[1.4125,21.5892]秒。显然，CPLEX的求解时间明显长于分支定界算法所花费的时间。除此之外，对于75%的问题实例，CPLEX求得的目标函数值远远大于分支定界算法的计算结果。以上结果充分表明了分支定界算法的优越性。

为了验证ADA启发式的渐近最优性，本文将测试的问题规模设定为500, 1000, 1500, 2000个工件，每种问题规模下进行10次独立实验，记录每次实验求得的目标值间隙OGP=(目标函数值-下界值)/下界值×100%，并将平均值记录在表2中。

通过表2中的数据，可以看出随着工件数增加，OGP值越来越接近零，即启发式算法的目标值与问题下界之间的间隙越来越小。由此，能够断定ADA启发式具有渐近最优性。

表2 ADA启发式渐近最优性实验结果(%)

6 结论

本文研究了用分支定界算法求解带有释放时间的单机双代理调度问题。针对大规模问题，提出了ADA启发式算法进行近似求解，并证明了渐近最优性。针对小规模问题，设计了分支定界算法进行最优求解，其中基于释放时间的分支规则和基于加工中断的下界有效地减少了实际运算量，从而加快了求解速度。

在未来的研究中，针对分支定界算法，将给出更有效的剪支规则进一步缩小搜索空间范围。此外，尝试结合有效的改进策略，利用智能优化算法求解中等规模问题，获得高质量的满意解。