Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

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

Highlights
Master Server