Scheduling orders for multiple product types to minimize total weighted completion time

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

Research output: Contribution to journalArticlepeer-review

55 Scopus citations

Abstract

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (≥ 2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.

Original languageEnglish (US)
Pages (from-to)945-970
Number of pages26
JournalDiscrete Applied Mathematics
Volume155
Issue number8
DOIs
StatePublished - Apr 15 2007

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Approximation algorithms
  • Design and analysis of algorithms
  • Order scheduling

Fingerprint

Dive into the research topics of 'Scheduling orders for multiple product types to minimize total weighted completion time'. Together they form a unique fingerprint.

Cite this