An Improved Tabu Search Meta-heuristic Approach for Solving Scheduling Problem with Non-availability Constraints

In this paper, the problem of scheduling on parallel machines subject to non-availability constraints with precedence constraints between the tasks is treated. We consider the minimization of the maximum completion time (i.e., makespan). We propose to use a meta-heuristic entitled tabu search to solve this scheduling problem which has its own application in the assembly industry where the tasks’ graph takes the form of an intree, and where the machines may not be available due to machine breakdowns or preventive maintenance. The insertion movement is used to generate neighbourhoods. Several versions of tabu meta-heuristic algorithm are proposed. The results of tabu search are compared with a proposed lower bound and the best heuristic. It is concluded that the last proposed version of tabu search is the better in terms of computed makespan and computing time. The algorithm of this proposed version uses two tabu lists and partitions the machines into two sets in order to reduce the number of generated neighbours and then minimize the computing time by keeping the same quality of solutions.