Single Machine Scheduling with Release Dates
We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completiontime formulation. We show their...
| Main Authors: | , , , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5211 |
| _version_ | 1826205405542350848 |
|---|---|
| author | Goemans, Michel X. Queyranne, Maurice Schulz, Andreas S. Skutella, Martin Wang, Yaoguang |
| author_facet | Goemans, Michel X. Queyranne, Maurice Schulz, Andreas S. Skutella, Martin Wang, Yaoguang |
| author_sort | Goemans, Michel X. |
| collection | MIT |
| description | We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completiontime formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent a-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least e/(e - 1) 1.5819. Both algorithms may be derandomized, their deterministic versions running in O(n2 ) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards. |
| first_indexed | 2024-09-23T13:12:27Z |
| format | Working Paper |
| id | mit-1721.1/5211 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:12:27Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52112019-04-10T15:18:11Z Single Machine Scheduling with Release Dates Goemans, Michel X. Queyranne, Maurice Schulz, Andreas S. Skutella, Martin Wang, Yaoguang approximation algorithm, LP relaxation, scheduling, online algorithm We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completiontime formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent a-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least e/(e - 1) 1.5819. Both algorithms may be derandomized, their deterministic versions running in O(n2 ) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards. 2004-05-28T19:28:17Z 2004-05-28T19:28:17Z 1999-10 Working Paper http://hdl.handle.net/1721.1/5211 en_US Operations Research Center Working Paper;OR 345-00 2377703 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | approximation algorithm, LP relaxation, scheduling, online algorithm Goemans, Michel X. Queyranne, Maurice Schulz, Andreas S. Skutella, Martin Wang, Yaoguang Single Machine Scheduling with Release Dates |
| title | Single Machine Scheduling with Release Dates |
| title_full | Single Machine Scheduling with Release Dates |
| title_fullStr | Single Machine Scheduling with Release Dates |
| title_full_unstemmed | Single Machine Scheduling with Release Dates |
| title_short | Single Machine Scheduling with Release Dates |
| title_sort | single machine scheduling with release dates |
| topic | approximation algorithm, LP relaxation, scheduling, online algorithm |
| url | http://hdl.handle.net/1721.1/5211 |
| work_keys_str_mv | AT goemansmichelx singlemachineschedulingwithreleasedates AT queyrannemaurice singlemachineschedulingwithreleasedates AT schulzandreass singlemachineschedulingwithreleasedates AT skutellamartin singlemachineschedulingwithreleasedates AT wangyaoguang singlemachineschedulingwithreleasedates |