【作者】 林琳；

【导师】 林诒勋；

【作者基本信息】 郑州大学 ， 运筹学与控制论， 2006， 硕士

【摘要】 排序理论是组合最优化学科中一个蓬勃发展的研究方向。平行机排序是其中一个重要组成部分。在经典的平行机排序文献中，人们往往研究工件间的序约束。这种序约束是用一个有向图D描述的先后顺序关系，即一个工件必须在它的先行工件完工后才能开始加工。本论文研究工件间的另一种相互关系一一同时性关系，即一个工件必须与享有同一资源的其他工件同时加工。这种同时性约束用一个无向图G来描述。例如对城市间的通道进行检疫消毒时，图G的顶点表示城市，边表示城市间的通道；每条边都有一个检疫任务，即一个工件。若干个平行作业的医疗队用m台平行机表示。为对疫情的传播进行严格封锁，同一城市引出的通道必须由相应的医疗队同时进行防疫处理。这就是说，关联于图G的一个顶点的边工件必须同时加工。又如在对一个通讯网络进行检测时，从一个节点（交换台站）发出检测信号，在其引出的所有线路中，检测人员必须同时进行操作。在其它系统中，当一些任务要共享一些资源（信息资源或物资资源）时，都有这种同时性约束。这样一来，我们得到有同时性约束的平行机排序问题如下：给定m台平行机及一个无向图G，其中G的边代表工件（称为“边工件”）；若一个边工件e=uv安排在时刻t开始加工，则关联于，u（或v）的全部未加工的边工件必须也在时刻t开始加工。至于目标函数，仍与通常的平行机排序一样，如最大完工时间C_max或完工时间和∑C_j等等。按照传统的三参数分类记号，此问题记为Pm|G-SMT|f，其中SMT为同时性（simultaneity）的简写，G表示工件间邻接关系的图，f为正则的目标函数，如C₍max及∑C_j等等。这将称为“一般模型”。在这个模型中，同一个时刻可以有多于一个顶点关联的边工件同时被加工（只要机器数足够多）。但是，有些实际问题提出更苛刻的要求：任何时刻只有一个顶点关联的边工件可以被同时加工，也就是被处理的顶点呈一个序列形式，所以我们称之为“序列模型”。 无论一般模型或序列模型，同时性约束的特点是：工件的安排受到机器数m及图G的顶点度的双重限制，所以此类问题的一般形式是困难的。本论文更多还原

【Abstract】 Scheduling is a flourishing direction of Combinatorial Optimization. Parallel machine schedule is an important component of it. In literatures of classical parallel machine scheduling, people often study the precedence constraint among jobs. This precedence constraint is described by a digraph D, that is to say, we cannot schedule a job until all its predecessors are scheduled. In this paper, we consider another relation among jobs—simultaneity constraint. It means that the jobs sharing common resources must start processing at the same time. The relation can be described by a graph G. For example, when we quarantine and disinfect the roads between cities, the vertices of G denote citices and the edges denote roads; every edge has a quarantine task—a job. Several medical groups are represented by m parallel machins. For we must block the spread of epidemic strictly, the roads leading from a common city must be prevented by medical groups simultaneously. That is to say, the edge jobs incident with a vertex in G must start processing simultaneously. For another example, when we examine a communication network, we send singal from a node and testing must be carried out simultaneously on all lines leading from this node. There is the simultaneity constraint in other systems when some tasks share a common resource. Then we get a parallel machine schedule problem with simutaneity constraint as follows: Given m parallel machines and a graph G, the edges of G represent jobs; if an edge job e=uv starts at time t, then all the unscheduled edge jobs incident with u（ or v） must start at time t. The objective function is the same as usual, such as makespan C_max or ∑C_j and so on. According to the traditional three-field classification, this problem is denoted by P_m|G - SMT|f, where SMT is the abbreviation of simultaneity and graph G represents the incidence relations among jobs, and f is a regular function, such as C_max or ∑C_j. This is called " general model ". In this model, it is allowed to schedule edge jobs incident with more than one vertex at the same time （if there are enough machines）. But in practical situation there may be more rigorous requst: at any time the scheduled edge jobs must be incident with only one vertex. That is to say,更多还原