Complexity of two dual criteria scheduling problems

In this article we answer the complexity question of two dual criteria scheduling problems which had been open for a long time. We show that both problems are binary NP-hard.