Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility

Simon Thevenin, Nicolas Zufferey and Jean-Yves Potvin

International Journal of Production Research, 2017, vol. 55, issue 6, 1588-1606

Abstract: In this paper, an extension of the graph colouring problem is introduced to model a parallel machine scheduling problem with job incompatibility. To get closer to real-world applications, where the number of machines is limited and jobs have different processing times, each vertex of the graph requires multiple colours and the number of vertices with the same colour is bounded. In addition, several objectives related to scheduling are considered: makespan, number of pre-emptions and summation over the jobs’ throughput times. Different solution methods are proposed, namely, two greedy heuristics, two tabu search methods and an adaptive memory algorithm. The latter uses multiple recombination operators, each one being designed for optimising a subset of objectives. The most appropriate operator is selected dynamically at each iteration, depending on its past performance. Experiments show that the proposed algorithm is effective and robust, while providing high-quality solutions on benchmark instances for the graph multi-colouring problem, a simplification of the considered problem.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2016.1181285 (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:taf:tprsxx:v:55:y:2017:i:6:p:1588-1606

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2016.1181285

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().