An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling
Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each of which running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arr...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/3878 |
| _version_ | 1826202154698801152 |
|---|---|
| author | Chou, Mabel Queyranne, Maurice Simchi-Levi, David |
| author_facet | Chou, Mabel Queyranne, Maurice Simchi-Levi, David |
| author_sort | Chou, Mabel |
| collection | MIT |
| description | Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each of which running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) on-line heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. We prove that the WSPR heuristic is asymptotically optimal for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation of the problem. |
| first_indexed | 2024-09-23T12:02:44Z |
| format | Article |
| id | mit-1721.1/3878 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:02:44Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/38782019-04-12T08:07:19Z An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling Chou, Mabel Queyranne, Maurice Simchi-Levi, David Weighted Shortest Processing Requirement on-line heuristic job processing requirements and weights Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each of which running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) on-line heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. We prove that the WSPR heuristic is asymptotically optimal for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation of the problem. Singapore-MIT Alliance (SMA) 2003-12-14T22:27:17Z 2003-12-14T22:27:17Z 2004-01 Article http://hdl.handle.net/1721.1/3878 en_US High Performance Computation for Engineered Systems (HPCES); 124605 bytes application/pdf application/pdf |
| spellingShingle | Weighted Shortest Processing Requirement on-line heuristic job processing requirements and weights Chou, Mabel Queyranne, Maurice Simchi-Levi, David An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling |
| title | An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling |
| title_full | An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling |
| title_fullStr | An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling |
| title_full_unstemmed | An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling |
| title_short | An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling |
| title_sort | asymptotically optimal on line algorithm for parallel machine scheduling |
| topic | Weighted Shortest Processing Requirement on-line heuristic job processing requirements and weights |
| url | http://hdl.handle.net/1721.1/3878 |
| work_keys_str_mv | AT choumabel anasymptoticallyoptimalonlinealgorithmforparallelmachinescheduling AT queyrannemaurice anasymptoticallyoptimalonlinealgorithmforparallelmachinescheduling AT simchilevidavid anasymptoticallyoptimalonlinealgorithmforparallelmachinescheduling AT choumabel asymptoticallyoptimalonlinealgorithmforparallelmachinescheduling AT queyrannemaurice asymptoticallyoptimalonlinealgorithmforparallelmachinescheduling AT simchilevidavid asymptoticallyoptimalonlinealgorithmforparallelmachinescheduling |