Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

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

Research output: Contribution to journalArticlepeer-review

33 Scopus citations

Abstract

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP-hard for any fixed number (> 2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two-phase heuristics and dynamic two-phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account.

Original languageEnglish (US)
Pages (from-to)243-260
Number of pages18
JournalNaval Research Logistics
Volume53
Issue number4
DOIs
StatePublished - Jun 2006

All Science Journal Classification (ASJC) codes

  • Ocean Engineering
  • Modeling and Simulation
  • Management Science and Operations Research

Keywords

  • Approximation algorithms
  • NP-hard
  • Order scheduling

Fingerprint

Dive into the research topics of 'Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel'. Together they form a unique fingerprint.

Cite this