A note on parallel-machine scheduling with deteriorating jobs

A. A K Jeng, Miao-Tsong Lin*

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

We consider a parallel-machine scheduling problem of minimizing the total completion time. The processing time of a job is a linear function of its starting time and deterioration rate. This problem is known to be NP-hard, even for the case with two machines. In this note, we generalize an existing lower bound for the two-machine case to the general case with an arbitrary number of machines. Despite the generalization concerning machine number, our bound has one extra term that makes our bound tighter than the existing one.Journal of the Operational Research Society (2007) 58, 824-826. doi:10.1057/palgrave.jors. 2602208 Published online 26 April 2006.

Original languageEnglish
Pages (from-to)824-826
Number of pages3
JournalJournal of the Operational Research Society
Volume58
Issue number6
DOIs
StatePublished - 1 Jun 2007

Keywords

  • Lower bound
  • Parallel-machine scheduling
  • Time-dependent processing time

Fingerprint Dive into the research topics of 'A note on parallel-machine scheduling with deteriorating jobs'. Together they form a unique fingerprint.

  • Cite this