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

(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个相互冲突的作业不允许同时进行加工。对并行机器调度施加这样的限制是合理的，因为在制造业或服务业中资源是有限的。……