Capacitated Lot Sizing Problem with Stochastic Times

In this paper, we study a capacitated multi-item dynamic lot sizing problem with stochastic production and setup times. In this problem, we consider stochastic times to obtain production plans that are both efficient and reliable. The objective of the considered problem is to minimize the total cost including regular production costs and expected overtime costs. The regular costs result from production, setup and inventory holding. The expected overtime costs are incurred due to the excess usage of the machine capacity. First, a procedure that exactly computes the expected overtime for a given production and setup plan is developed. A solution procedure based on tabu search algorithm is proposed to effectively solve the problem. This procedure includes three main phases: initialization, improving, and scheduling. In the first phase of the algorithm, an initialization method is developed to construct feasible production plans. These plans are then improved by the proposed tabu search method. In the scheduling phase, a linear programming model is developed to further improve the solutions obtained by the local search method. The performance of our solution procedure is validated by the lower bounds reported in the literature. Moreover, results show that our tabu search method performs well by obtaining very good solutions in reasonable amount of times