并行变邻域搜索下的订单接收与流水车间调度

郑 凡，雷德明

(武汉理工大学 自动化学院，湖北 武汉430070)

面对竞争日益激烈的态势，越来越多的制造企业开始采用订单型生产模式来满足客户个性化的产品需求。客户一般要求制造商在规定的交货期内完成订单生产，否则制造商将承担经济和市场信誉等方面的损失［1］。因此，在有限的生产能力和严格交货要求下，制造商必须同时进行订单接收和订单调度的决策以实现其总收益的最大化［2］。订单接收与调度(OAS)问题是一种联合决策问题，属于NP -hard 问题，它可以分解成两个子问题：①企业要综合考虑来决策能够接收哪些订单;②已接收的订单如何安排加工顺序。这两个子问题相互影响和制约，最终目的是使企业在经济或信誉方面获得最大收益［3-4］。

近年来，考虑订单接收的车间调度问题受到研究者的广泛关注，研究者分别研究了单机、并行机和流水车间等制造环境下的OAS 问题［5-9］，目前关于流水车间环境下的OAS 问题的研究较少。XIAO［10］针对置换流水车间环境下的OAS 问题，运用一种基于偏序优化的模拟退火算法以解决问题的整数规划模型并得到近似最优解。WANG等［11］运用一种改进的人工蜂群算法解决了双机流水车间环境下的OAS 问题。WANG 等［12］针对同样的问题又提出了一种启发式算法和分枝定界算法。变邻域搜索(VNS)算法作为一种改进型启发式算法，在求解大规模的组合优化问题上有较为明显的优势，已被广泛应用于生产调度领域并具有较强的搜索优势。笔者研究流水车间环境下的OAS 问题，并提出一种新型的并行变邻域搜索(PVNS)算法。将PVNS 与遗传算法和蜂群算法进行了大量实例比较，实验结果表明，PVNS 对所研究的问题具有良好的优化效果。

1 问题描述

流水车间环境下的OAS 问题描述如下：存在n个订单和m台机器，订单集合O={O1，O2，…，On}，机器集合M={M1，M2，…，Mm}。每个订单按如下顺序访问所有的机器：先在M1上加工，再在M2上加工，依次进行直到所有机器访问完毕。每个订单在每台机器上只加工一次，每台机器同一时间只能加工一个订单，各订单在各机器上的加工时间已知。即第i个订单Oi需要完成m道工序，这些工序由(Oi1，Oi2，…，Oim)组成，且订单Oi的实际收益r*i由该订单的最大收益ri、交货期di、加工完成时间ci和延期惩罚权重ωi等共同决定。

OAS 问题由订单接收子问题和已接收订单的调度子问题组成。其中订单接收子问题指如何从n个订单中选择j个订单问题;调度子问题则指对已接收的订单安排加工顺序问题。在一个订货系统中，订单的接收决策受限于有限的生产能力和交货时间的要求，已接收订单的调度决策由其开始加工时间、加工时间和最大收益等决定。

OAS 问题的目标是通过完成订单的接收决策和合理安排已接收订单的加工顺序使订单生产的实际总收益最大化。

式中：Rtotal为订单生产的实际总收益;yi取值为0 或1，取1 表示订单i被接收，取0 则表示被拒绝;∑ni=1yi=j，j为所接收订单总数。

2 基本变邻域搜索算法

变邻域搜索算法(VNS)是一种启发式策略，它具有方法简单、容易实现和无需调整参数等优点，该方法已被成功应用于许多组合优化问题。相比于传统方法的单一邻域结构，VNS 首先预定义一系列的邻域结构，并在搜索过程中系统性地不断扩大邻域搜索范围，直到获得更好的解［13］。

基本VNS 的算法流程如下：

(1)定义一系列的邻域结构Nk，k=1，2，…，kmax，产生一个初始解x，并令其为当前解;

(2)重复下列过程至算法终止;

(3)令k=1;

(4)重复下列过程至算法k=kmax：①扰动。由当前解x在其第k种邻域Nk内随机产生 一个新解x';②局部搜索。以x'为初值应用邻域搜索方法获得解x″;③如果x″优于x，则x=x″，否则k=k+1。

由VNS 的算法流程可以看出，确定邻域结构及其数量，确定各邻域结构在搜索中应用的次序及其改变的策略是VNS 要解决的基本问题。

3 并行变邻域搜索算法

3.1 基于订单编号的编码和解码机制

笔者利用双串来表示OAS 问题的解。对于流水车间环境下具有n个订单的OAS 问题，串v1={θ1，θ2，…，θn}表示订单的调度情况，其中θi∈{1，2，…，n}，{θ1，θ2，…，θn}={1，2，…，n};串v2={y1，y2，…，yn}表示订单的接收情况。

解码过程如下：首先根据v2确定被接收的订单;然后从v1中剔除被拒绝的订单，剩余部分则为已接受订单的排列;最后根据已接收订单的排列顺序，依次安排这些订单的加工，再结合每个订单的惩罚权重算出每个订单的收益，进而得出OAS 问题的目标函数值即所有订单的实际总收益。

假设PVNS 处理器的个数为npr，随机产生npr个初始解，每个处理器采用一个初始解。

3.2 邻域结构

邻域结构是PVNS 产生新解的主要方式。在利用PVNS 求解OAS 问题时，邻域结构使算法从当前解转移到其相邻解，并保证解的可行性。动态地改变邻域结构以使搜索过程顺利跳出局部最优，确保得到的解近似于全局最优解。根据上述编码机制，设计了6 种邻域结构。

(1)邻域结构Ns1。邻域结构Ns1通过改变处理器当前解的调度串来构造邻域解。在接收串不变的情况下，Ns1从调度串中随机选择两个不同的位置，并将两个位置上的订单编号进行互换来产生邻域解。

(2)邻域结构Ns2。邻域结构Ns2通过改变处理器当前解的接收串来产生邻域解。Ns2通过从接收串中随机选择两个不同的位置，并将两个位置上的数字(1 或0)进行互换来产生邻域解，且调度串保持不变。

(3)邻域结构Ns3。邻域结构Ns3是邻域结构Ns2的进一步加强。在调度串不变的情况下，从接收串中随机选择4 个不同的位置，并将这4 个位置上的订单编号两两互换，这样扩大了邻域搜索范围，使搜索更加丰富。

(4)邻域结构Ns4。邻域结构Ns4通过倒置处理器当前解的调度串的部分订单编号来构造邻域解。从调度串中随机选择两个不同的位置，并将两个位置之间的订单编号进行倒置产生邻域解，且接收串v2保持不变。

(5)邻域结构Ns5。邻域结构Ns5通过插入操作改变处理器当前解的调度串来构造邻域解。在接收串保持不变的情况下，从调度串中随机选择两个位置j和k(k＞j+1)，并将k位置上的订单编号插入到j位置，且j位置到k-1 位置上的订单编号依次向后移动一位。

(6)邻域结构Ns6。邻域结构Ns6是邻域结构Ns1的进一步加强。其具体过程如下：对于处理器的当前解，从调度串中随机选择两个不同的位置，然后将调度串分割为左、中、右3 个部分，再将左右两部分的订单编号子串进行互换，且接收串保持不变。

3.3 PVNS 算法

如何在最短时间内获得最优解或接近最优解是解决OAS 问题要面对的首要难题。为了解决这个难题，将并行搜索策略视为一种可行方案。并行搜索策略下的启发式算法允许同时运行多个邻域结构来搜索解空间，且各邻域结构在搜索中应用的数目和次序各不相同。并行化的应用增加了对解空间的探测，避免了算法陷入局部最优，从而大大提升了算法的寻优能力。为了有效地解决OAS 问题，提出了一种新型的并行变邻域搜索(PVNS)算法。

笔者提出的基于流水车间环境下OAS 问题的PVNS 的实现流程如下：

(1)初始化。定义用于扰动的邻域结构集合P={Ns1，Ns4，Ns5，Ns6}和用于局部搜索的邻域结构集合L={Ns1，Ns2，Ns3，Ns4，Ns5，Ns6}，以及处理器的个数，为每个处理器确定要使用的邻域结构和相应的次序;

(2)产生npr个初始解，确定精英解x*;

(3)选择算法终止条件(设置最大迭代次数)。重复下列过程直至算法结束：①For 每个并行处理器的当前解xi执行如下过程mmax次：扰动过程。随机从集合P中选择邻域结构，产生一个解xi∈Nsk(xi);局部搜索。根据该处理器的邻域结构及其使用次序，确定相应的邻域结构，产生新解¯xi;若f(¯xi)＞f(xi)则xi←¯xi，更新精英解x*;否则当前解保持不变。②执行上述过程α 次，指定两个处理器互换其当前解。

PVNS 的并行变邻域搜索阶段的设计是PVNS 的重要内容，是PVNS 能否快速找到最优解的关键。笔者设置npr个处理器，每个处理器采用VNS 对当前解实施扰动和局部搜索，用于局部搜索的邻域结构各有不同，使用次序也有差异。部分处理器可采用只改变调度串的邻域结构，在不改变订单接收情况下通过变邻域搜索获得更好的解;其他处理器则采用同时改变双串的邻域结构，虽然改变了订单的接收状况，但扩大了搜索空间，增大了邻域搜索后所得当前解的多样性。

PVNS 中处理器当前解的互换是指处理器独立运行一定迭代次数后，处理器的当前解两两互换的过程。这个阶段的设计能有效地避免算法陷入局部最优，大大增强PVNS 全局优化能力。该阶段的互换过程如下：每个处理器迭代α 次后获得当前解xi，解码后获得相应的目标值f(xi)，再按照目标值的大小将npr个当前解xi依次排列，最后将该序列首尾两两互换即可。当算法的最大迭代次数到达指定值时，算法停止运行，并输出最终的精英解x*。

4 实验测试及结果分析

4.1 实例描述

为了测试及比较PVNS 的性能，选择了7 个计算实例，这7 个实例的订单数目分别为10，20，30，40，50，60 及80。对第i个订单Oi，它的最大收益ri为［100，300］范围内的随机数，它在每台机器上的加工时间为［5，10］范围内的随机数。笔者将每个订单的交货期设置成其在所有机器上的加工时间之和的ρ 倍。这7 个实例每个订单的值分别为1.5，1.5，2.0，3.0，4.0，8.0，8.0 。因为只有ρ取适当的值时，大多数订单才能在交货期内完成所有加工，从而保证所得到的交货期有意义。通过大量的计算实验，获得每个实例相应的ρ 值。另外设置了3 种不同的惩罚权重ω：0.3，0.6，0.9。随着订单数n的增加，实验的计算难度和时间随之增加。设置参数ρ 和ω 后，每种算法运行20 次，从而获得实验所需结果：最优解max(实际总收益最大的解)，最差解min(实际总收益最小的解)，平均解avg及运行时间t。

4.2 算法的比较

笔者选择GA 和ABC 作为比较对象。GA 作为一种经典的进化算法，具有隐含并行性和全局解空间搜索两大显著特点，其自组织、自适应、自学习和群体进化能力使其被广泛应用于大规模复杂优化问题中;ABC 作为一种新兴的智能算法，机制简单，参数少，在各种NP -hard 问题上取得了较好的优化效果。针对流水车间环境下的OAS 问题，采用改进的PVNS、GA 和ABC，进行比较实验的3 种算法的编码解码机制和算法的终止条件已知且相同。

4.3 实验结果

所采用实验平台是一台2.50 GHz 主频和4 G 内存配置的笔记本电脑。笔记本电脑的操作系统是Windows 7 系统，且Visual C+ + 6.0 软件实现了所有算法的编译。

在PVNS 中，处理器的个数、每个处理器邻域结构的使用类型及次序和其局部搜索中邻域搜索的最大迭代次数由大量的计算实验决定。根据对算法不同参数值的测试试验及其结果，PVNS 的参数设置如下：处理器的个数npr=4;每个处理器邻域搜索的最大迭代次数nmax=850。

在比较实验中，总迭代次数的设定十分关键，如果总迭代次数太小，每种算法的邻域搜索不充分将导致算法无法收敛从而无法得到最优解;反之，虽然能获得最优解但大大增加了计算时间，影响了算法的效率。通过在其他参数不变的情况下改变总迭代次数观察实际总收益变化的实验来得到合适的总迭代次数。即为不同订单数目的OAS 问题选择适当的总迭代次数：订单数目为10和20 时，实例的总迭代次数为20 000;订单数目为30、40 和50 时，实例的总迭代次数为60 000;订单数目为60 和80 时，实例的总迭代次数则为80 000。当惩罚权重ω =0.6 时，3 种算法的实验结果如表1 所示。另外，为了更好地比较大规模订单数目下PVNS、GA 和ABC 这3 种算法的优化能力，进行了如下实验：在n=60，ρ =8，ω =0.9的参数条件下，不断增加总迭代次数，记录下不同总迭代次数下3 种算法获得的实际总收益的最优解。实验结果如图1 和图2 所示。

表1 惩罚权重为0.6 时3 种算法的实验结果

图1 PVNS 与GA 实验比较图

图2 PVNS 和ABC 实验比较图

从实验结果可以看出，PVNS 的寻优能力优于GA，且略胜于ABC。GA 不能优化流水车间大规模订单下的OAS 问题的原因如下：GA 对解空间的探索能力有限，易收敛到局部最优解;GA 的参数较多，例如交叉率和变异率，且这些参数的选择严重影响最优解的结果;GA 算法实现比较复杂，计算时间长(订单数目增加时，该问题尤为严重)。而ABC 则主要受限于其较差的全局优化能力，从算法解的性质看，ABC 是在寻找一个比较好的局部最优解，而不是全局最优解。因此，PVNS 相比其他两种算法拥有参数少、结构简单、易于实现和局部搜索充分等优点，具有全局优化能力。

5 结论

笔者研究了多机器流水车间环境下订单接收与生产调度问题，提出了一种并行变邻域搜索算法。在大量的不同订单数目的实例实验中，证明PVNS 算法具有优秀的优化能力和优化效果。其原因在于：①运用双串来表示问题的解决方案，大大提高了算法的可行性和操作能力;②PVNS 的结构简单易于实现;③多邻域搜索结构的设计使邻域搜索更加灵活多变，互换、插入和倒置等操作的局部特性使每个处理器能更好地逼近最优解;④PVNS 算法中多处理器当前解的互换阶段扩大了解空间，有效避免陷入局部优化，使PVNS 具有良好的全局优化能力。

［1］ 唐恒永，赵传立.排序引论［M］.北京：科学出版社，2002：3 -12.

［2］ 刘民，吴澄. 制造过程智能优化调度算法及其应用［M］.北京：国防工业出版社，2008：36 -45.

［3］ 雷德明. 现代制造系统智能调度技术及其应用［M］.北京：中国电力出版社，2010：56 -98.

［4］ ZHANG L，LU L，YUAN J.Single machine scheduling with release dates and rejection［J］. European Journal of Operational Research，2009(198)：975 -978.

［5］ LU L，ZHANG L，YUAN J. The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan［J］. Theoretical Computer Science，2009(396)：283 -289.

［6］ OGUZ C，SALMAN F S，YALCIN Z B. Order acceptance and scheduling decisions in make - to - order systems［J］. International Journal of Production Economics，2010，125(1)：200 -211.

［7］ CESARET B，OGUZ C.A tabu search algorithm for order acceptance and scheduling［J］.Computers ＆ Operations Research，2012，39(6)：1197 -1205.

［8］ SU N，ZHANG M J，MARK J，et al.Learning reusable initial solutions for multi - objective order acceptance and scheduling problems with genetic programming［J］. European Conference on Genetic Programming，2013(7831)：157 -168.

［9］ LIN S W，YING K C.Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm［J］.Journal of the Operational Research Society，2013，64(2)：293 -311.

［10］ XIAO Y Y.Permutation flow shop scheduling with order acceptance and weighted tardiness［J］.Applied Mathematics and Computation，2012，218(15)：7911-7926.

［11］ WANG X L，XIE X Z.A modified artificial bee colony algorithm for order acceptance in two -machine flow shops［J］. International Journal of Production Economics，2013，141(1)：14 -23.

［12］ WANG X L，XIE X Z.Order acceptance and scheduling in a two-machine flowshop［J］.International Journal of Production Economics，2013，141(1)：366-376.

［13］ 王凌.车间调度及其遗传算法［M］.北京：清华大学出版社，2003：103 -123.