Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs

A. A K Jeng, Miao-Tsong Lin*

*Corresponding author for this work

Research output: Contribution to journalArticle

23 Scopus citations

Abstract

In this paper, we study a scheduling problem of minimizing the total completion time on a single machine where the processing time of a job is a step function of its starting time and a due date that is common to all jobs. This problem has been shown to be script N sign ℘-hard in the literature. To derive optimal solutions from a practical aspect, we develop a lower bound and two elimination rules to design branch-and-bound algorithms. Through computational experiments, we show that the proposed properties are effective in curtailing unnecessary explorations during the solution-finding process, and that the synergy of these properties can solve problems with up to 100 jobs in a few seconds.

Original languageEnglish
Pages (from-to)521-536
Number of pages16
JournalComputers and Operations Research
Volume32
Issue number3
DOIs
StatePublished - 1 Mar 2005

Keywords

  • Branch-and-bound algorithm
  • Single-machine scheduling
  • Step deterioration
  • Total completion time

Fingerprint Dive into the research topics of 'Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs'. Together they form a unique fingerprint.

  • Cite this