The Generalized Assignment Problem and Extensions

Dolores Romero Morales, H. Edwin Romeijn

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

Abstract

In this chapter we have described the state of the art in solving the Generalized Assignment Problem, as well as many extensions thereof. The approach we have taken is to generalize the GAP to a much larger class of Convex Assignment Problems, show that many of the extensions of the GAP proposed in the literature are members of this class, and describe many of the proposed solution approaches to the GAP in terms of the larger class of problems. Throughout the chapter we have paid particular attention to the Generalized Assignment Problem, the Multi-Resource Generalized Assignment Problem, and the Multi-Period Single-Sourcing Problem.
In this chapter we have described the state of the art in solving the Generalized Assignment Problem, as well as many extensions thereof. The approach we have taken is to generalize the GAP to a much larger class of Convex Assignment Problems, show that many of the extensions of the GAP proposed in the literature are members of this class, and describe many of the proposed solution approaches to the GAP in terms of the larger class of problems. Throughout the chapter we have paid particular attention to the Generalized Assignment Problem, the Multi-Resource Generalized Assignment Problem, and the Multi-Period Single-Sourcing Problem.
LanguageEnglish
Title of host publicationHandbook of Combinatorial Optimization : Supplement Volume B
EditorsDing-Zhu Du, Panos M Pardalos
VolumeB
Place of PublicationBoston, MA
PublisherSpringer
Date2005
Pages259-311
ISBN (Print)9780387238296
ISBN (Electronic)9780387238302
DOIs
StatePublished - 2005
Externally publishedYes

Keywords

    Cite this

    Morales, D. R., & Romeijn, H. E. (2005). The Generalized Assignment Problem and Extensions. In D-Z. Du, & P. M. Pardalos (Eds.), Handbook of Combinatorial Optimization: Supplement Volume B (Vol. B, pp. 259-311). Boston, MA: Springer. DOI: 10.1007/b102533
    Morales, Dolores Romero ; Romeijn, H. Edwin. / The Generalized Assignment Problem and Extensions. Handbook of Combinatorial Optimization: Supplement Volume B. editor / Ding-Zhu Du ; Panos M Pardalos. Vol. B Boston, MA : Springer, 2005. pp. 259-311
    @inbook{8ab5d3a1c0b74bcfbbebef4aa5978c2e,
    title = "The Generalized Assignment Problem and Extensions",
    abstract = "In this chapter we have described the state of the art in solving the Generalized Assignment Problem, as well as many extensions thereof. The approach we have taken is to generalize the GAP to a much larger class of Convex Assignment Problems, show that many of the extensions of the GAP proposed in the literature are members of this class, and describe many of the proposed solution approaches to the GAP in terms of the larger class of problems. Throughout the chapter we have paid particular attention to the Generalized Assignment Problem, the Multi-Resource Generalized Assignment Problem, and the Multi-Period Single-Sourcing Problem.",
    keywords = "Operations Research, Mathematical Programming, Combinatorics, Systems Theory, Control, Computer Science, general",
    author = "Morales, {Dolores Romero} and Romeijn, {H. Edwin}",
    year = "2005",
    doi = "10.1007/b102533",
    language = "English",
    isbn = "9780387238296",
    volume = "B",
    pages = "259--311",
    editor = "Ding-Zhu Du and Pardalos, {Panos M}",
    booktitle = "Handbook of Combinatorial Optimization",
    publisher = "Springer",
    address = "Germany",

    }

    Morales, DR & Romeijn, HE 2005, The Generalized Assignment Problem and Extensions. in D-Z Du & PM Pardalos (eds), Handbook of Combinatorial Optimization: Supplement Volume B. vol. B, Springer, Boston, MA, pp. 259-311. DOI: 10.1007/b102533

    The Generalized Assignment Problem and Extensions. / Morales, Dolores Romero; Romeijn, H. Edwin.

    Handbook of Combinatorial Optimization: Supplement Volume B. ed. / Ding-Zhu Du; Panos M Pardalos. Vol. B Boston, MA : Springer, 2005. p. 259-311.

    Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

    TY - CHAP

    T1 - The Generalized Assignment Problem and Extensions

    AU - Morales,Dolores Romero

    AU - Romeijn,H. Edwin

    PY - 2005

    Y1 - 2005

    N2 - In this chapter we have described the state of the art in solving the Generalized Assignment Problem, as well as many extensions thereof. The approach we have taken is to generalize the GAP to a much larger class of Convex Assignment Problems, show that many of the extensions of the GAP proposed in the literature are members of this class, and describe many of the proposed solution approaches to the GAP in terms of the larger class of problems. Throughout the chapter we have paid particular attention to the Generalized Assignment Problem, the Multi-Resource Generalized Assignment Problem, and the Multi-Period Single-Sourcing Problem.

    AB - In this chapter we have described the state of the art in solving the Generalized Assignment Problem, as well as many extensions thereof. The approach we have taken is to generalize the GAP to a much larger class of Convex Assignment Problems, show that many of the extensions of the GAP proposed in the literature are members of this class, and describe many of the proposed solution approaches to the GAP in terms of the larger class of problems. Throughout the chapter we have paid particular attention to the Generalized Assignment Problem, the Multi-Resource Generalized Assignment Problem, and the Multi-Period Single-Sourcing Problem.

    KW - Operations Research, Mathematical Programming

    KW - Combinatorics

    KW - Systems Theory, Control

    KW - Computer Science, general

    U2 - 10.1007/b102533

    DO - 10.1007/b102533

    M3 - Book chapter

    SN - 9780387238296

    VL - B

    SP - 259

    EP - 311

    BT - Handbook of Combinatorial Optimization

    PB - Springer

    CY - Boston, MA

    ER -

    Morales DR, Romeijn HE. The Generalized Assignment Problem and Extensions. In Du D-Z, Pardalos PM, editors, Handbook of Combinatorial Optimization: Supplement Volume B. Vol. B. Boston, MA: Springer. 2005. p. 259-311. Available from, DOI: 10.1007/b102533