Exact and meta-heuristic approaches for the production leveling problem

DOI10.1007/S10951-022-00721-1zbMATH Open1495.90086arXiv2006.08731OpenAlexW3034727577MaRDI QIDQ2163752FDOQ2163752

Christoph Mrkvicka, Nysret Musliu, Johannes Vass, Marie-Louise Lackner, Felix Winter

Publication date: 10 August 2022

Published in: Journal of Scheduling (Search for Journal in Brave)

Abstract: In this paper we introduce a new problem in the field of production planning which we call the Production Leveling Problem. The task is to assign orders to production periods such that the load in each period and on each production resource 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. A formal model of the problem is proposed and NP-hardness is shown by reduction from Bin Backing. As an exact method for solving moderately sized instances we introduce a 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 Variable Neighborhood Descent and Simulated Annealing. Regarding exact techniques, the main question of research is, up to which size instances are solvable within a fixed amount of time. For the metaheuristic approaches the aim is to show that they produce near-optimal solutions for smaller instances, but also scale well to very large instances. A set of realistic problem instances from an industrial partner is contributed to the literature, as well as random instance generators. The experimental evaluation conveys that the proposed MIP model works well for instances with up to 250 orders. Out of the investigated metaheuristic approaches, Simulated Annealing achieves the best results. It is shown to produce solutions with less than 3% average optimality gap on small instances and to scale well up to thousands of orders and dozens of periods and products. The presented metaheuristic methods are already being used in the industry.

Full work available at URL: https://arxiv.org/abs/2006.08731

Recommendations

• Resource leveling in make-to-order production: modeling and heuristic solution method
• Multi-level lot-sizing problem: Evaluation of a simulated-annealing heuristic
• Solving symmetric mixed-model multi-level just-in-time scheduling problems
• A heuristic approach for big bucket multi-level production planning problems
• Simulated annealing and genetic algorithms for scheduling products with multi-level product structure

zbMATH Keywords

simulated annealingmetaheuristicsmulti-objective optimizationmixed integer programmingcomplexity analysisproduction leveling

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Mixed integer programming (90C11)

Cites Work

• Optimization by Simulated Annealing
• Title not available (Why is that?)
• Title not available (Why is that?)
• A classification of assembly line balancing problems
• Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 6th international conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27--31, 2009. Proceedings
• Minimizing variation of production rates in just-in-time systems: A survey
• Title not available (Why is that?)
• The balanced academic curriculum problem revisited
• Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach
• Level Schedules for Mixed-Model Assembly Lines in Just-In-Time Production Systems
• Approximation schemes for scheduling on parallel machines
• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• The product rate variation problem and its relevance in real world mixed-model assembly lines
• Hybrid metaheuristics. 5th international workshop, HM 2008, Málaga, Spain, October 8--9, 2008. Proceedings
• Title not available (Why is that?)
• Trade-off analysis approach for interactive nonlinear multiobjective optimization

Cited In (1)

• Resource leveling in make-to-order production: modeling and heuristic solution method

Uses Software

• Gurobi
• Stony Brook
• SMAC
• GitHub

This page was built for publication: Exact and meta-heuristic approaches for the production leveling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2163752)