Authors: Benmansour, Rachid
Braun, Oliver
Hanafi, Saïd
Mladenović, Nenad 
Title: Using a Variable Neighborhood Search to Solve the Single Processor Scheduling Problem with Time Restrictions
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 11328 LNCS
First page: 202
Last page: 215
Conference: 6th International Conference on Variable Neighborhood Search, ICVNS 2018; Sithonia; Greece; 4 October 2018 through 7 October 2018
Issue Date: 1-Jan-2019
Rank: M33
ISBN: 978-3-030-15842-2
ISSN: 0302-9743
DOI: 10.1007/978-3-030-15843-9_16
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.
Keywords: Fixed neighborhood search | NP-hard | Scheduling | Single processor | Time restrictions | Variable neighborhood search
Publisher: Springer Link

Show full item record


checked on May 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.