A note on the paper "Minimizing total tardiness on parallel machines with preemptions" by Kravchenko and Werner [2010]

D. Prot, O. Bellenguez-Morineau, C. Lahlou

In this note, we point out two major errors in the paper "Minimizing total tardiness on parallel machines with preemptions" by Kravchenko and Werner [2010]. More precisely, they proved that both problems P|pmtn|sum(Tj) and P|rj, pj = p, pmtn|sum(Tj) are NP-Hard. We give a counter-example to their proofs, letting the complexity of these two problems open.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment