Order scheduling in an environment with dedicated resources in parallel

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

Research output: Contribution to journalArticlepeer-review

68 Scopus citations

Abstract

We consider m machines in parallel with each machine capable of producing one specific product type. There are n orders with each one requesting specific quantities of the various different product types. Order j may have a release date r j and a due date d j. The different product types for order j can be produced at the same time. We consider the class of objectives Σ fj(Cj) that includes objectives such as the total weighted completion time Σ wjCj and the total weighted tardiness Σ wjTj of the n orders. We present structural properties of the various problems and a complexity result. In particular, we show that minimizing Σ Cj when m ≥ 3 is strongly NP-hard. We introduce two new heuristics for the Σ Cj objective. An empirical analysis shows that our heuristics outperform all heuristics that have been proposed for this problem in the literature.

Original languageEnglish (US)
Pages (from-to)355-386
Number of pages32
JournalJournal of Scheduling
Volume8
Issue number5
DOIs
StatePublished - Oct 2005

All Science Journal Classification (ASJC) codes

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Keywords

  • Approximation
  • NP-hard
  • Order scheduling
  • Tabu Search
  • Total completion time

Fingerprint Dive into the research topics of 'Order scheduling in an environment with dedicated resources in parallel'. Together they form a unique fingerprint.

Cite this