  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.
