IDEAS home Printed from https://ideas.repec.org/a/ids/ijmore/v25y2023i1p47-67.html
   My bibliography  Save this article

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

Author

Listed:
  • Adlane Baaziz
  • Hacène Ait Haddadène
  • Ammar Oulamara
  • Ahmed Kouider

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.

Suggested Citation

  • Adlane Baaziz & Hacène Ait Haddadène & Ammar Oulamara & Ahmed Kouider, 2023. "Scheduling preemptive jobs on parallel machines with a conflict graph: a graph multi-colouring approach," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 25(1), pages 47-67.
    • Handle: RePEc:ids:ijmore:v:25:y:2023:i:1:p:47-67
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=131397
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ids:ijmore:v:25:y:2023:i:1:p:47-67. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=320 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.