Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Non-approximability results for scheduling problems with minsum criteria
Autore:
Hoogeveen, H; Schuurman, P; Woeginger, GJ;
Indirizzi:
Univ Utrecht, Dept Comp Sci, NL-3508 TB Utrecht, Netherlands Univ UtrechtUtrecht Netherlands NL-3508 TB 3508 TB Utrecht, Netherlands Tech Univ Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands Tech Univ Eindhoven Eindhoven Netherlands NL-5600 MB dhoven, Netherlands Graz Tech Univ, Inst Math, A-8010 Graz, Austria Graz Tech Univ Graz Austria A-8010 Univ, Inst Math, A-8010 Graz, Austria
Titolo Testata:
INFORMS JOURNAL ON COMPUTING
fascicolo: 2, volume: 13, anno: 2001,
pagine: 157 - 168
SICI:
1091-9856(200121)13:2<157:NRFSPW>2.0.ZU;2-1
Fonte:
ISI
Lingua:
ENG
Soggetto:
APPROXIMATION ALGORITHMS; COMPLEXITY; TIME;
Keywords:
scheduling; unrelated parallel machines; open shop; flow shop; precedence constraints; communication delays; approximation algorithm; approximation scheme; worst-case analysis; non-approximability; L-reduction; gap-reduction; APX-hardness;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
22
Recensione:
Indirizzi per estratti:
Indirizzo: Hoogeveen, H Univ Utrecht, Dept Comp Sci, POB 80089, NL-3508 TB Utrecht, Netherlands Univ Utrecht POB 80089 Utrecht Netherlands NL-3508 TB rlands
Citazione:
H. Hoogeveen et al., "Non-approximability results for scheduling problems with minsum criteria", INFORMS J C, 13(2), 2001, pp. 157-168

Abstract

We provide several non-approximability results for deterministic scheduling problems whose objective is to minimize the total job completion time. Unless P = NP, none of the problems under consideration can be approximated in polynomial time within arbitrarily good precision. Most of our results are derived by APX-hardness proofs. We show that, whereas scheduling on unrelated machines with unit weights is polynomially solvable, the problem becomes APX-hard if release dates or weights are added. We further show APX-hardness for scheduling in flow shops, job shops, and open shops. We also investigate the problems of schedulingon parallel machines with precedence constraints and unit processing times, and two variants of the latter problem with unit communication delays; for these problems we provide lower bounds on the worst-case behavior of any polynomial-time approximation algorithm through the gap-reduction technique.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 19/01/20 alle ore 09:32:41