A local search algorithm for the optimization of the stochastic economic lot scheduling problem

This paper describes a model for the stochastic economic lot scheduling problem (SELSP), and a Local Search heuristic to find close to optimal solutions to this model. The SELSP considers multiple products, which have to be scheduled on a single facility with limited capacity and significant setup times and costs. The demand is modeled as a stationary compound renewal process. The objective is to find a schedule that minimizes the long-run average costs for setups and inventories while satisfying a given fill rate. We use a cyclic scheduling approach in which the individual cycle time of each product is a multiple of some basic period (fundamental cycle). For the deterministic version of the SELSP, efficient heuristics have been developed which guarantee the feasibility of the solution by adding an additional constraint to the problem. In our case this is not sufficient, because for the calculation of the average inventory levels and fill rates we need to develop a schedule with detailed timing of the lots. We present an efficient heuristic for this scheduling problem, which can also be used to check the feasibility of the solution. Thereby, the most time-consuming step (the calculation of average inventory levels and fill rates) is only performed for a limited set of candidates. The algorithm was tested on deterministic benchmark problems from literature and on a large set of stochastic instances. We report on the performance of the heuristic in both cases and try to identify the main factors influencing the objective.