工件带有相容约束性及运输时间的分批排序研究

金世国，张巧利

（1.郑州信息科技职业学院，河南 郑州 450046；2.河南广播电视大学，河南 郑州 450008）

工件带有相容约束性及运输时间的分批排序研究

金世国1，张巧利2

（1.郑州信息科技职业学院，河南 郑州 450046；2.河南广播电视大学，河南 郑州 450008）

近年来，工件带有相容约束性的加工运输问题在物流和供应链管理领域得到了广泛地关注。这里讨论相应的单机平行分批排序问题，首先把工件间的相容约束用图来刻画，进一步给出了问题的复杂性，并对相容约束图为分裂图的情形，给出了时间界为O(n2)的多项式时间算法。

相容约束；单机；平行分批

在排序论中，工件是被加工的对象；机器是提供加工的对象。分批排序问题是指若干个工件可以在同一批加工，加工过程中不允许中断。平行分批排序是指机器可以同时加工多个工件，每批工件同时开工与完工，该批工件中，加工时间的最大者称为批的加工时间。现有一台批处理机和足够多的车辆，n 个工件J1,J2,… ,Jn需要在机器上加工，完工后用车辆将其运送到目的地。每个工件加工时间pj，运输时间qj。其中有的工件可以放在同批中加工，而有的工件不能在同批加工。一批完工后并行地运输。批B的加工时间为

i完工时间用C(Bi)来表示，运输时间 。因而产生这样一个问题：在工件具有这种相容约束的条件下，如何进行分批，如何对这些批排序，可以使得这样的分批排序的目标函数值最小？我们这里考虑目标为工件最后到达顾客时间的情形。把工件的相容约束条件用一个图来刻画．把工件集对应于有n个顶点的图G的顶点集；然后考虑图的边集，任两个顶点连边当且仅当对应的工件是相容。

对于工件带运输时间或单机平行分批排序问题，已经有了很多研究成果。Lawer等证明了离线时是强NP困难的，但是若工件允许被打断此时问题变为了多项式可解，同时当工件到达时间一致时，存在著名的LDT (the longest delivery timefirst)算法，当工件不同时到达时，Kise等证明了LDT算法的竞争比为2。

1 问题的复杂性

团分解问题：给定团G =(V,E)和整数K ≤V，则问图G 的顶点能否被划分为k ≤K个不交的子集合V1,V2,… ,Vk，使得图G[Vi](1 ≤ i ≤k)是图G的一个完全子图。

引理1： 团分解问题是NP困难。

命题1 ：问题1| p− batch; pj=p,qj=q;G|Dmax是NP困难。

证明：显然，该排序问题的判定问题属于NP类。

用团的分解问题来做归结。我们由引理1得知，团分解问题是NP困难的。给团分解问题的一实例G =(V,E)和正整数K，构造1| p− batch; pj=p,qj=q;G|Dmax的判定问题的实例如下：V(G)的n 个顶点分别对应n 个有同一工时p及运输时间q的工件，同时记门槛值为Y = Kp+q。此时，排序问题的判定问题为：是否有平行分批排序π使得Dmax以给定的门槛值作为上界，即Dmax≤Y？如果团分解问题有解，也就是存在一整数k ≤K，使图G的顶点集V(G)被划为k 个不相交的子集且每一子集的导出子图G[Vi](1 ≤ i ≤k)均为图G的完全子图，则排序问题中团Vi视为一批，即有k批，且批序列为一可行排序。明显，Dmax= kp +q ≤Y 是成立的，所有排序问题有解。反之，如果该排序问题有解，也就是存在一可行排序π，满足Dmax≤Y = Kp+q 。不失一般性设则有Dmax=kp + q ≤Y =K p +q，把VBi作为批Bi中工件的顶点集，G[VBi]为图G 的完全子图，那么划分VB1,… ,VBk是团分解问题的一解。

2 相容约束为分裂图时算法

图G =(V,E)为分裂图，是指其顶点集可以分为两个部分：V = X ∪ Y,X ∩ Y =∅ ，其中X为独立集，Y为团，且除G[Y ]内的边外，E还有一些X与Y间的边。这里工件集的相容约束用分裂图G 表示，其中工件集是图G 的顶点集。从而及为工件集。现假设工件加工时间均为p ，xi的运输时间为q(xi)，yj的运输时间为q(yj)。全部工件在一分批机器M上加工，这里批容量无限，且同批加工的工件必须是G的一团。问题为求一分批排序使任务的完工时间最小。

这里，Bi为第i 批的工件集（图G的一个团），第i 批的完工时间为运输时间为先来分析一下工件分批情况。由X ={x1,x2,… ,xm}是独立集知，顶点xi各占一批(该批中还可能有其相邻的顶点)。记xi在Y中的邻集为N(xi)，有xi∪N(xi)是一团，此团或其中部分可做为一批。另外，Y是一团，其任一部分均可作为一批，与xi不相邻的顶点需要单独作为一批，即若则必须占一批。下Y′面我们假设Y′≠∅，如此，方案至少包含m+1批。问题的关键是如何把Y的顶点放入到这些批中，可以使目标函数Dmax最小。然后，简化问题：（1）若存在y ∈N(xi)满足q(y ) ≤q(x)，则工件y可以分到xi在的批B 中，该批的运输时间q(B ) =q(xi)没有变化，对目标函数也没有影响，因此可把这样的顶点给暂时给删去。（2）若存在y ∈Y Y′满足q(y ) ≤q(Y′)，则工件y 可以分到Y′在的批中，该批的运输时间没有变化，对目标函数也没有影响，因此也可以把这样的顶点给暂时删去。

证明：此时m+1批可看成m+1个单独的工件，从而可转化为单机排序问题1||Dmax，用熟知的LDT (the longest delivery time first)规则，就可以得最优解。

下面考虑YY′≠∅的情况，解决如何将Y Y′的顶点添加到m+1批中去。

命题3：取所有工件中运输时间最大的为v*，即（1）如果v*∈X，不失一般性设v*=x1，则有最优解使{x1}是第一批。（2）如果，则有最优解使Y′为第一批。（3）如果记则有最优解使v*与及Y′中具有最大运输时间者位于第一批。

Step 3：如果所有的批都已顺序，那么终止，输出最优排序

Step 4：从未顺序及未分批的所有工件中，挑出运输时间最大的工件v*。（1）若v*∈X，比如v*=xi，则将xi所在的批安排在最前面（未安排顺序的批的第一位）。（2）若v*∈Y′，则将Y′所在的批安排在最前面。（3）若v*∈Y~，则从与v*相邻的顶点及Y′中挑出运输时间最大的，如某个xil或Y′，同时将v*放入它所在的批，将此批排在最前面。令

证明：由命题2及3可知算法的正确性。下面只证明时间复杂性。

算法开始执行时，对所有工件的运输时间q(xi)或q(yj)按照递减的顺序排列，其运行时间为O(n logn)。此时得到及Y′按照LDT顺序排列，算法以下步骤都以此为基础。其次，每一次循环算法都确定出一批顺序，所以循环数≤k≤n。而每一循环中的计算量体现在Step 4的(4．3)，找出与最坏情形需要扫描X 中的所有顶点。故计算量是O(n)。由此，总计算复杂性为

3 结语

工件带有相容约束性及运输时间的单机平行分批排序问题具有很强的实际应用背景，本文对其问题复杂性进行了研究，并对于相容约束为分裂图时的排序问题给出了时间界为O(n2)的多项式时间算法。

[1]唐国春，张峰，罗守成． 现代排序论[M]．上海：上海科学普及出版社,2003：40-42．

[2]Poon C K and Zhang P．Minimizing makespan in batch machine scheduling[J]．Algorithms, 2004, 39:155-174．

[3]Garey M R and Johnson D S．Computers and Intractability: A Guide to the Theory of NP-Completeness[M]． W． H． Freeman and Company, New York, 1979．

TB114.1

A

1671-0711（2017）08（下）-0226-02

河南省教育厅科学技术研究重点项目(15A110003)。