هماهنگی برنامه ریزی تولید در محیط تولید سلولی با استفاده از جستجوگر ممنوعه

In this paper, an integrated model for production planning in cellular manufacturing (CM) systems is proposed. The model considers general CM features such as quadratic terms for inter-cell material handling and decisions for manufacturing cell construction. In addition, the solution of the model will provide production planning decisions such as times to start part processing and levels of finished part inventory. The model is then transformed to equivalent simpler models and is solved by Tabu search based procedure. Results from testing numerical examples show encouraging behaviors of the developed model and algorithm.

Cellular manufacturing (CM) is a widely used approach for organizing machines and people into groups to produce a variety of parts in part families. CM is also effective in implementing flexible manufacturing systems and is normally associated with automated batch production (Singh, 1996). Successful CM implementations have resulted in reduced set-up times, reduced material flow and in-process inventory, better system management, improved production efficiency and product quality (Hyer and Wemmerlov, 1989 and Wemmerlov and Johnson, 1997). In the past 30 years, CM problems have been studied by many researchers as summarized by Reisman et al., 1997 and Sarker and Mondal, 1999. Recently, CM research has expanded to developing integrated models and methods as discussed in Song and Choi (2001). For example, Atmani, Lashkari, and Caron (1995) presented a model for simultaneous cell formation and operation allocation. Lockwood, Mahmoodi, and Mosier (2000) studied CM scheduling problems. Production planning in CM systems was discussed in Chen, 2001 and Olorunniwo, 1996. A variety of effective methods were developed to investigate and solve CM problems. These include traditional mathematical programming (Chen, 1998 and Heragu and Chen, 1998) and simulation studies (Shang and Tadikamalla, 1998 and Shinn and Williams, 1998). Non-traditional methods such as neural networks, Tabu search, genetic search and simulated annealing have also been used to search for optimal solutions of various CM problems as can be found in Jamal, 1993, Joines et al., 1996, Lozano et al., 1999, Rao and Gu, 1995 and Sofianopoulou, 1997. Some of the methods were compared in Asokan, Prabhakaran, and Kumar (2001) for their effectiveness and efficiency in solving CM problems. In this paper, we followed the integrated approach to study a production planning problem over a certain planning horizon in CM systems with fixed charge cost. Most existing mathematical programming models for cell formation assume that the number of cells has been given and the cells have been identified. The solutions of the problems were then to allocate proper machines to the cells and to decide the part families to be processed. The purposes are to minimize certain criteria such as material handling cost or dis-similarities among part families. For CM planning, Schaller, Erenguc, and Vakharia (2000) proposed an integer programming model to simultaneously determine the cells to be used and units of parts to be processed in different time periods. In this paper, we consider a similar production planning problem, but the integer programming model developed in this research has more general features where not only the number of cells, but also the formation of the cells are to be determined by the solution of the model. The objective of the model is to minimize the total cost including inter-cell material handling cost, fixed cell set-up cost, production set-up cost and product inventory cost in the system. Detailed description of the problem and the development of the integer programming model are given in Section 2. Due to the NP-hardness of the model we employ an embedded optimization technique to transform the original model to a parametric LP problem. A specially designed Tabu search (Glover & Laguna, 1997) procedure is developed to find optimal or near-optimal solution of the transformed problem. Model transformations are presented in Section 3. Details of the Tabu search process are discussed in Section 4. We tested the developed methods using several numerical examples. Detailed data and computational results of one of the example problems are presented in Section 5. In Section 6, we present the summary, conclusions and our plans for future research in this area.

In this paper, the problem of production planning in CM systems was discussed. Production planning, cell formation and fixed charge costs were considered simultaneously. The problem was formulated as a non-linear mixed integer-programming model. The solution of the model is to minimize total cost of inter-cell material handling, cell construction and required machines, and to minimize production planning related cost. The formulation integrates both cell design and cell operation aspects in a single mathematical programming model. The complicated features of the NP-hard model make it impossible to solve the problem within tolerable computational times on regular computing platforms, if traditional optimization methods are used. In order to obtain optimal or near optimal solutions of the problem, an embedded optimization procedure was developed to transform the original mixed integer-programming model into a binary problem. We then applied Tabu search method to find optimal or near optimal solution of the reduced problem. One of the advantages of the developed approach is that the search process does not need to start with a feasible solution to the original problem. The final solution found by the search process will be feasible even the initial solution was infeasible. Example problems tested in this research showed that the developed search method can arrive at near optimal solutions in most cases. Similar approach can be found in the literature. For example, Teghem, Pirlot, and Antoniadis (1995) developed a simulated annealing algorithm with embedded linear program to solve a production planning problem. While in this research a heuristic algorithm coupling Tabu search and linear programming is developed to solve an integrated production planning and cell formation problem in a CM environment. The developed model and algorithm can be further extended without much technical difficulty. For example, job-scheduling requirement may be included in the model as side constraints (Cao & Uebe, 1995). They can be treated by using penalty functions with certain modifications of the present Tabu search procedure. The current and extended models may be solved by developing deeper search procedures and more powerful computational algorithms. For example, better lower bounds could be generated by Lagrangian relaxation for deeper Tabu search as suggested in Glover and Laguna (1997). In addition, adaptive Tabu list size (Salhi, 2002) could be used instead of fixed Tabu list size. The above-mentioned model and algorithm modifications will be further explored for better search performances in our future research in this area.