1958 publicerade Wagner och Whitin en seminaltidning om det deterministiska problemet med okapacitet, en grundläggande modell som är inbäddad i många praktiska produktionsplaneringsproblem. I det här dokumentet överväger vi en grundläggande version av denna modell där krav (och andra problemparametrar) är stokastiska: det stokastiska icke-funktionshindrade lot-sizing problemet (SULS). Vi definierar produktionsbanan för en optimal lösning för vår modell och använder denna fastighet för att utveckla en bakåtgående dynamisk programmeringsrekursion. Detta tillvägagångssätt gör att vi kan visa att värdefunktionen är bitvis linjär och rätt kontinuerlig. Vi använder sedan dessa resultat för att visa att en fullständig karakterisering av den optimala värdefunktionen kan uppnås genom en dynamisk programmeringsalgoritm i polynom tid för fallet att varje icke-blad nod innehåller minst två barn. Dessutom visar vi att vår strategi leder till en polynom tid algoritm för att få en optimal lösning på alla fall av SULS, oavsett strukturen i scenariot träd. Vi visar också att värdefunktionen för problemet utan installationskostnader är kontinuerlig, bitvis linjär och konvex, och därför kan en ännu mer effektiv dynamisk programmeringsalgoritm utvecklas för detta specialfall.
REF presenterade en dynamisk programmeringsmetod som bestämmer en lösning för den stokastiska okapaciteterade partistorleksproblem i polynom tid.
Polynomial time algorithms for stochastic uncapacitated lot-sizing problems
{'venue': 'Operations Research', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}