Optimization of the stochastic dynamic production cycling problem by a genetic algorithm

摘要

A production system to produce products of multiple items by several machines to meet time-varying stochastic demand is considered. The planning horizon is finite and divided into discrete periods. The demand in each period is mutually independent random variable whose probability distribution is known. Each machine can process at most one item in each period. Setup cost and setup time are incurred only when a machine changes from production of one item to another. Though this kind of problem can be formulated as a Markov decision model, it requires prohibitively long time to obtain a solution. Therefore, an eclectic model is proposed, where items are treated as variables to be determined at the beginning of the planning horizon and production quantities are determined as a policy. The objective function to be minimized is the expectation of the sum of production costs, inventory-holding costs, shortage costs and setup costs. A solution procedure consisting of a genetic algorithm and dynamic programming is proposed to obtain a near-optimal solution for the eclectic model. Three kinds of computational experiments are provided. First, we investigate preliminarily the difference between the optimal value for our eclectic model and the optimal value for the pure Markov decision model in which both items and production quantities are determined as a policy. It has been seen that the difference of the optimal values for the two models is small and the proposed eclectic model is effective. Secondly, we evaluate preliminarily the performance of the genetic algorithm itself for a deterministic model with a single machine that is a special case of the eclectic model. We have found that the genetic algorithm is so effective that we can apply it to the eclectic model. Thirdly, we provide main computational experiments to evaluate the performance of the proposed solution procedure consisting of the genetic algorithm and dynamic programming for the eclectic model. It has been found that good solutions can be obtained efficiently by the proposed solution procedure.