Makespan minimization in single-machine scheduling with step-deterioration of processing times

A A K Jeng and B M T Lin ()
Additional contact information
A A K Jeng: National Chi Nan University
B M T Lin: National Chi Nan University

Journal of the Operational Research Society, 2004, vol. 55, issue 3, 247-256

Abstract: Abstract 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 𝒩𝒫-hard in the literature. In this paper, we first show this problem to be 𝒩𝒫-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.

Keywords: single-machine scheduling; step-deterioration; makespan; dynamic programming; branch-and-bound (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601693 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:55:y:2004:i:3:d:10.1057_palgrave.jors.2601693

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601693

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().