Flowshop scheduling of deteriorating jobs on dominating machines

In this paper we consider the general, no-wait and no-idle permutation flowshop scheduling problem with deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. We assume a linear deterioration function with identical increasing rates for all the jobs and there are some dominating relationships between the machines. We show that the problems to minimize the makespan and the total completion time remain polynomially solvable when deterioration is considered, although these problems are more complicated than their classical counterparts without deterioration.

► Flowshop scheduling of linear deteriorating jobs on dominating machines is modeled and studied.
► Some problems to minimize the makespan and the total completion time are polynomially solvable.
► Experimental results show that the proposed algorithms run very efficiently.