Det gemensamma påfyllningsproblemet (JRP) handlar om att optimera varutransporter från en leverantör till detaljhandlare genom ett gemensamt lager. Varje transport innebär transport av varor från leverantören till lagret, till en fast kostnad C, följt av en omfördelning av dessa varor från lagret till de återförsäljare som beställde dem, där transport av varor till en återförsäljare ρ har en fast kostnad c ρ. Dessutom ådrar sig detaljhandlarna kostnader för att vänta på varje beställning. Målet är att minimera den totala kostnaden för att uppfylla alla order, nämligen summan av alla frakt- och väntekostnader. JRP har studerats väl inom Operations Research och, på senare tid, inom området approximationsalgoritmer. För godtyckliga väntande kostnadsfunktioner är den mest kända approximationen 1,8. Detta förhållande kan minskas till 1 574 för JRP-D-modellen, där det inte finns några kostnader för att vänta men beställningar har tidsfrister. När det gäller hårdhetsresultat är det känt att problemet är APX-hård och att det naturliga linjära programmet för JRP har integrality gap minst 1.245. Båda resultaten håller även för JRP-D. I online-scenariot är de bästa lägre och övre gränserna för konkurrensförhållandet 2,64 respektive 3. Den nedre gränsen på 2.64 gäller även för den begränsade versionen av JRP, betecknad JRP-L, där väntekostnadsfunktionen är linjär. Vi tillhandahåller flera nya approximativa resultat för JRP. I offline-fallet ger vi en algoritm med förhållandet 1 791 som bryter barriären på 1,8. I online-fallet visar vi en lägre gräns på 2 754 för konkurrensförhållandet för JRP-L (och därmed även JRP), vilket förbättrar den tidigare gränsen på 2,64. Vi studerar också onlineversionen av JRP-D, där vi bevisar att det optimala konkurrensförhållandet är 2.
För deadline fall den bästa nedre gränsen är 2 REF.
Better Approximation Bounds for the Joint Replenishment Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}