Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10523980 | Operations Research Letters | 2013 | 5 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Igor Averbakh, Mehmet Baysan,