Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

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

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space.

Original languageEnglish (US)
Pages (from-to)107-123
Number of pages17
JournalAnnals of Operations Research
Volume159
Issue number1
DOIs
StatePublished - Mar 2008

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Management Science and Operations Research

Keywords

  • Approximation algorithms
  • NP-hard
  • Order scheduling
  • Total weighted completion time

Fingerprint

Dive into the research topics of 'Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time'. Together they form a unique fingerprint.

Cite this