An efficient backtracking heuristic for the resource allocation problem with compatibility and exclusivity constraints

Ahmed Khassiba ()
Additional contact information
Ahmed Khassiba: Capgemini Engineering, Sud-Ouest

Journal of Heuristics, 2025, vol. 31, issue 1, No 4, 29 pages

Abstract: Abstract We study a resource allocation problem featuring specific constraints, called exclusivity constraints, in addition to regular compatibility constraints. Resources are to be allocated to independent modules, each having a list of compatible resources. A resource can be allocated to several modules. However, some modules exhibit exclusivity constraints, requiring each of them to be allocated to one dedicated compatible resource, not shared with any other module. Such a resource allocation problem arises in the deployment of simulation modules on computational resources in a distributed simulation platform, where the simulation requester may require some modules to be allocated to dedicated resources for a better soft real-time execution, or for instrumentation purposes. In this paper, we introduce the problem of resource allocation with compatibility and exclusivity constraints and show it reduces to the list-coloring problem in a threshold graph. We deduce that our problem is NP-complete in the general case, while it can be solved in polynomial time, in two special cases. We propose a heuristic backtracking algorithm enhanced by pruning rules and exploiting the subproblems’ special structure. Compared to four list coloring heuristics adapted to our problem, our heuristic algorithm can be considered as the method of choice to find high-quality solutions in short computing times.

Keywords: Resource allocation; List-coloring problem; Backtracking algorithm; Pruning rules; Imperfect matching (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-024-09538-x 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:joheur:v:31:y:2025:i:1:d:10.1007_s10732-024-09538-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-024-09538-x

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

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