Skip to Main content Skip to Navigation
Conference papers

A variable neighborhood search for single machine scheduling problem with time restrictions

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03388198
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Wednesday, October 20, 2021 - 11:52:29 AM
Last modification on : Wednesday, November 3, 2021 - 4:42:37 AM

Identifiers

  • HAL Id : hal-03388198, version 1

Collections

Citation

Rachid Benmansour, Said Hanafi, Olivier Braun. A variable neighborhood search for single machine scheduling problem with time restrictions. MIC'2017, The 12th edition of the Metaheuristics International Conference, Jul 2017, Barcelona, Spain. ⟨hal-03388198⟩

Share

Metrics

Record views

9