Published on Mon Jun 15 2020

Exact and Metaheuristic Approaches for the Production Leveling Problem

Johannes Vass, Marie-Louise Lackner, Nysret Musliu

Production Leveling is an important intermediate step between long-term planning and the final scheduling of orders within a production period. A formal model of the problem is proposed and NP-hardness is shown by reducing Bin Backing. For solving large problem instances, metaheuristic local search is investigated.

0
0
0
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.

Fri Sep 05 2008
Artificial Intelligence
MOOPPS: An Optimization System for Multi Objective Scheduling
MOOPPS is an optimization system solving multi-objective production scheduling problems. The identification of Pareto optimal alternatives or at least a close approximation of them is possible by a set of implemented metaheuristics. Necessary control parameters can easily be adjusted by the decision maker.
0
0
0
Mon Jun 22 2020
Artificial Intelligence
Metaheuristics for the Online Printing Shop Scheduling Problem
The online printing shop scheduling problem is considered. A local search strategy and metaheuristic approaches are proposed and evaluated. Extensive experiments with large-sized instances show the proposed methods are suitable for solving practical instances of the problem.
0
0
0
Fri Jul 19 2019
Artificial Intelligence
Conditional Markov Chain Search for the Generalised Travelling Salesman Problem for Warehouse Order Picking
The Generalised Travelling Salesman Problem (GTSP) is a well-known problem. It arises in warehouse order picking, where each stock is distributed between several locations. The methods are designed with those instances in mind.
0
0
0
Mon May 28 2012
Artificial Intelligence
A Mixed Integer Programming Model Formulation for Solving the Lot-Sizing Problem
This paper addresses a mixed integer programming (MIP) formulation for the multi-item uncapacitated lot-sizing problem. The proposed MIP model has been utilized to find out the optimum order quantity, optimum order time, and the minimum total cost of purchasing.
0
0
0
Thu Jul 04 2019
Artificial Intelligence
A global constraint for the capacitated single-item lot-sizing problem
The goal of this paper is to set a constraint programming framework to solve single-item lot-sizing problems. We establish a new lower bound for this problem by using a subtle time decomposition. We show that bound consistency can be achieved in pseudo-polynomial time.
0
0
0
Fri Oct 23 2020
Neural Networks
A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem
The Flexible Job Shop Scheduling Problem (FJSP) is a combinatorial problem that continues to be studied extensively. The GLNSA algorithm is complemented with a tabu search that implements a simplified version of the Nopt1 neighborhood.
0
0
0