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

Alix Munier-Kordon (1)

1 CIAN - Circuits Intégrés Numériques et Analogiques

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 32.

Domaines: Informatique [cs]

Alix Munier-Kordon. Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay. Operations Research Letters, 2004, 32 (6), pp.557-564. ⟨10.1016/j.orl.2003.12.003⟩. ⟨hal-01195965⟩