Heuristic and metaheuristic approaches for parallel machine scheduling under resource constraints

Mohamed Amine Abdeljaoued (), Nour El Houda Saadani () and Zied Bahroun ()
Additional contact information
Mohamed Amine Abdeljaoued: Université de Tunis El Manar
Nour El Houda Saadani: Université de Tunis El Manar
Zied Bahroun: American University of Sharjah

Operational Research, 2020, vol. 20, issue 4, No 8, 2109-2132

Abstract: Abstract In this paper, an NP-hard parallel machine scheduling problem under resource reservation constraints is studied. The problem is characterized by a set of operations that have to be scheduled on parallel machines, given that the process of each operation requires one specific additional resource, present in a single copy, from a set of reusable resources. The objective is to minimize the makespan. After a mathematical formulation of the problem, two new heuristics that quickly reach a satisfying solution and a simulated annealing metaheuristic aiming to improve the solutions’ quality are provided. The performance of these methods is assessed in a detailed experimental study that includes a comparison with three heuristics from the literature and a worst case analysis of the best performing heuristic. The obtained results show that one of our heuristics outperforms the literature’s methods for nearly all the tested instances, while the simulated annealing algorithm improves the heuristics’ outcomes and ensure near optimal solutions in most of the tests.

Keywords: Scheduling; Parallel machines; Resource; Heuristic; Metaheuristic (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-018-0412-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:20:y:2020:i:4:d:10.1007_s12351-018-0412-3

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-018-0412-3

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().