Abstrakt. I Cloud-system hanterar vi ofta jobb som anländer och avgår online. Vid ankomsten bör ett jobb tilldelas en server. Varje jobb har en storlek som definierar den mängd resurser som det behöver. Servererna har en enhetlig kapacitet och vid varje tidpunkt bör den totala storleken på de jobb som tilldelas en server inte överstiga kapaciteten. Denna inställning är nära relaterad till den klassiska bin förpackning problem. Skillnaden är att, i bin packning, målet är att minimera det totala antalet använda servrar. I molnet är dock avgiften för varje server proportionell mot längden på det tidsintervall den hyrs ut för, och målet är att minimera kostnaden för att hyra alla använda servrar. Nyligen övervägdes vissa paketeringsstrategier för att hyra servrar i molnet [Li et al. SPAA'14. Där bevisas det att alla Any-Fit bin förpackningsstrategi har ett konkurrenskraftigt förhållande på minst μ, där μ är max/min intervall längd förhållandet mellan jobb. Det visas också att First Fit har ett konkurrensförhållande på 2μ + 13 medan Best Fit inte alls är konkurrenskraftigt. Vi observerar att den nedre gränsen av μ sträcker sig till alla online-algoritmer. Vi visar också att, överraskande, Next Fit algoritm har konkurrensförhållande på högst 2μ + 1. Vi visar också att en variant av Next Fit uppnår ett konkurrensförhållande på K × max{1, μ/(K − 1)} + 1, där K är en parameter för algoritmen. I synnerhet, om värdet av μ är känt, algoritmen har en kompetitiv kvot på μ + 2; detta förbättras på den befintliga övre gränsen av μ + 8. Slutligen introducerar vi en enkel algoritm som heter Move To Front (MTF) som har ett konkurrenskraftigt förhållande på högst 6μ + 7 och även lovande genomsnittliga prestanda. Vi studerar experimentellt den genomsnittliga prestandan hos olika algoritmer och observerar att MTF:s typiska beteende är tydligt bättre än andra algoritmer.
Kamali och Ortiz REF förbättrade den övre gränsen för Next-Fit och introducerade en ny algoritm, Move To Front, som gjorde det bästa i genomsnitt fallet för den dynamiska bin förpackning total kostnad minimization problem.
Efficient Online Strategies for Renting Servers in the Cloud
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}