Abstract
A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minimized. Deliveries to different customers cannot be combined. We present an on-line algorithm with the competitive ratio bounded by 3+α, where α is the ratio of the largest processing time to the smallest processing time.
| Original language | English |
|---|---|
| Pages (from-to) | 710-714 |
| Number of pages | 5 |
| Journal | Operations Research Letters |
| Volume | 41 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 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
- Integrated production-distribution problems
- On-line algorithm
- Supply chain scheduling