یک روش برنامه ریزی پویا به گزینی مبتنی بر GA برای مسائل CF چند دوره

In this paper we have introduced a multi-period cell formation (CF) model which is more computationally challenging than the most comprehensive CF models in the literature. A dynamic programming (DP) based approach coupled with GA-based heuristic is proposed to solve the multi-period problem. Since, the introduced dynamic programming is general and can be applied to any GA-based heuristic with full rejuvenation cycles to solve the multi-period part of the model, we focused only on the DP approach in this paper but have explained the interface with the GA-based heuristic. Illustrative example has been provided that clarifies the application of DP-heuristic. The performance of the DP-heuristic has been evaluated against LINGO and multi period GA-based heuristic.

In situations where the sequence-dependent setup times frequently apply, the design of the cellular manufacturing system shall incorporate setup time in the cell formation procedure, in order to reduce the overall production cost even further by involving the setup cost in the cost minimization process. The integer programming model of such a problem is NP-complete in its strong sense. The presence of the sequence-dependent setup cost term leads to outburst of huge number of integer variables even for medium scale problem instances. Therefore exact optimization algorithms such as branch and bound and branch and cut methods may not provide “good” solutions in a reasonably short amount of time. Also the structure of the corresponding matrices is such that it does not accommodate special treatment to attain optimum solutions in acceptable time. In these situations, one has no way other than to turn to approximate methods for a “good enough solution”. To address the impasse, a multi-period GA-based heuristic was developed. This heuristic was able to solve the single period problems of the mathematical programming model with acceptable accuracy in reasonably short amount of time as compared with commercial optimization software package. However, the multi-period solutions were not as satisfactory, mainly due to its contribution to the enlargement of the solution space which poses further computational burden. In order to remedy this shortcoming, a supplementary approach was needed. A multi-stage solution approach was considered in the first stage of which the GA-based heuristic provides near optimal solution for single periods of the model and in the second stage of which, a dynamic programming based heuristic uses the single-period solutions provided by the GA-based heuristic to generate the multi-period solution. The rest of this paper is organized as follows: Section 2 is the literature review relevant to this research. Section 3 introduces the mathematical model. Section 4 introduces the dynamic programming-based heuristic. Section 5 presents an illustrative numerical example. Section 6 compares the performance of the dynamic programming-based heuristic with those of LINGO and the multi-period GA. Finally Section 7 concludes this paper.

In this paper, a dynamic programming enhanced multi-period GA-based heuristic was introduced for transition from single-period solutions to multi-period solution. The decomposition of the global model of the current research problem provides an opportunity to divide the main problem to single-period problems. Given the fact that for transition from the machine-cell configuration in one period to that in another period, a reconfiguration cost is incurred based on the current configuration of the concerning periods, any combination of feasible solutions in different single periods can be considered to represent a feasible multi-period solution. Finding the best multi-period solution would then turn to be one of finding the optimal policy in a dynamic programming problem. While our previously devised problem specific GA-based heuristic was performing satisfactory in comparison with commercial software packages based on B & B algorithm, the multi-period solution was not at par for comparable multi-period problems. The proposed DP-enhanced heuristic eases the complexity by decomposing the model into smaller single period problems that can be solved by single-period GA-based heuristic and then combine them using dynamic programming approach to find the best combination of solutions that would represent the multi-period solution. The solution found by DP-enhanced heuristic is more robust in terms of sensitivity to the size of the problem and outperforms the multi-period solutions provided by regular GA-based heuristic. In the DP-enhanced heuristic the sub-optimal solutions of the GA-based heuristic are combined by adding the cost of reconfiguring the machine-cell from one period to the next period to the overall single-period cost of the two periods. Since, the GA-based heuristic has performed satisfactorily in providing sub-optimal single-period solutions, DP-enhanced heuristic utilizes a set of best feasible solutions for each period to combine with those of the next period in the manner explained above. The best optimal policy is represented by the combination of certain best feasible solutions of each period that collectively represent the lowest overall cost including reconfiguration costs. The DP-enhanced heuristic has been compared with both LINGO and multi-period GA as depicted in Table 7 and Table 13, respectively, where DP-enhanced approach consistently shows better results in terms of both best objective value and computation time.