Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal 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]