I det här dokumentet introducerar vi knapsack-problemet för lättfördärvliga lager när det gäller optimal dynamisk fördelning av en produktsamling till en begränsad knapsack. Motiveringen för att utforma ett sådant problem kommer från intäktsförvaltningen i detaljhandeln, där olika produkter ofta har en tillhörande livslängd under vilken de endast kan säljas, och cheferna kan regelbundet välja vissa produkter som ska tilldelas ett begränsat marknadsföringsutrymme som förväntas locka fler kunder än standardhyllorna. En annan motivation kommer från schemaläggning av förfrågningar i moderna multiserver datacenter så att kvaliteten på servicekrav som ges av slutförande deadlines är uppfyllda. Med hjälp av Lagrangian strategi vi härleda en optimal index policy för Whittle lättnad av problemet där knapsack kapacitet används endast i genomsnitt. Om vi antar en viss struktur av den optimala policyn för eninventeringskontroll, bevisar vi indexerbarhet och härleder en effektiv, linjär tid algoritm för beräkning av indexvärden. Såvitt vi vet är vårt papper det första som ger indexerbarhetsanalys av en rastlös bandit med tvådimensionellt tillstånd (livstid och lagernivå). Vi illustrerar att dessa indexvärden är numeriskt nära de verkliga indexvärdena när en sådan struktur inte finns. Vi testar två indexbaserade heuristik för det ursprungliga, icke-relaxerade problemet: (1) en konventionell indexregel, som föreskriver att beställa produkterna enligt deras nuvarande indexvärden och främjar så många produkter som passar i knapsacken, och (2) en nyligen föreslagen index-knapsack heuristic, som använder indexvärdena som en proxy för priset på marknadsföring och föreslår att lösa en deterministisk knapsack problem att välja produkterna. Genom en systematisk beräkningsstudie visar vi att prestandan hos båda heuristikerna är nästan optimal, och att index-knapsack heuristiska överträffar den konventionella indexregeln.
Vårt dokument fastställer också den asymptotiska prestandan för Whittle indexpolicy, medan REF tog upp indexerbarheten och utvecklade en iterativ algoritm för att beräkna Whittle index.
Generalized Restless Bandits and the Knapsack Problem for Perishable Inventories
{'venue': 'Oper. Res.', 'journal': 'Oper. Res.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}