Production Planning Heuristic

Solving the Capacitated Lot-Sizing Problem (CLSP) with Tabu Search.

Gantt

...

Metaheuristic Description

Tabu Search is implemented as follows:

The solution is represented as a list of production lots for each product and period. A production lot specifies the production quantity assigned to cover the demand of a certain period.
In each iteration, a neighborhood is generated. The neighborhood consists of all solutions that can be reached from the current one by applying a move.
A move shifts one, several, or all production lots of a specific product from one period to another.
In every iteration, the best move is executed. To prevent cycling, the reverse of this move is declared tabu for a certain number of iterations (tabu tenure).
Feasibility: demand is always met; overcapacity is allowed but associated with penality costs.
Note: In this implementation, splitting the demand of a single period across multiple production periods is not allowed. However, this is important in tight capacity scenarios.

For comparison:

Hill Climbing is identical to Tabu Search but does not use a tabu list. The search stops as soon as no improving move is available.
The Start Solution produces each demand exactly in its demand period, without carrying inventory across periods.

Problem Statement

The Capacitated Lot-Sizing Problem (CLSP) is a classical optimization problem in production planning. It deals with deciding how much of each product to produce in each time period over a planning horizon, subject to:

Demand requirements: Each period has a known demand that must be met (no backlogging allowed).
Production capacity: Each period has limited machine or resource capacity, restricting the total production volume. This capacity is consumed not only by production times (units produced per unit of time) but also by setup times (time required to switch production between products).
Setup costs and inventory costs: Producing in a period incurs fixed setup costs. Surplus production can be stored to meet future demand but incurs holding costs.
The goal is to minimize total costs (setup + inventory) while ensuring feasibility.

Mathematical Definition

Sets and Indices

$I : set of products, i \in I$ $T : set of periods, t \in T = {1, \dots, H}$

Parameters

$d_{i t} : demand of product i in period t$ $h_{i} : inventory holding cost per unit of product i per period$ $s_{i} : setup cost for producing product i$ $a_{i} : production time per unit of product i$ $b_{i} : setup time for product i$ $C_{t} : available production capacity in period t$

Decision Variables

$x_{i t} \geq 0 : production quantity of product i in period t$ $y_{i t} \in {0, 1} : 1 if product i is produced in period t$ $I_{i t} \geq 0 : inventory of product i at end of period t$

Model

Objective Function

$Minimize: \sum_{i \in I}^{} \sum_{t \in T}^{} s_{i} y_{i t} + h_{i} I_{i t}$

Inventory balance (demand satisfaction):

$I_{i t-1} + x_{i t} = d_{i t} + I_{i t}, ∀ i ∈ I, t ∈ T$

Capacity constraints (setup + production times consume capacity):

$\sum_{i \in I}^{} a_{i} x_{i t} + b_{i} y_{i t} \leq C_{t}, ∀ t ∈ T$

Production only if setup:

$x_{i t} \leq M_{i} y_{i t}, ∀ i ∈ I, t ∈ T$

Variable Domains:

$x_{i t} \geq 0, I_{i t} \geq 0, y_{i t} \in {0, 1}, ∀ i ∈ I, t ∈ T$