Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0903.90100
Kovalyov, Mikhail Y.; Kubiak, Wieslaw
A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs. (English)
[J] J. Heuristics 3, No.4, 287-297 (1998). ISSN 1381-1231; ISSN 1572-9397/e

Summary: A fully polynomial approximation scheme for the problem of scheduling $n$ deteriorating jobs on a single machine to minimize makespan is presented. Each algorithm of the scheme runs in $O(n^5L^4/\varepsilon^3)$ time, where $L$ is the number of bits in the binary encoding of the largest numerical parameter in the input, and $\varepsilon$ is required relative error. The idea behind the scheme is rather general and it can be used to develop fully polynomial approximation schemes for other combinatorial optimization problems. Main feature of the scheme is that it does not require any prior knowledge of lower and/or upper bounds on the value of optimal solutions.

MSC 2000:: *90B35 Scheduling theory

Keywords: fully polynomial approximation scheme; deteriorating jobs; single machine; makespan

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]