Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 0936.90026
Kubiak, Wieslaw; van de Velde, Steef
Scheduling deteriorating jobs to minimize makespan. (English)
[J] Nav. Res. Logist. 45, No.5, 511-523 (1998). ISSN 0894-069X; ISSN 1520-6750/e

Summary: We consider a single-machine problem of scheduling $n$ independent jobs to minimize makespan, in which the processing time of job $J_j$ grows by $w_j$ with each time unit its start is delayed beyond a given common critical date $d$. This processing time is $p_j$ if $J_j$ starts by $d$. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in $O(nd \sum_{j=1}^n p_i)$ time and $O(nd)$ space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date $D>d$. For this case, we give two pseudopolynomial time algorithms: one runs in $O(n^2 d(D-d) \sum_{j=1}^n p_j)$ time and $O(nd (D-d))$ space, the other runs in $O(nd \sum_{j=1}^n w_j (\sum_{j=1}^n p_j)^2)$ time and $O(nd \sum_{j=1}^n w_j \sum_{j=1}^n p_j)$ space.

MSC 2000:: *90B35 Scheduling theory
90C39 Dynamic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords: single-machine scheduling; deteriorating jobs; NP-hardness; dynamic programming; pseudopolynomial algorithm; branch and bound algorithm

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]