Scheduling multiple products on parallel machines with setup costs

Vladimir Krasik, Joseph Leung, Michael Pinedo, Zhang Jiawei

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


We consider a class of production scheduling models with m identical machines in parallel and k different product types. It takes a time to produce one unit of product type i on any one of the machines. There is a demand stream for product type i consisting of ni units with each unit having a given due date. Before a machine starts with the production of a batch of products of type i a setup cost cis, is incurred. We consider several different objective functions. Each one of the objective functions has three components, namely a total setup cost, a total earliness cost, and a total tardiness cost. In our class of problems we find a relatively large number of problems that can be solved either in polynomial time or in pseudo-polynomial time. The polynomiality or pseudo-polynomiality is achieved under certain special conditions that may be of practical interest; for example, a regularity pattern in the string of due dates combined with earliness and tardiness costs that are similar for different types of products. The class of models we consider includes as special cases discrete counterparts of a number of inventory models that have been considered in the literature before, e.g., Wagner and Whitin (Manage Sci 5 (1958), 89-96) and Zangwill (Oper Res 14 (1966), 486-507; Manage Sci 15 (1969), 506-527).

Original languageEnglish (US)
Pages (from-to)654-669
Number of pages16
JournalNaval Research Logistics
Issue number7
StatePublished - Oct 2008

All Science Journal Classification (ASJC) codes

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


  • Batch scheduling
  • Deterministic scheduling
  • Due dates
  • Earliness costs
  • Inventory control
  • Setup costs
  • Tardiness costs


Dive into the research topics of 'Scheduling multiple products on parallel machines with setup costs'. Together they form a unique fingerprint.

Cite this