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 given m parallel machines and a graph G, whose vertices represent jobs. Simultaneity constraint means that we can process a vertex job v if and only if there exists at least dG(v) idle machines, where dG(v) is the degree of vertex v in graph G. 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. Let pv denote the processing time of vertex job v, we define pv = 0 if d(v) = 0, and pv = 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.