Analysis of a linear programming heuristic for scheduling unrelated parallel machines (Q1061599): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0166-218x(85)90009-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1965349277 / rank | |||
Normal rank |
Latest revision as of 08:26, 30 July 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
0 references