Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay

✍ Scribed by Alix Munier Kordon

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 221 KB
• Volume: 32
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2003.12.003

✦ Synopsis

We consider the makespan minimization for a unit execution time task sequencing problem with a bipartite precedence delays graph and a positive precedence delay d. We prove that the associated decision problem is strongly NP-complete and we provide a non-trivial polynomial sub-case. We also give an approximation algorithm with ratio 3 2 .