Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines

Joseph Y.T. Leung, Haibing Li, Michael Pinedo, Jiawei Zhang

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

We consider the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. Preemptions are allowed. The completion time of an order is the finish time of the product type that is completed last for that order. The objective is to minimize the total weighted completion time. We propose heuristics for the non-preemptive as well as the preemptive case and obtain worst case bounds that are a function of the number of machines as well as the differences in the speeds of the machines. Even though the worst-case bounds we showed for the two heuristics are not very tight, our experimental results show that they yield solutions that are very close to optimal.

Original languageEnglish (US)
Pages (from-to)119-129
Number of pages11
JournalInformation Processing Letters
Volume103
Issue number3
DOIs
StatePublished - Jul 31 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis of algorithms
  • Flexible machines
  • Heuristics
  • Order scheduling
  • Uniform machines

Fingerprint

Dive into the research topics of 'Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines'. Together they form a unique fingerprint.

Cite this