Exact and approximate algorithms for the multi-period procurement problem where dedicated supplier capacity can be reserved

Abstract

This paper is concerned with a multi-period inventory problem where the demand and the supplier capacity of a given key resource are discrete random variables with known probability distribution. The procurement manager has to answer two types of questions: how much supplier quantity to reserve for each period (where all of these reservations have to madeprior to the start of the first period) and how large an order quantity to use at start of each period. An exact procedure, based on branch and bound and dynamic programming, as well as various heuristic methods to solve the problem are presented in this paper. Heuristic methods are shown to perform extremely well in the sense that they provide near optimal strategies while requiring much less computational effort than the exact method.

Zusammenfassung

Vorliegende Arbeit behandelt ein mehrperiodiges Lagerhaltungsproblem, worin sowohl die Nachfrage als auch die Lieferkapazität eines bestimmten Rohstoffs diskrete Zufallsvariable mit bekannter Verteilungsfunktion sind. Vor Beginn der ersten Periode ist die beim Lieferanten zu reservierende Rohstoffmenge für jede Periode zu bestimmen, darauf anschließend ist zu Beginn jeder Periode die tatsächlich zu bestellende Rohstoffmenge zu bestimmen. Ein exakter, aufbranch and bound und dynamischer Programmierung basierender Algorithmus und verschiedene Heuristiken für dieses Problem werden vorgestellt und miteinander verglichen. Die Heuristiken schneiden dabei sehr gut ab, da sie ausgezeichnete, suboptimale Lösungen mit erheblich weniger Rechenaufwand finden.