Parallel Machine Scheduling With A Simultaneity Constraint And Unit-Length Jobs To Minimize The Makespan

In this paper, we consider the parallel machine scheduling with a simultaneity constraint and unit-length jobs. The problem can be described as follows. There are givenmparallel machines and a graphG, whose vertices represent jobs. Simultaneity constraint means that we can process a vertex jobvif and only if there exists at leastdG(v)idle machines, wheredG(v)is the degree of vertexvin graphG. Once a vertex job is completed, we delete the vertex and its incident edges from the graph. The number of machines that a vertex job needing depends on its degree in current graph. Changes of graph result in changes of vertex degree. Here, we consider a special case that all jobs in the original graph are unit-length. Letpvdenote the processing time of vertex jobv, we definepv= 0ifd(v) = 0, andpv= 1, otherwise. The objective is to minimize the time by which each vertex job is completed, i.e., the time by which the graph becomes an empty graph. We show that this problem is strongly NP-hard and provide a$(2-\frac{1}{m})$-approximation algorithm.