Solution algorithms for the total weighted completion time minimization flow shop scheduling with decreasing linear deterioration

In this paper, we consider a two-machine flow shop scheduling problem with decreasing linear deterioration. By decreasing linear deterioration, we mean that the processing time is a decreasing function of its execution start time. The objective is to find a sequence that minimizes the total weighted completion time. Several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. Two heuristic algorithms are also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented.