Machine scheduling problems with a position-dependent deterioration

In this study, we propose a new scheduling model with position-dependent deterioration, in which the processing time of a job is defined by an increasing function of total weighted normal processing time of jobs prior to it in the sequence, where the weight is position dependent. We show that some single machine scheduling problems remain polynomially solvable under the proposed model, respectively. In addition, we show that some special cases of the flow shop scheduling problems can be optimally solved by polynomial time algorithm, respectively.