Analysis of a linear programming heuristic for scheduling unrelated parallel machines (Q1061599): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q170009 |
||
Property / author | |||
Property / author: Chris N. Potts / rank | |||
Revision as of 06:39, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Analysis of a linear programming heuristic for scheduling unrelated parallel machines |
scientific article |
Statements
Analysis of a linear programming heuristic for scheduling unrelated parallel machines (English)
0 references
1985
0 references
Each of n jobs is to be processed without interruption on one of m unrelated parallel machines. The objective is to minimize the maximum completion time. A heuristic method is presented, the first stage of which uses linear programming to form a partial schedule leaving at most m-1 jobs unscheduled: the second stage schedules these m-1 jobs using an enumerative method. For \(m\geq 3\), it is shown that the heuristic has a (best possible) worst-case performance ratio of 2 and has a computational requirement which is polynomial in n although it is exponential in m. For \(m=2\), it is shown that the heuristic has a (best possible) worst-case performance ratio of \((1+\sqrt{5})/2\) and requires linear time. A modified version of the heuristic is presented for \(m=2\) which is shown to have a (best possible) worst-case performance ratio of 3/2 while still requiring linear time.
0 references
unrelated parallel machines
0 references
maximum completion time
0 references
heuristic method
0 references
worst-case performance
0 references