I am looking for the best known approximation algorithm for the scheduling problem $P2|tree;p_j=1;M_j|C_{max}$, which to my knowledge is at least $\mathbb{NP}$-hard. A more elaborate description of the problem: I want to find a non-preemptive schedule on two machines with minimum makespan for $n$ jobs with uniform processing times $p_{j}=1$, which need to be processed according to precedence conditions defined via a directed acyclic graph. The processing time for every job is independent of the chosen machine, but some jobs might only be executable on one of the machines. Any hints would be greatly appreciated, as I have not found anything for this specific problem yet.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.