Exact and meta-heuristic approaches for the production leveling problem
From MaRDI portal
Publication:2163752
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.
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
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1064419 (Why is no real title available?)
- scientific article; zbMATH DE number 2144493 (Why is no real title available?)
- A classification of assembly line balancing problems
- A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
- Analytic combinatorics
- Approximation schemes for scheduling on parallel machines
- Hybrid metaheuristics. 5th international workshop, HM 2008, Málaga, Spain, October 8--9, 2008. Proceedings
- 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
- Level Schedules for Mixed-Model Assembly Lines in Just-In-Time Production Systems
- Minimizing variation of production rates in just-in-time systems: A survey
- Optimization by simulated annealing
- Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach
- The balanced academic curriculum problem revisited
- The product rate variation problem and its relevance in real world mixed-model assembly lines
- Trade-off analysis approach for interactive nonlinear multiobjective optimization
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)
