Parallel Machine Scheduling With Simultaneity Constraint

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,...