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 1095.90038
Jeng, A.A.K.; Lin, B.M.T.
Makespan minimization in single-machine scheduling with step-deterioration of processing times.
(English)
[J] J. Oper. Res. Soc. 55, No. 3, 247-256 (2004). ISSN 0160-5682

Summary: This paper considers a single-machine scheduling problem of minimizing the maximum completion time for a set of independent jobs. The processing time of a job is a non-linear step function of its starting time and due date. The problem is already known to be $\cal {NP}$-hard in the literature. In this paper, we first show this problem to be $\cal {NP}$-hard in the ordinary sense by proposing a pseudo-polynomial time dynamic programming algorithm. Then, we develop two dominance rules and a lower bound to design a branch-and-bound algorithm for deriving optimal solutions. Numerical results indicate that the proposed properties can effectively reduce the time required for exploring the solution space.
MSC 2000:
*90B35 Scheduling theory
90C39 Dynamic programming
90C60 Abstract computational complexity for math. programming problems

Keywords: single-machine scheduling; step-deterioration; makespan; dynamic programming; branch-and-bound

Highlights
Master Server