Özet
Suppose a distribution center receives orders from customers for delivery of some goods. Orders may be delayed to be grouped and delivered in batches. The cost of one delivery does not depend on the number of orders taken. The total cost (to be minimized) is the sum of the total delay time of the orders and the total delivery cost. In the on-line environment, where at any time there is no information about future orders, there is a simple on-line algorithm with competitive ratio 2 which is known to be the best possible. We consider the semi-online environment where at any instant we know the orders that will be released in the next S time units, but have no information about the orders that will be released later. For this environment, we present a semi-online algorithm and analyze its competitive ratio.
| Orijinal dil | İngilizce |
|---|---|
| Sayfa (başlangıç-bitiş) | 28-42 |
| Sayfa sayısı | 15 |
| Dergi | Discrete Applied Mathematics |
| Hacim | 161 |
| Basın numarası | 1-2 |
| DOI'lar | |
| Yayın durumu | Yayınlandı - Oca 2013 |
| Harici olarak yayınlandı | Evet |
Finansman
This work was supported by a grant from the Natural Sciences and Engineering Research Council of Canada (NSERC) to the first author.
| Finansörler | Finansör numarası |
|---|---|
| Natural Sciences and Engineering Research Council of Canada |