Performance enhancement of numerical approaches for scheduling problem on machine single

Abstract

In this paper, we consider a single-machine scheduling problem, with the aim of minimizing the weighted sum of the  completion time. This problem is NP-hard, making the search for an optimal solution very difficult. In this frame, two heuristics (H₁), (H₂) and metaheuristic tabu search are suggested.

To improve the performance of this techniques, we used, on one hand, different diversification strategies (TES₁ and TES₂) with the aim of exploring unvisited regions of the solution space. On the other hand, we suggested three types of neighborhoods (neighborhood by swapping, neighborhood by insertion and neighborhood by blocks).It must be noted that tasks movement can be within one period or between different periods.