๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

No coin nor oath required. For personal study only.

โœฆ 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 .


๐Ÿ“œ SIMILAR VOLUMES