Heuristics for parallel machine scheduling with delivery times (Q1338896)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 695004
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Heuristics for parallel machine scheduling with delivery times |
scientific article; zbMATH DE number 695004 |
Statements
Heuristics for parallel machine scheduling with delivery times (English)
0 references
23 November 1994
0 references
A parallel machine scheduling problem is considered in which each job has a processing time and a delivery time. The objective is to find a schedule which minimizes the time by which all jobs are delivered. For a single machine this problem is easily solved in polynomial time, for \(m \geq 2\) machines it becomes NP-hard. Several heuristics using list scheduling as a subroutine are proposed and a tight worst-case analysis is given. The best one of our heuristics has a worst-case performance guarantee of \(2 - 2/(m + 1)\). For the on-line case we give a heuristic with the (best possible) worst-case performance of two.
0 references
identical parallel machines
0 references
parallel machine scheduling problem
0 references
delivery time
0 references
heuristics
0 references
worst-case analysis
0 references
0.8747236132621765
0 references
0.8739724159240723
0 references
0.872776210308075
0 references
0.8542043566703796
0 references
0.8467820286750793
0 references
