Minimizing total completion time in a two-machine flow shop with deteriorating jobs (Q850246)

In the paper two-machine flow-shop scheduling problems with deteriorating jobs are studied where the processing time of a job is given by an increasing linear deterioration function depending on its starting time. The objective is to find a schedule minimizing the total completion time. At first, the authors study some polynomially solvable special cases of the problem and derive some dominance properties and two lower bounds. Afterwards, a heuristic and a branch-and-bound algorithm are proposed and compared in computational experiments.