Preemptive multiprocessor order scheduling to minimize total weighted flowtime

Joseph Y.T. Leung, C. Y. Lee, C. W. Ng, G. H. Young

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Consider m identical machines in parallel, each of which can produce k different product types. There is no setup cost when the machines switch from producing one product type to another. There are n orders each of which requests various quantities of the different product types. All orders are available for processing at time t = 0, and preemption is allowed. Order i has a weight wi and its completion time is the time when its last requested product type finishes. Our goal is to find a preemptive schedule such that the total weighted completion time ∑ wi Ci is minimized. We show that this problem is NP-hard even when all jobs have identical weights and there are only two machines. Motivated by the computational complexity of the problem, we propose a simple heuristic and show that it obeys a worst-case bound of 2 - 1/m. Finally, empirical studies show that our heuristic performs very well when compared with a lower bound of the optimal cost.

Original languageEnglish (US)
Pages (from-to)40-51
Number of pages12
JournalEuropean Journal of Operational Research
Volume190
Issue number1
DOIs
StatePublished - Oct 1 2008

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Flexible machines
  • Heuristics
  • NP-hard
  • Order scheduling
  • Total weighted completion time

Fingerprint Dive into the research topics of 'Preemptive multiprocessor order scheduling to minimize total weighted flowtime'. Together they form a unique fingerprint.

Cite this