The multilevel lot-sizing (MLLS) problem is a key production planning problem in materials requirements planning (MRP) system. The MLLS problem deals with determining the production lot-sizes of various items appearing in the product structure over a given finite planning horizon to minimize the production cost, the inventory carrying cost, the back ordering cost and etc. This paper proposed a particle swarm optimization (PSO) algorithm for solving the uncapacitated MLLS problem with assembly structure. All the mathematical operators in our algorithm are redefined and the inertial weight parameter can be either a negative real number or a positive one. The feasibility and effectiveness of our algorithm are investigated by comparing the experimental results with those of a genetic algorithm (GA).
Material requirements planning (MRP) is an old field of study within business, but it still plays an important part in coordinating replenishment decisions for complex finished goods. The MLLS problem in MRP systems belongs to those problems that industry manufacturers daily face in organizing their overall production plans [1]. The objective of the problem is to decide the optimal production lot size and the inventory volume to minimize the production cost, the inventory carrying cost, the back ordering cost and etc [2]. The MLLS problem is a combinatorial optimization problem which can be classified into different categories according to the product structures (e.g., single level system, serial, assembly, and general systems) and the capacity structures (e.g., uncapacitated, capacitated single resource, and capacitated multiple resources) [3]. Table 1, which is based on Ref. [3], gives a brief review of some important literature for the different categories of the capacitated lot-sizing problem. In both MRP and manufacturing resource planning (MRPII), capacity is an important factor that is always checked by a capacity requirements planning (CRP) module, but it does not mean that the uncapacitated problem is an out-of-date problem. One can justify this by the fact that, in practice, uncapacitated lot-sizing models continue to be largely used since the implementation of capacitated approaches requires much data which firms are often reluctant to collect or maintain [4]. So the uncapacitated problem still has significance.
For solving the MLLS problem, people used to adopt heuristics (e.g. Wagner–Whitin, Silver–Meal and etc.) [2]. Recently, the applications of evolutionary computing methods (ECM) were seen in some papers. Tang [14] adopted simulated annealing to solve uncapacitated serial structure problems; Dellaert an Jeunet [1] and [24] used genetic algorithms for solving an uncapacitated general structure problem; Xie and Dong [3] proposed a heuristic genetic algorithm for a capacitated general structure problem; Dellaert and Jeunet [25] designed randomized heuristics for uncapacitated general structure problems; Jeunet and Jonard [26] developed single-point stochastic search algorithms for uncapacitated general structure problems and Pitakaso et al. [4] presented a max–min ant system for uncapacitated general structure problems. ECM may not get the optimal solution to a problem, but it takes little effort to reach a near-optimal solution. A PSO algorithm, which is one of the ECM, was developed by Kennedy and Eberhart in 1995 [31]. The original intent of PSO was to graphically simulate the graceful but unpredictable choreography of a bird flock. PSO exhibits common evolutionary computation attributes including: (1) it is initialized with a population of random solutions, (2) it searches for optima by updating generations, and (3) potential solutions, called particles, are then “flown” through the problem space by following the current optimum particles [32]. So far, few people have adopted a PSO algorithm to solve the MLLS problem. Here we proposed a PSO algorithm for solving an uncapacitated MLLS problem with assembly structure and the feasibility and effectiveness of our algorithm are investigated. Also, we plan to extend this approach to general structure problems with limited and unlimited capacities.
This paper is organized as follows: Section 2 is dedicated to the presentation and mathematical formulation of the MLLS problem. In Section 3, a brief introduction of a PSO algorithm and the framework of the proposed algorithm will be stated. The experimental frameworks and the computational results will be presented in Section 4. Finally, the conclusion and outlook can be found in Section 5.
In this paper, a PSO algorithm is proposed to solve the uncapacitated MLLS problems with assembly structure. Our contribution is twofold: (1) all the mathematical operators in PSO formulas are redefined; (2) we provide a new way for using a PSO algorithm to those researchers who work on MLLS problems. In our future study, a PSO algorithm suitable for solving more complicated MLLS problems should be developed and the application scope should be further extended to other similar research fields.
