Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions

A.P.M. Wagelmans, B. Moerman, C.P.M. Hoesel, van

    Onderzoeksoutput: Boek/rapportRapportAcademic

    69 Downloads (Pure)

    Samenvatting

    In this paper we discuss two basic geometric techniques that can be used to speed up certain types of dynamic programs. We first present the algorithms in a general form, and then we show how these techniques can be applied to the economic lot-sizing problem and extensions. Furthermore, it is illustrated that the geometric techniques can be used to give elegant and insightful proofs of structural results, like Wagner and Whitin's planning horizon theorem. Finally, we present results of computational experiments in which new algorithms for the economic lot-sizing problem are compared with each other, as well as with other algorithms from the literature. Keywords: Dynamic programming, computational analysis, lot-sizing, inventory
    Originele taal-2Engels
    Plaats van productieEindhoven
    UitgeverijTechnische Universiteit Eindhoven
    Aantal pagina's30
    StatusGepubliceerd - 1992

    Publicatie series

    NaamMemorandum COSOR
    Volume9245
    ISSN van geprinte versie0926-4493

    Vingerafdruk Duik in de onderzoeksthema's van 'Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit