Using local search methods to solve two machine flow shop scheduling problem

Abstract EN

There are a lot of scheduling problems that have a combinatorial aspect and these problems are difficult to be solved.

Therefore we can use the local search methods to find the optimal solution or near optimal solution.

In this paper we consider the scheduling problem on two machine flow shop to find the minimum value of the objective function (maximum completion time and maximum of tardiness).

The main contribution in this work is a branch and bound (BAB) algorithm with optimal solution and some of the local search methods namely descent method (DM), adjacent pairwise interchange method (APIM).

Also, prove some of special cases of which leads to optimal solution.

Since the problem is NP-hard, descent method (DM) and adjacent pairwise interchange method (APIM) are proposed to solve the problem efficiency.