Discrete Particle Swarm Optimization for the Multi-Level Lot-Sizing Problem

1. Introduction

Tactical planning plays a major part within industrial planning and consists in the elaboration of production plans which minimize logistic costs (for instance production, holding or setup costs). It means that the aim of tactical planning is to determine, for each item, quantities to be manufactured per period in order to meet the customer’s request at a lower cost. Referring to hierarchical planning system proposed by (Vollmann, Berry & Whybark, 1997), tactical planning is composed of three planning levels:

• -

  the Sales and Operation Planning (S&OP),

• -

  the Master Planning Schedule (MPS),

• -

  the Material Requirement Planning (MRP).

The S&OP consists in finding a balance between sales and production level on a midterm horizon (around 1 year). On this horizon, production capacity is not considered as fixed but can vary thanks to the use of overtime, sub-contracting, hiring, firing and so on.

The MPS is defined by (Genin, 2003) as a problem for which the first goal is to find an optimal production plan which meets the customers’ requests and provides release dates and amounts for all these products. The objective function lies in minimizing production, holding and setup costs.

Elaborating internal component planning is the main goal of MRP. By using bills of materials (BOM), these plans are deduced from the MPS.

Usually, tactical production planning are modelled thanks to mathematical models called “Lot-Sizing problems”. A huge number of models have been proposed in the literature (Rizk & Martel, 2001; Drexl & Kimms, 1997).

The large diversity of these models can be explained by the complexity of modeling the system: some planning objectives require detailed modeling (setup time constraints, sequencing, etc.) while other ones need only rough one. Readers can refer to (Comelli, Gourgand & Lemoine, 2008; Rizk & Martel, 2001) for a review of the main “Lot-Sizing” mathematical models found in literature. Nevertheless, important discriminating criteria can be highlighted. Indeed, according to the planning levels concerned, some important assumptions have been made. For instance, “Lot-Sizing” models can be mono or multi-level, capacitated or uncapacitated formalization. With regard of level criteria, mono-level models deal with S&OP and MPS elaboration (only end items are planned) whereas multi-level ones take into account components production planning. Relating to capacitated criteria, MRP systems do not initially consider manufacturing capacity. With MRP II, the capacity becomes an important factor which is checked by a capacity requirements planning module. Nevertheless, (Han, Tang, Kaku & Mu, 2009) point out that uncapacitated “Lot-Sizing” problems are still largely used (in ERP for example) “since the implementation of capacitated approaches requires much data which firms are often reluctant to collect or maintain”.

In this paper, we deal with the Multi-Level Lot-Sizing Problem (MLLP) which is an uncapacitated multi-level Lot-Sizing problem, dedicated to MRP system. We propose an effective heuristic method to solve it, based on a Particle Swarm Optimization (PSO). Our contribution is thus organized as follows: in the second section, we give a brief review of solution approaches for the MLLP. In the third section, we present the Particle Swarm Optimization method. In Section 4, the proposed approach is given and the last section is dedicated the last section is dedicated to our experimental results.

2. Mllp: State Of The Art

As described before, the MLLP is an uncapacitated multi-level “lot sizing problem” mathematical model. It can be formulated as a mixed-integer programming model, using the following notations:

Parameters:

N: Number of items

T: Number of periods

D_i: Customer’s demand for item i at period t

α_ij:“Gozinto” factor. Its value is zero if item is not an immediate successor of item. Otherwise, it is the quantity of itemthat is directly needed to produce one item