Exact and meta-heuristic approaches for the production leveling problem

Johannes Vass (), Marie-Louise Lackner (), Christoph Mrkvicka (), Nysret Musliu () and Felix Winter ()
Additional contact information
Johannes Vass: TU Wien
Marie-Louise Lackner: TU Wien
Christoph Mrkvicka: MCP GMBH
Nysret Musliu: TU Wien
Felix Winter: TU Wien

Journal of Scheduling, 2022, vol. 25, issue 3, No 7, 339-370

Abstract: Abstract In this paper, we introduce a new problem in the field of production planning, called the production leveling problem. The task is to assign orders to production periods such that the load in each period and for each product type is balanced, capacity limits are not exceeded, and the orders’ priorities are taken into account. Production leveling is an important intermediate step between long-term planning and the final scheduling of orders within a production period, as it is responsible for selecting good subsets of orders to be scheduled within each period. We provide a formal model of the problem and study its computational complexity. As an exact method for solving moderately sized instances, we introduce a mixed integer programming (MIP) formulation. For solving large problem instances, metaheuristic local search is investigated. A greedy heuristic and two neighborhood structures for local search are proposed in order to apply them using simulated annealing. Furthermore, three possible extensions that arise from the application in practice are described and implemented, both within the MIP model and within simulated annealing. We make publicly available a set of realistic problem instances from the industry as well as from random instance generators. The experimental evaluation on our test sets shows that the proposed MIP model is well suited for solving instances with up to 250 orders. Simulated annealing produces solutions with less than $$3\%$$ 3 % average optimality gap on small instances, and scales well up to thousands of orders and dozens of periods and product types. The metaheuristic method presented herein is already being successfully used in the industry.

Keywords: Production leveling; Multi-objective optimization; Mixed integer programming; Metaheuristics; Simulated annealing; Complexity analysis (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00721-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:25:y:2022:i:3:d:10.1007_s10951-022-00721-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00721-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().