Two dedicated parallel machines scheduling problem with precedence constraints to minimize makespan is considered.
Given a set N of n jobs that must be processed on two parallel machines. Jobs from the subset N1 have to be processed on the first machine, jobs from N2 on the second one. All the jobs are assumed to be available for processing at time 0. For each job j a processing time is known. Furthermore, arbitrary finish-start precedence relations are introduced between the jobs according to an acyclic directed graph G. The objective is to determine the starting time in such a way that the given precedence relations are fulfilled and the makespan (the maximal completion time) is minimized. This problem originally appeared as a sub-problem of the well-known two-sided assembly line balancing problem (TSALBP-1). Denote this problem P2|N1,N2,prec|Cmax.
The following Lemmas are proven:
Lemma 1. A special case of the problem P2|N1,N2,chain|Cmax is NP hard in the strong sense, where G consists only chains of jobs.
Lemma 2. A simple assembly line balancing problem(SALBP-1) can be reduced P2|N1,N2,chain|Cmax in polynomial time.
Lemma 3. A special case with equal-processing-times of jobs P2|N1,N2,p_j=1|Cmax is NP hard in the strong sense.
Lemma 4. The problem P2|N1,N2,prec|Cmax --> max with opposite optimization criterion is NP-hard in the strong sense.
We showed as well that List Scheduling Algorithm with some domination rules (Critical Path, Largest Processing Time, etc.) has an approximation ratio almost equal 2.