Scheduling preemptive jobs on parallel machines with a conflict graph: a graph multi-colouring approach

Adlane Baaziz, Hacène Ait Haddadène, Ammar Oulamara and Ahmed Kouider

International Journal of Mathematics in Operational Research, 2023, vol. 25, issue 1, 47-67

Abstract: This paper addresses the problem of scheduling n preemptive jobs, which must be carried before a predefined overall deadline, on a set of m parallel machines. This deadline corresponds to the end of the planning horizon. Each job has its own processing time and a predetermined gain assigned to it when it is completely executed. Resources are distinguished into two types: shared and critical resources. Jobs requiring the same critical resource are subjected to conflicting constraints modelled by an undirected graph. The goal is to optimise three objectives: the main one is maximising the total gain of the performed jobs. The two others objectives consider the manner of the jobs accomplishment, where the number of interruptions and the total completion time have to be minimised. To solve this NP-hard problem, an improved simulated annealing based on: 1) a minimum lost gain strategy for vertices colouring procedure; 2) a new technique for the selection of a new solution is proposed. Extensive computational experiments show the capability of the proposed algorithm to obtain optimal solutions in a reasonable amount of CPU time for small instances, and significantly better results than in the rest methods of the literature for large instances.

Keywords: parallel machines scheduling; graph multi-colouring; meta-heuristic approach. (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=131397 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijmore:v:25:y:2023:i:1:p:47-67

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().