Research on two-machine flow shop scheduling problem with release dates and truncated learning effects

In this article, a two-machine flow shop scheduling problem with release dates and truncated learning effects is studied. The objective is to find a sequence such that the total completion time is minimized. This problem is NP-hard and cannot be solved in polynomial time. Therefore, a branch-and-bound algorithm (dominance conditions, lower bounds and an upper bound are needed) and an heuristic algorithm are proposed. In addition, simulated annealing and tabu search are developed to obtain near-optimal solutions for the problem. A large number of computational tests have been conducted, and the data show that the branch-and-bound algorithm can handle small-sized problems effectively within 14 jobs, while the proposed heuristic algorithm has a shorter running time for large-sized problems.