A variable neighborhood search for single machine scheduling problem with time restrictions
Résumé
In this paper we analyze a single machine scheduling problem with time restrictions. The objective considered is the minimization of the makespan. In this problem several jobs, available at the begging of the schedule, have to be processed on a single machine. The machine can handle only one job at a time, and during any time period of length alpha the number of jobs being executed is less than or equal to a given integer value B. The problem is known to be NP-hard for any value of B > 2. We propose a variable neighborhood search metaheuristic to solve the problem and we conduct computational experiments on randomly generated instances. The results indicate that our algorithm is effective and efficient regarding the quality of the solutions and the computational times required to find them.