IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v55y2017i6p1588-1606.html
   My bibliography  Save this article

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

Author

Listed:
  • Simon Thevenin
  • Nicolas Zufferey
  • Jean-Yves Potvin

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.

Suggested Citation

  • Simon Thevenin & Nicolas Zufferey & Jean-Yves Potvin, 2017. "Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1588-1606, March.
    • Handle: RePEc:taf:tprsxx:v:55:y:2017:i:6:p:1588-1606
    DOI: 10.1080/00207543.2016.1181285
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2016.1181285
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2016.1181285?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

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

    References listed on IDEAS

    as
    1. Solnon, Christine & Cung, Van Dat & Nguyen, Alain & Artigues, Christian, 2008. "The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF'2005 challenge problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 912-927, December.
    2. Cheng, T. C. E. & Sin, C. C. S., 1990. "A state-of-the-art review of parallel-machine scheduling research," European Journal of Operational Research, Elsevier, vol. 47(3), pages 271-292, August.
    3. Stefano Gualandi & Federico Malucelli, 2012. "Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 81-100, February.
    4. Pesenti, Raffaele & Ukovich, Walter, 2003. "Economic lot scheduling on multiple production lines with resource constraints," International Journal of Production Economics, Elsevier, vol. 81(1), pages 469-481, January.
    5. Corominas, Albert & Pastor, Rafael & Plans, Joan, 2008. "Balancing assembly line with skilled and unskilled workers," Omega, Elsevier, vol. 36(6), pages 1126-1132, December.
    6. Ivo Blöchliger & Nicolas Zufferey, 2013. "Multi-coloring and job-scheduling with assignment and incompatibility costs," Annals of Operations Research, Springer, vol. 211(1), pages 83-101, December.
    7. Lushchakova, Irina N. & Strusevich, Vitaly A., 2010. "Scheduling incompatible tasks on two machines," European Journal of Operational Research, Elsevier, vol. 200(2), pages 334-346, January.
    8. Karen Aardal & Stan Hoesel & Arie Koster & Carlo Mannino & Antonio Sassano, 2007. "Models and solution techniques for frequency assignment problems," Annals of Operations Research, Springer, vol. 153(1), pages 79-129, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Julio Mar-Ortiz & Alex J. Ruiz Torres & Belarmino Adenso-Díaz, 2022. "Scheduling in parallel machines with two objectives: analysis of factors that influence the Pareto frontier," Operational Research, Springer, vol. 22(4), pages 4585-4605, September.
    2. Hanane Krim & Nicolas Zufferey & Jean-Yves Potvin & Rachid Benmansour & David Duvivier, 2022. "Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times," Journal of Scheduling, Springer, vol. 25(1), pages 89-105, February.
    3. Santini, Alberto & Bartolini, Enrico & Schneider, Michael & Greco de Lemos, Vinicius, 2021. "The crop growth planning problem in vertical farming," European Journal of Operational Research, Elsevier, vol. 294(1), pages 377-390.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yalaoui, F. & Chu, C., 2006. "New exact method to solve the Pm/rj/[summation operator]Cj schedule problem," International Journal of Production Economics, Elsevier, vol. 100(1), pages 168-179, March.
    2. Natalia Castro & María A. Garrido-Vizuete & Rafael Robles & María Trinidad Villar-Liñán, 2020. "Contrast in greyscales of graphs," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 874-898, April.
    3. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    4. Lin, Hung-Tso & Liao, Ching-Jong, 2003. "A case study in a two-stage hybrid flow shop with setup time and dedicated machines," International Journal of Production Economics, Elsevier, vol. 86(2), pages 133-143, November.
    5. Biber Nurit & Mor Baruch & Schlissel Yitzhak & Shapira Dana, 2023. "Lot scheduling involving completion time problems on identical parallel machines," Operational Research, Springer, vol. 23(1), pages 1-29, March.
    6. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    7. George L. Vairaktarakis, 2003. "The Value of Resource Flexibility in the Resource-Constrained Job Assignment Problem," Management Science, INFORMS, vol. 49(6), pages 718-732, June.
    8. Anurag Agarwal & Varghese S. Jacob & Hasan Pirkul, 2006. "An Improved Augmented Neural-Network Approach for Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 119-128, February.
    9. Olcay Polat & Can B. Kalayci & Özcan Mutlu & Surendra M. Gupta, 2016. "A two-phase variable neighbourhood search algorithm for assembly line worker assignment and balancing problem type-II: an industrial case study," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 722-741, February.
    10. Jamie Fairbrother & Adam N. Letchford & Keith Briggs, 2018. "A two-level graph partitioning problem arising in mobile wireless communications," Computational Optimization and Applications, Springer, vol. 69(3), pages 653-676, April.
    11. Yuan Sun & Samuel Esler & Dhananjay Thiruvady & Andreas T. Ernst & Xiaodong Li & Kerri Morgan, 2024. "Instance space analysis for the car sequencing problem," Annals of Operations Research, Springer, vol. 341(1), pages 41-69, October.
    12. Kloster, Konstantin & Moeini, Mahdi & Vigo, Daniele & Wendt, Oliver, 2023. "The multiple traveling salesman problem in presence of drone- and robot-supported packet stations," European Journal of Operational Research, Elsevier, vol. 305(2), pages 630-643.
    13. Lee, Soonhui & Turner, Jonathan & Daskin, Mark S. & Homem-de-Mello, Tito & Smilowitz, Karen, 2012. "Improving fleet utilization for carriers by interval scheduling," European Journal of Operational Research, Elsevier, vol. 218(1), pages 261-269.
    14. Henrich, Peter & Land, Martin & Gaalman, Gerard, 2006. "Grouping machines for effective workload control," International Journal of Production Economics, Elsevier, vol. 104(1), pages 125-142, November.
    15. Jun-Ho Lee & Hyun-Jung Kim, 2021. "A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and limited setup operators," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 992-1026, December.
    16. Golle, Uli & Rothlauf, Franz & Boysen, Nils, 2014. "Car sequencing versus mixed-model sequencing: A computational study," European Journal of Operational Research, Elsevier, vol. 237(1), pages 50-61.
    17. Elif Elcin Gunay & Ufuk Kula, 2017. "A stochastic programming model for resequencing buffer content optimisation in mixed-model assembly lines," International Journal of Production Research, Taylor & Francis Journals, vol. 55(10), pages 2897-2912, May.
    18. Delorme, Xavier & Dolgui, Alexandre & Kovalyov, Mikhail Y., 2012. "Combinatorial design of a minimum cost transfer line," Omega, Elsevier, vol. 40(1), pages 31-41, January.
    19. Dupont, Audrey & Linhares, Andréa Carneiro & Artigues, Christian & Feillet, Dominique & Michelon, Philippe & Vasquez, Michel, 2009. "The dynamic frequency assignment problem," European Journal of Operational Research, Elsevier, vol. 195(1), pages 75-88, May.
    20. D Biskup & M Feldmann, 2006. "Lot streaming with variable sublots: an integer programming formulation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 296-303, March.

    More about this item

    Statistics

    Access and download statistics

    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:taf:tprsxx:v:55:y:2017:i:6:p:1588-1606. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.