We consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. This problem models many real-world applications in which jobs must be assigned to agents but the costs of assignment may vary after the decision has been taken. We computationally examine two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. We also examine exact algorithmic approaches (Benders-like decomposition and branch-and-cut) and further introduce a more sophisticated algorithm that incorporates various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.
Exact and heuristic algorithms for the interval min-max regret generalized assignment problem / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: COMPUTERS & INDUSTRIAL ENGINEERING. - ISSN 0360-8352. - 125(2018), pp. 98-110.
Data di pubblicazione: | 2018 |
Data di prima pubblicazione: | 14-ago-2018 |
Titolo: | Exact and heuristic algorithms for the interval min-max regret generalized assignment problem |
Autore/i: | Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori |
Autore/i UNIMORE: | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.cie.2018.08.007 |
Rivista: | |
Volume: | 125 |
Pagina iniziale: | 98 |
Pagina finale: | 110 |
Codice identificativo ISI: | WOS:000449569500008 |
Codice identificativo Scopus: | 2-s2.0-85051787994 |
Citazione: | Exact and heuristic algorithms for the interval min-max regret generalized assignment problem / Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori. - In: COMPUTERS & INDUSTRIAL ENGINEERING. - ISSN 0360-8352. - 125(2018), pp. 98-110. |
Tipologia | Articolo su rivista |
File in questo prodotto:

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris