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

Authors: Adlane Baaziz; Hacène Ait Haddadène; Ammar Oulamara; Ahmed Kouider

Addresses: LaROMaD Laboratory, Department of Operations Research, Faculty of Mathematics, University of Science and Technology Houari Boumediene (USTHB), Algiers, Algeria ' LaROMaD Laboratory, Department of Operations Research, Faculty of Mathematics, University of Science and Technology Houari Boumediene (USTHB), Algiers, Algeria ' LORIA Laboratory, University of Lorraine, Nancy, France ' Centre de Développement des Technologies Avancées (CDTA), Division Productique et Robotique (DPR), Algiers, Algeria

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.

DOI: 10.1504/IJMOR.2023.131397

International Journal of Mathematics in Operational Research, 2023 Vol.25 No.1, pp.47 - 67

Received: 22 Dec 2021
Accepted: 16 Apr 2022
Published online: 09 Jun 2023 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article