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. We deal with a production system to produce products of multiple items by several machines to meet time-varying stochastic demand. The planning horizon is finite and divided into discrete periods. Setup cost and setup time are incurred when a machine changes from production of one item to another. We should determine items and quantities of products produced on each machine in each period so as to minimize the expected sum of costs. This kind of problem is called a stochastic dynamic production cycling problem. Though it can be formulated as a Markov decision model, it requires a prohibitively long time to obtain a solution and is not practical. Therefore we propose an eclectic model that is easier to handle, where items are determined at the beginning of the planning horizon and production quantities are determined with the observed, actual inventory level. A branch and bound method is applicable for the eclectic model, but it is difficult to deal with larger problems. Instead we propose a solution procedure consisting of a genetic algorithm and dynamic programming to calculate a near-optimal solution for larger problems. The computational experiments show that the proposed eclectic model is effective and that good solutions for the eclectic model can be obtained efficiently by the proposed solution procedure.
production cycling genetic algorithm stochastic demand dynamic programming production planning lot size markov decision process