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

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

0.00 Avg rating—0 Votes
Article ID: iaor2005527
Country: Netherlands
Volume: 32
Issue: 6
Start Page Number: 557
End Page Number: 564
Publication Date: Nov 2004
Journal: Operations Research Letters
Authors:
Keywords: combinatorial analysis, graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.