This paper addresses the parallel machine scheduling problem with family dependent setup times and total weighted completion time minimization. In this problem, when two jobs j and k are scheduled consecutively on the same machine, a setup time is performed between the finishing time of j and the starting time of k if and only if j and k belong to different families. The problem is strongly NP-hard and is commonly addressed in the literature by heuristic approaches and by branch-and-bound algorithms. Achieving proven optimal solution is a challenging task even for small size instances. Our contribution is to introduce five novel mixed integer linear programs based on concepts derived from one-commodity, arc-flow and set covering formulations. Numerical experiments on more than 13000 benchmark instances show that one of the arc-flow models and the set covering model are quite efficient, as they provide on average better solutions than state-of-the-art approaches, with shorter computation times, and solve to proven optimality a large number of open instances from the literature.

Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization / Kramer, A.; Iori, M.; Lacomme, P.. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 289:3(2021), pp. 825-840. [10.1016/j.ejor.2019.07.006]

Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization

Kramer A.
;
Iori M.;
2021

Abstract

This paper addresses the parallel machine scheduling problem with family dependent setup times and total weighted completion time minimization. In this problem, when two jobs j and k are scheduled consecutively on the same machine, a setup time is performed between the finishing time of j and the starting time of k if and only if j and k belong to different families. The problem is strongly NP-hard and is commonly addressed in the literature by heuristic approaches and by branch-and-bound algorithms. Achieving proven optimal solution is a challenging task even for small size instances. Our contribution is to introduce five novel mixed integer linear programs based on concepts derived from one-commodity, arc-flow and set covering formulations. Numerical experiments on more than 13000 benchmark instances show that one of the arc-flow models and the set covering model are quite efficient, as they provide on average better solutions than state-of-the-art approaches, with shorter computation times, and solve to proven optimality a large number of open instances from the literature.
2021
5-lug-2019
289
3
825
840
Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization / Kramer, A.; Iori, M.; Lacomme, P.. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 289:3(2021), pp. 825-840. [10.1016/j.ejor.2019.07.006]
Kramer, A.; Iori, M.; Lacomme, P.
File in questo prodotto:
File Dimensione Formato  
KIL_PswC.pdf

Open access

Descrizione: Versione pre print
Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 383.73 kB
Formato Adobe PDF
383.73 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1186979
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 20
social impact