带冲突约束的两台专用机器调度问题

龚 悦，张 安，陈光亭，李好好，陈 永

(1.杭州电子科技大学理学院，浙江 杭州 310018；2.台州学院电子与信息工程学院，浙江 台州 318000；3.浙江财经大学数据科学学院，浙江 杭州 310018)

0 引 言

并行专用机器调度问题广泛存在于各类制造业，更优的调度策略有助于企业减少成本。Goemans[1]研究并行专用机器调度问题，并针对极小化最大完工时间的目标提出一个近似比为7/6的近似算法。“并行专用机器”一词意味着每个作业都有1个专门的机器用于处理该作业。如果机器的数量是任意的且仅有1个非共享资源，该问题是NP-难的[2]。随后，Kellerer等[3]进一步证明了当有2种类型的资源，且每种类型的资源恰好有2个单位，每个作业都将消耗2个单位的资源情况下，2台并行专用机器及多台并行专用机器的调度问题仍是NP-难的。Even等[4]针对m台机器和单位作业的情形，证明了任何确定性在线算法的近似比至少为2-1/m；在预先已知作业个数的情况下，还提出了一个近似比为2-1/7的在线算法。即使专用机器上已知作业序列，上述提到的几个调度问题仍是NP-难的[5-8]。本文讨论其中1台机器工作序列已知的2台专用机器的调度问题。

1 算法设计与分析

实际生产中，每个作业对加工资源都有特定需求，如熟练的技术人员或专用工具。当某些作业对特定资源的总需求超过供应量时，这些作业之间就产生冲突。在任何时刻，2个相互冲突的作业不允许同时进行加工。对并行机器调度施加这样的限制是合理的，因为在制造业或服务业中资源是有限的。在带有冲突约束的条件下，调度规定了将机器、时间间隔和资源分配给具有冲突约束的作业。本文研究该问题的一个变体，即其中专用机器M1上作业的加工顺序已经给出，目标为极小化最大完工时间。由于该问题是NP-难的，下面给出求解该问题的多项式时间近似算法并从理论上分析得到算法的近似比。

假设2台并行专用机器M1和M2分别用于处理2个不相交的作业集N1={J1,1,J1,2,…,J1,n1}，N2={J2,1,J2,2,…,J2,n2}，其中n1，n2分别表示2个集合中作业的个数。任何1台机器在同一时刻最多只能处理1个作业，每个作业只能在1台机器上被处理，抢占和中断是不允许的。作业集N1中的作业加工顺序已经固定，令机器M1上作业的加工顺序为J1,1,J1,2,…,J1,n1，作业Ji,j,i∈{1,2},j∈{1,2,…,ni}的处理时间为pi,j，且有：

min{p1,1,p1,2,…,p1,n1}≥max{p2,1,p2,2,…,p2,n2}

(1)

任意给定1个排序，Ci,j表示作业Ji,j的完工时间，Cmax表示该排序的总完工时间，即Cmax=maxi=1,2,j=1,2,…,ni{Ci,j}，目标是寻求最大完工时间的最小排序，即minCmax。

作业间的冲突约束可通过1个无向二部图G=(V1∪V2,E)来表示，其中V1=N1和V2=N2对应2个作业集，若作业J1,s∈N1和作业J2,t∈N2之间存在冲突，则边(J1,s,J2,t)∈E，这样所定义的二部图称之为冲突图。在任何时刻都不能同时处理2个相互冲突的作业。特别地，属于同一作业集的2个作业不存在冲突约束。

为了解决以上问题，本文提出一种贪婪算法——Longest Processing Time算法，简称LPT算法。算法具体描述如下。

(1)机器M1上的作业连续加工，即作业之间无空闲。

(2)将作业集N2中的作业按照加工时间从大到小的顺序进行排列。

(4)若N2中仍有未加工的作业，则在J1,n1的完工时间之后开始加工。

LPT算法得到的可行排序如图1所示。

M1:J1,1J1,2J1,3…J1,n1 M2:J2,1J2,2δ1δ2J2,3…J2,i-1δn1J2,i…J2,n2

图1 加工序列

证明在LPT算法得到排序中，将作业集N1(N2)分为2个集合：N11,N12(N21,N22)。N22表示所有在J1,n1的完工时间之后开始加工的作业集合。N21表示在J1,n1的完工时间之前开始加工的作业集合。N11表示与N22中至少1个作业不冲突的作业集合。N12表示与N22中所有作业都冲突的作业集合。令P1,P2,P11,P12,P21,P22分别表示作业集N1,N2,N11,N12，N21,N22中所有作业的加工时间总和。则有：

(2)

由于N12中任意作业与N22中所有作业之间均存在冲突，则有：

(3)

接下来，分2种情况进行讨论。

(2)若

P11>2/3P1

(4)

接下来证明

(5)

(6)

所以有：

(7)

又因为：

(8)

所以有：

p2,j2>δj1

(9)

(10)

又由式(8)可知：

(11)

所以有：

(12)

将式(4)代入式(12)，可得：

P21>1/3P1

(13)

令δ=δ1+δ2+…+δn1，因为

P21+δ=P1

(14)

所以有：

δ<2/3P1

(15)

则有：

(16)

2 算法紧例

图2 作业冲突图

假设机器M1和机器M2分别处理2个互不相交的作业集合，N1={J1,1,J1,2,J1,3}，N2={J2,1,J2,2,J2,3,J2,4,J2,5,J2,6}机器M1上作业的加工顺序为J1,1,J1,2,J1,3，且min{p1,1,p1,2,p1,3}≥max{p2,1,p2,2,p2,3,p2,4,p2,5,p2,6}，需要加工的作业用job来表示，每个作业的加工时间如表1所示，其冲突图如图2所示。

表1 作业加工时间

通过运行LPT算法得到的算法解如图3所示，不难发现最优解如图4所示。

M1:111M2:1/2+ε1/2+ε1/21/21/21/2

M1:111M2:1/21/21/21/21/2+ε1/2+ε

3 结束语

本文研究了具有冲突约束且1台机器作业顺序已定的并行专用机器调度问题，基于最大加工时间优先原则设计了近似比为5/3的近似算法。后续将从2个方面进行研究，首先对算法进行进一步改进，由于算法仅仅采用了贪婪算法的思想，若在此基础上增加匹配，改进后的算法可能得到更好的近似比。其次，目标函数可以变为第2台机器上的最大完工时间，在冲突图不同的情况下证明该问题的复杂性。