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

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

Laurent Deroussi (Blaise Pascal University, Clermont-Ferrand II, France) and David Lemoine (Ecole des Mines de Nantes, France)
DOI: 10.4018/978-1-4666-2145-9.ch007
OnDemand PDF Download:
List Price: $37.50


This paper presents a Discrete Particle Swarm Optimization (DPSO) approach for the Multi-Level Lot-Sizing Problem (MLLP), which is an uncapacitated lot sizing problem dedicated to materials requirements planning (MRP) systems. The proposed DPSO approach is based on cost modification and uses PSO in its original form with continuous velocity equations. Each particle of the swarm is represented by a matrix of logistic costs. A sequential approach heuristic, using Wagner-Whitin algorithm, is used to determine the associated production planning. The authors demonstrate that any solution of the MLLP can be reached by particles. The sequential heuristic is a subjective function from the particles space to the set of the production plans, which meet the customer’s demand. The authors test the DPSO Scheme on benchmarks found in literature, more specifically the unique DPSO that has been developed to solve the MLLP.
Chapter Preview


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.


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:

    • o

      N: Number of items.

    • o

      T: Number of periods.

    • o

      Di: Customer’s demand for item i at period t.

    • o

      αij: “Gozinto” factor. Its value is zero if item is not an immediate successor of item j.

  • Otherwise, it is the quantity of itemthat is directly needed to produce one item i:

    • o

      hi: Non-negative holding cost for item i.

    • o

      si: Non-negative setup cost for item i .

    • o

      Ii0: Initial inventory for item i.

    • o

      M: An arbitrary very large number.

Complete Chapter List

Search this Book: