Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive r...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/4048 |
| _version_ | 1826207056070180864 |
|---|---|
| author | Megow, Nicole Schulz, Andreas S. |
| author_facet | Megow, Nicole Schulz, Andreas S. |
| author_sort | Megow, Nicole |
| collection | MIT |
| description | We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios compared to the previously best-known deterministic on-line algorithms, which are (4+epsilon)-competitive in either case. Our preemptive algorithm is 2-competitive, which actually meets the competitive ratio of the currently best randomized on-line algorithm for this scenario. Our nonpreemptive algorithm has a competitive ratio of 3.28. Both results are characterized by a surprisingly simple analysis; moreover, the preemptive algorithm also works in the less clairvoyant environment in which only the ratio of weight to processing time of a job becomes known at its release date, but neither its actual weight nor its processing time. In the corresponding nonpreemptive situation, every on-line algorithm has an unbounded competitive ratio |
| first_indexed | 2024-09-23T13:43:28Z |
| format | Working Paper |
| id | mit-1721.1/4048 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:43:28Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/40482019-04-12T08:25:02Z Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms Megow, Nicole Schulz, Andreas S. Scheduling Sequencing Approximation Algorithms On-line Algorithms Competitive Ratio We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios compared to the previously best-known deterministic on-line algorithms, which are (4+epsilon)-competitive in either case. Our preemptive algorithm is 2-competitive, which actually meets the competitive ratio of the currently best randomized on-line algorithm for this scenario. Our nonpreemptive algorithm has a competitive ratio of 3.28. Both results are characterized by a surprisingly simple analysis; moreover, the preemptive algorithm also works in the less clairvoyant environment in which only the ratio of weight to processing time of a job becomes known at its release date, but neither its actual weight nor its processing time. In the corresponding nonpreemptive situation, every on-line algorithm has an unbounded competitive ratio 2004-02-06T20:52:54Z 2004-02-06T20:52:54Z 2004-02-06T20:52:54Z Working Paper http://hdl.handle.net/1721.1/4048 en_US MIT Sloan School of Management Working Paper;4435-03 136628 bytes application/pdf application/pdf |
| spellingShingle | Scheduling Sequencing Approximation Algorithms On-line Algorithms Competitive Ratio Megow, Nicole Schulz, Andreas S. Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms |
| title | Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms |
| title_full | Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms |
| title_fullStr | Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms |
| title_full_unstemmed | Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms |
| title_short | Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms |
| title_sort | scheduling to minimize average completion time revisited deterministic on line algorithms |
| topic | Scheduling Sequencing Approximation Algorithms On-line Algorithms Competitive Ratio |
| url | http://hdl.handle.net/1721.1/4048 |
| work_keys_str_mv | AT megownicole schedulingtominimizeaveragecompletiontimerevisiteddeterministiconlinealgorithms AT schulzandreass schedulingtominimizeaveragecompletiontimerevisiteddeterministiconlinealgorithms |