Scheduling three chains on two parallel machines

Alessandro Agnetis

doi:10.1016/j.ejor.2009.07.001

Scheduling three chains on two parallel machines

2010-05-01

10

PRE

AI

DOI：10.1016/j.ejor.2009.07.001

Original

Original request for help

Save

Abstract

En 中文

We consider the problem of scheduling n tasks subject to chain-precedence constraints on two identical machines with the objective of minimizing the makespan. The problem is known to be strongly NP-hard. Here, we prove that it is binary NP-hard even with three chains. Furthermore, we characterize the complexity of this case by presenting a pseudopolynomial time algorithm and a fully polynomial time approximation scheme. (C) 2009 Elsevier B.V. All rights reserved.

Keywords:

Computational complexity

Scheduling

Parallel machines

Approximation

Scheduling three chains on two parallel machines

Abstract

Journal

Organization