An exact algorithm for the mixed-model level scheduling problem

Jordi Pereira, Mariona Vilà

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


The Monden Problem, also known as the Output Rate Variation Problem, is one of the original formulations for mixed-model assembly line-level scheduling problems in a just-in-time system. In this paper, we develop a new branch-and-bound procedure for the problem that uses several new and previously proposed lower and upper bounds. The algorithm also includes several dominance rules that leverage the symmetry in the problem as well as a new labelling procedure that avoids repeated exploration of previously examined partial solutions. The branching strategy exploits the capabilities of current multiprocessor computers by exploring the search tree in a parallel fashion. The algorithm has been tested on several sets of instances from the literature and is able to optimally solve problems that are double the size of those addressed by other procedures previously reported in the literature.

Original languageEnglish
Pages (from-to)5809-5825
Number of pages17
JournalInternational Journal of Production Research
Issue number19
StatePublished - 2 Oct 2015
Externally publishedYes


  • JIT
  • manufacturing
  • mixed-model level scheduling
  • production


Dive into the research topics of 'An exact algorithm for the mixed-model level scheduling problem'. Together they form a unique fingerprint.

Cite this