Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 28-42 |
| Number of pages | 15 |
| Journal | Discrete Applied Mathematics |
| Volume | 161 |
| Issue number | 1-2 |
| DOIs | |
| Publication status | Published - Jan 2013 |
| Externally published | Yes |
Funding
This work was supported by a grant from the Natural Sciences and Engineering Research Council of Canada (NSERC) to the first author.
| Funders | Funder number |
|---|---|
| Natural Sciences and Engineering Research Council of Canada |
Keywords
- Competitive analysis
- Semi-online algorithm
- Supply chain scheduling