Scheduling orders for multiple product types with due date related objectives

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

Research output: Contribution to journalArticlepeer-review

46 Scopus citations


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 has a release date rj and a due date dj. The different product types for order j can be produced at the same time. We consider various due date related objectives such as the minimization of the maximum lateness Lmax and the total number of late orders ∑Uj. We present polynomial time algorithms for the easy cases and heuristics for NP-hard cases. For minimizing ∑Uj, we also propose an exact algorithm based on Constraint Propagation and bounding strategy. The effectiveness of the algorithms is demonstrated through an empirical study.

Original languageEnglish (US)
Pages (from-to)370-389
Number of pages20
JournalEuropean Journal of Operational Research
Issue number2 SPEC. ISS.
StatePublished - Jan 16 2006

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Exact algorithm
  • Heuristics
  • NP-hard
  • Order scheduling
  • Total number of late orders


Dive into the research topics of 'Scheduling orders for multiple product types with due date related objectives'. Together they form a unique fingerprint.

Cite this