Scheduling preemptive jobs on parallel machines with a conflict graph: a graph multi-colouring approach
by Adlane Baaziz; Hacène Ait Haddadène; Ammar Oulamara; Ahmed Kouider
International Journal of Mathematics in Operational Research (IJMOR), Vol. 25, No. 1, 2023

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.

Online publication date: Fri, 09-Jun-2023

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Mathematics in Operational Research (IJMOR):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com