The Single Machine Parallel Batch Scheduling Problem With Job Compatibility Constraints

In this paper, we consider the single machine parallel batch problem with job compatibility constraints. Given n jobs J1, J2, ..., Jn and a single machine that can process a batch of jobs at the same time. The jobs are processed in batches if and only if these jobs satisfy the relation of compatibility. However each of those that cannot be compatible has to schedule in a single batch respectively. Now we construct a new graph G as follows:Consider the jobs J1, J2, ..., Jn as the vertices of the graph G; And join the jobs (vertices) Ji and Jj if they are compatible and can be processed in one batch. It is easy to see that the jobs scheduled in the same batch must be a clique in graph G. Therefore we can study this scheduling problem through a graph G, which may be a easier way to solve the problem. Before we start to study the scheduling problem, it is necessary to define the model of this problem and some notations. We call this model the single machine parallel batch scheduling problem with job compatibility constraints, and we denote it by1|p-batch; G|fwhere f is a regular objective function.Herein, this paper mainly consider this scheduling problem with makespan as its objective function, and we also talk a little about the total completion time as its objective function. Therefore this paper represents its main conclusions as follows:When the graph G is a general graph, we can prove the scheduling problem l\p -batch; G|Cmax is NP-hard by reduction from the clique cover problem.(1) The decision version of the problem 1|p — batch; G|Cmax is NP-complete. Since the scheduling problem 1|p — batch; G|Cmax is NP-hard, we first consider graphswith special structure.(2) When the graph is limited to be a general bipartite graph G = (X, Y;E),X = (p1,... ,Pm}, Y = {q1, ..., qn}, where pi, qj for all i,j are also representing the processing time of the corresponding jobs. Then we have a polynomial algorithm, which sovles thescheduling problem 1|p - batch; bipartite|Cmax with the running time O(n3).(3) Given the complete bipartite graph G = (X,Y;E), where X = {p1,....,pm},Y = {q1,...,qn}, pi, qj also denote the processing time of the corresponding jobs respectively. Without loss of generality, we suppose that m ≤ n. Then we have a more effective algorithm, which solves the problem 1|p -batch; complete bipartite |Cmax correctly with running time O(nlogn).(4) As a generalization of the complete bipartite graph, we consider the complete m-partite graph. Given the complete m-partite graph G - (X1,...,Xm;E), where |Xi| = ni, ∑m i=1 ni = n. Suppose that n1≥ n2 ≥...≥ nm. And then this paper gives a polynomial algorithm, which solves the problem l\p — batch; complete m-partite |Cmax in O(nlogn) time.(5) Suppose that the graph G is a tree with diameter no more than 4. Let d be the diameter of tree T. Then this paper has a polynomial algorithm with the running time O(n), which solves the problem 1|p — batch;tree with d ≤ 4|Cmax correctly.(6) Suppose the graph G - (S∪Q, E) be a split graph, where S = {p1, ... ,ps} is an independent set, Q = {q1,..., qt} is a clique, and pi, qj is also the processing time of the corresponding jobs respectively. Then this paper gives a polynomial algorithm, which solves the problem 1|p — batch; split graph|Cmax in O(n2) time.When this paper consider the total completion time of batches as the objective function, we have the following conclusions.(7) The decision version of the problem 1|p - batch,pj = 1;G|∑C(Bi) is NP-complete.(8) The problem 1|p — batch,pj = 1; bipartite|∑C (Bi) has a polynomial algorithm with the running time O(n2).