Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints

摘要

In this paper we investigate two-machine flow shop scheduling problems with deteriorating jobs and chain precedence constraints. We consider two types of precedence constraints. Under the first type constraints, a successor cannot start on any machine before its predecessor has been completed on the same machine. Under the second one, a successor cannot start on any machine before its predecessor has been completed on all machines. We show that the problem with the first type precedence constraints is polynomially solvable, and the problem with the second type precedence constraints is NP-hard in the strong sense.