Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints |
| |
Authors: | Chuanli Zhao Hengyong Tang |
| |
Institution: | School of Mathematics and Systems Science, Shenyang Normal University, Shenyang, Liaoning 110034, China |
| |
Abstract: | 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. |
| |
Keywords: | Scheduling Flow shop Deteriorating Precedence constraints Makespan |
本文献已被 ScienceDirect 等数据库收录! |