An iterated beam search algorithm for the multi-level production smoothing problem with workload smoothing goal

Abstract

This paper is concerned with a generalised version of the production smoothing problem. The problem involves both usage and loading goals at multiple levels. Three existing heuristic approaches, namely the one-stage (1SH), two-stage (2SH) and earliest-due-date (EDD) heuristics are adapted, as well as a novel iterated beam search (IBS) algorithm is proposed to solve the problem. An extensive computational study is designed in the paper and used to compare the four heuristic approaches. The results show that IBS finds the best solution in the majority of test instances and requires less computation time than 2SH.

Keywords:

• just-in-time
• production smoothing
• NP-hard
• heuristics
• beam search