Decomposition based heuristic algorithm for lot-sizing and scheduling problem treating time horizon as a continuum

Seong in Kim, Junghee Han, Youngho Lee, Eunkyung Park

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


In this paper, we deal with a new lot-sizing and scheduling problem (LSSP) that minimizes the sum of production cost, setup cost, and inventory cost. Incorporating the constraints of setup carry-over and overlapping as well as demand splitting, we develop a mixed integer programming (MIP) formulation. In the formulation, problem size does not increase as we enhance the precision level of a time period; for example, by dividing a time period into a number of microtime periods. Accordingly, in the proposed model, we treat the time horizon as a continuum not as a collection of discrete time periods. Since the problem is theoretically intractable, we develop a simple but efficient heuristic algorithm by devising a decomposition scheme coupled with a local search procedure. Even if in theory the heuristic may not guarantee finding a feasible solution, computational results demonstrate that the proposed algorithm is a viable choice in practice for finding good quality feasible solutions within acceptable time limit.

Original languageEnglish
Pages (from-to)302-314
Number of pages13
JournalComputers and Operations Research
Issue number2
Publication statusPublished - 2010 Feb

Bibliographical note

Funding Information:
We appreciate very much the valuable comments and suggestions of reviewers. This research was supported by a Korea University Grant and by the Second Brain Korea 21 Project of Ministry of Education, Science and Technology.


  • Heuristic
  • Lot-sizing and scheduling
  • Production system

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Decomposition based heuristic algorithm for lot-sizing and scheduling problem treating time horizon as a continuum'. Together they form a unique fingerprint.

Cite this