Flow shop makespan minimization scheduling with deteriorating jobs under dominating machines

摘要

This paper studies general, no-wait or no-idle flow shop scheduling problems with deteriorating jobs, that is, jobs whose processing times are an increasing function of their start times. A linear deterioration function with identical normal processing times of all jobs is assumed and some dominating relationships between machines can be satisfied. For the makespan minimization problems, the following dominant machines constraint: idm, ddm, idm-ddm and ddm-idm are considered. We show that these problems can be solved in polynomial time, although these problems are more complicated than the classical ones.