论文部分内容阅读
排序理论是组合最优化学科中一个蓬勃发展的研究方向。平行机排序是其中一个重要组成部分。在经典的平行机排序文献中,人们往往研究工件间的序约束。这种序约束是用一个有向图D描述的先后顺序关系,即一个工件必须在它的先行工件完工后才能开始加工。本论文研究工件间的另一种相互关系一—同时性关系,即一个工件必须与享有同一资源的其他工件同时加工。这种同时性约束用一个无向图G来描述。例如对城市间的通道进行检疫消毒时,图G的顶点表示城市,边表示城市间的通道;每条边都有一个检疫任务,即一个工件。若干个平行作业的医疗队用m台平行机表示。为对疫情的传播进行严格封锁,同一城市引出的通道必须由相应的医疗队同时进行防疫处理。这就是说,关联于图G的一个顶点的边工件必须同时加工。又如在对一个通讯网络进行检测时,从一个节点(交换台站)发出检测信号,在其引出的所有线路中,检测人员必须同时进行操作。在其它系统中,当一些任务要共享一些资源(信息资源或物资资源)时,都有这种同时性约束。这样一来,我们得到有同时性约束的平行机排序问题如下:给定m台平行机及一个无向图G,其中G的边代表工件(称为“边工件”);若一个边工件e=uv安排在时刻t开始加工,则关联于u(或v)的全部未加工的边工件必须也在时刻t开始加工。至于目标函数,仍与通常的平行机排序一样,如最大完工时间Cmax或完工时间和∑Cj等等。按照传统的三参数分类记号,此问题记为Pm|G-SMT|f,其中SMT为同时性(simultaneity)的简写,G表示工件间邻接关系的图,f为正则的目标函数,如Cmax及∑Cj等等。这将称为“一般模型”。在这个模型中,同一个时刻可以有多于一个顶点关联的边工件同时被加工(只要机器数足够多)。但是,有些实际问题提出更苛刻的要求:任何时刻只有一个顶点关联的边工件可以被同时加工,也就是被处理的顶点呈一个序列形式,所以我们称之为“序列模型”。
无论一般模型或序列模型,同时性约束的特点是:工件的安排受到机器数m及图G的顶点度的双重限制,所以此类问题的一般形式是困难的。本论文将从算法的观点研究此类问题,包括三个方面:计算复杂性,多项式时间算法及近似算法。具体的说,本论文的主要结果如下:
1.NP-完全性证明。对序列模型及一般模型,证明Pm|pi:1,G-SMT|Cmax及Pm|pj=1,G-SMT|∑Cj的判定形式是NP-完全问题。
2.对Pm|pj=1,G-SMT|Cmax给出(2-1/m)-近似算法。
3.对特殊图G给出Pm|pj=1,G-SMT|Cmax(或∑Cj)的多项式时间算法,如G为树、单圈图、完全偶图、完全七部图、平面格子图等。