排序理论是组合最优化学科中一个蓬勃发展的研究方向。平行机排序是其中一个重要组成部分。在经典的平行机排序文献中，人们往往研究工件间的序约束。这种序约束是用一个有向图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为树、单圈图、完全偶图、完全七部图、平面格子图等。