Skip to Main content Skip to Navigation
Conference papers

Using a Variable Neighborhood Search to Solve the Single Processor Scheduling Problem with Time Restrictions

Abstract : We study the single-processor scheduling problem with time restrictions in order to minimize the makespan. In this problem, n independent jobs have to be processed on a single processor, subject only to the following constraint: During any time period of length α> 0 the number of jobs being executed is less than or equal to a given integer value B. It has been shown that the problem is NP-hard even for B = 2. We propose the two metaheuristics variable neighborhood search and a fixed neighborhood search to solve the problem. We conduct computational experiments on randomly generated instances. The results indicate that our algorithms are effective and efficient regarding the quality of the solutions and the computational times required for finding them.
Document type :
Conference papers
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03679883
Contributor : Kathleen TORCK Connect in order to contact the contributor
Submitted on : Friday, May 27, 2022 - 11:17:29 AM
Last modification on : Saturday, May 28, 2022 - 3:42:21 AM

Identifiers

Collections

Citation

Rachid Benmansour, Oliver Braun, Said Hanafi, Nenad Mladenovic. Using a Variable Neighborhood Search to Solve the Single Processor Scheduling Problem with Time Restrictions. 6th International Conference on Variable Neighborhood Search, ICVNS 2018, Oct 2018, Sithonia, Greece. pp.202-215, ⟨10.1007/978-3-030-15843-9_16⟩. ⟨hal-03679883⟩

Share

Metrics

Record views

5