اکتشافی جستجو های تصادفی برای یک برنامه ریزی تولید چند هدفه

Real world production planning is involved in optimizing different objectives while considering a spectrum of parameters, decision variables, and constraints of the corresponding cases. This comes from the fact that production managers desire to utilize from an ideal production plan by considering a number of objectives over a set of technological constraints. This paper presents a new multi-objective production planning model which is proved to be NP-Complete. So a random search heuristic is proposed to explore the feasible solution space with the hope of finding the best solution in a reasonable time while extracting a set of Pareto-optimal solutions. Then each Pareto-optimal solution is considered as an alternative production plan in the hand of production manager. Both the modeling and the solution processes are carried out for a real world problem and the results are reported briefly. Also, performance of the proposed problem-specific heuristic is verified by comparing it with a multi-objective genetic algorithm on a set randomly generated test data.

Production planning is such a key issue that both directly and indirectly influences on the performance of the facility. Different approaches are proposed in the literature for production planning, each of them has its own characteristics (Florian and Klein, 1971 and Lee, 2004). For various cases, new models or algorithms are developed till now (Chen et al., 2008, Kirca, 1990, Teyarachakul et al., 2008 and Woeginger, 2005). Few algorithms consider the existence of maximum production capacity (Bertrand and Van-Oijen, 1996, Florian and Klein, 1971 and Sandbothe and Thompson, 1990). On the other hand, production managers usually desire to produce in a semi-fixed rate for different planning periods. A common characteristic in the most production planning models is that they do not pay attention to this requirement, and consequently their optimal solutions are with lots of variations in batch size of different periods. In recent years, various models are proposed to solve this problem in order to satisfy managers in some extent. Most existing models seek a way to determine an ideal production level that variations of lot sizes are as small as possible in a narrow band around this ideal level, as depicted in Fig. 1. This band is usually labeled as the ideal production band (Aryanezhad, Karimi-Nasab, & Bakhshi, 2008). Some models in the literature attempt to force some dummy objectives to the classic batch sizing models. Due to the conflicts between different goals of an existing model, a number of solution methods have been proposed in the literature (Azoza and Bonney, 1990 and Tsou, 2008). Some researchers tried to obtain the narrowest ideal band as possible (Aryanezhad et al., 2008 and Karimi-Nasab and Aryanezhad, 2011). A few studies are aimed at forcing their models to obtain an ideal production band limited to the maximum production capacity. Fig. 1 shows an example of the ideal level and ideal production band. In Fig. 1, it is assumed that the dashed line in the ideal band is the ideal production level. Full-size image (21 K) Fig. 1. Ideal production band (taken from Karimi-Nasab and Aryanezhad (2011)). Figure options In Fig. 1, the forecasted demand (D t) and smoothed batch size View the MathML sourcext∗ of t = 1, 2, … , 12 periods are plotted. It is noteworthy that a fundamental assumption is that values of demands in each planning period is given or forecasted by a good method. The upper dot line indicates the maximum production capacity. Another fundamental assumption is that the maximum production capacity of all periods is constant. One of the topics in literature is the relation between JIT and batch size smoothing approaches. One of the requirements to produce in JIT framework is not to have large variations in market demands (Ehrhardt, 1998 and Lee, 2004). JIT is a production philosophy that proposes to have the followings altogether as possible: (I) having the minimum inventory volumes, (II) having the minimum deviation from customer demand, (III) having the most smoothed production plan over planning periods, (IV) utilizing from a smoothed work load stream over machineries, and so forth. Now for solving this dilemma and nearing to the philosophy of JIT, we could do some of manipulations. For example, customers’ demand could be met in maximum one period delay. In the other words, if the demand of a period is less than the maximum production capacity, that period should produce as JIT, but in other cases, the difference between demand and maximum production capacity could be produced in the adjacent period. And the aim should be not to use the later method as possible. All of these are because of high shortage and holding costs. The high shortage costs would be for the importance/attentions paid to customers. So these scenarios would depend on holding/shortage/delay/… costs, which will be considered. Furthermore, factories not producing in the framework of JIT, should not be worried about using the proposed model. These problematices forces us to use mathematical model instead of decision making based on simple conditions to consider different scenarios of production planning. When considering some of the objectives such minimization of total cost, virtual distance from ideal smoothness, virtual distance from ideal JIT production, etc. the complexity of the model increases because: (a) it is asked to generate some of the Pareto-optimal solutions instead of one unique solution vector and (b) adding a new objective to a complex model, makes it more complex to solve and analyze ( Voorneveld, 2003). For these reasons, heuristics are developed to obtain the answer of the problem approximately in a very short run time ( Woeginger, 2005). Different multi-objective solution methods are developed in the literature for solving problems with different working assumptions such as: – multi-objective particle swarm optimization (MOPSO) (Tsou, 2008 and Hsu et al., 2009, etc.), – multi-objective genetic algorithm (MOGA) (Karimi-Nasab and Aryanezhad, 2011, Soares and Vieira, 2009 and Morad and Zalzala, 1999, etc.), – artificial neural network (ANN) (McMullen, 2001 and Gholamian et al., 2006, etc.), – fuzzy simulation (Maity and Maiti, 2008 and Xu and Zhao, 2008, etc.), – problem-specific heuristic (Karimi-Nasab & Pakgohar, 2010). Also, Tsou, 2008 declared that it is necessary to introduce the best solution among the set of Pareto-optimal solutions to the production manager. He proposed using a simple decision making method such as TOPSIS for recognizing the best solution after obtaining a set of Pareto-optimal solutions by a multi-objective solution method such as MOPSO. Random search methods are so widespread for their simplicity and efficiency in solving complex problems in a reasonable time by an acceptable degree of accuracy. Of course, random search methods could be considered as a special category of simulation–optimization techniques (Pierreval & Paris, 2003). Also different characteristics of random search algorithms for discrete optimization are discussed in the literature (Bartkute and Sakalauskas, 2009, Hong and Nelson, 2007 and Sriver et al., 2009). Hence all of the time new versions of random search algorithms are proposed in the literature (Horng and Lin, 2009, Litinetski and Abramzon, 1998 and Touat et al., 2007). Different simulation models are proposed for optimization in production planning, scheduling and other problems (Jozefowska and Zimniak, 2008, Sastry et al., 2005, Dijk and Sluis, 2008, Hsieh, 2002, Kleijnen, 2008 and Paternina-Arboleda and Das, 2005). For example, Kleijnen and Wan (2007) illustrated the use of simulation optimization in an (s, S) inventory management system with the objective function of minimizing the expected value of specific inventory costs. On the other hand, production planning with multi-objective in mind need a method to find the best solution over all feasible points, or as it is a real challenge to find such an ideal solution, at least give a set of non-dominated production plans as Pareto-optimal solutions. Thus simulation optimization is used in multi-objective problems successfully (Zhang, 2008). Also some special purpose packages are constructed for optimizing production and manufacturing systems via simulation such as SimOpt (Guo, Liao, Cheng, & Liu, 2006). But all of them have their own limitations, especially for adding complicated constraints or new objective functions to an optimization model. Recently Bachelet and Yon (2007) proposed a coupling between optimization and simulation that tries to improve the solution provided by a mathematical model. In this study, a multi-objective production planning problem is formulated in Section 2. As the main problem is proved to be NP-Complete in Section 3, meanwhile it is desired to obtain a set of Pareto-optimal solutions of the problem in a reasonable CPU time; a random search algorithm is developed in Section 4. Also, for evaluating the performance of the heuristic, a multi-objective genetic algorithm is developed in Section 4. Through the reports, some related theorems and lemmas are proved. The algorithm is examined on a set of real world data in Section 5 and some of Pareto-optimal production plans are obtained for it. Furthermore, comparisons of the heuristic with multi-objective genetic algorithm are given at the end of Section 5. Finally, Section 6 is dedicated to some of concluding remarks and future research directions.

The numerical example showed that the model and the solution method together, result in Pareto-optimal solutions which are between complete loyalty to the Philosophy of JIT (w1 + w2 = 0) and leveled production (w2 = 1). Of course the total number of Pareto-optimal solutions obtained by the proposed algorithm is a value between one and maximum number of its iterations. So it is questioned whether or not it is better to search for the best solution while after a few iterations of the algorithm, the average time between two founded Pareto-optimal solutions becomes larger and larger. Surely it is an open question in the studied problem and many other multi-objective problems that if the best solution exists in FSS. As the algorithm is completely adapted to problem structure, it performed better than the multi-objective genetic algorithm, specially for small- and medium-sized instances. The model could be developed for the case of dealing with non-zero setup times or variable production capacity or stochastic demand in each planning period. Also the model and the heuristic could be developed for analyzing the same problem in the environment of flow shop, job shop, and open shop. This research could be continued for considering stochastic perishable items. Also the current research could be extended for considering other technological constraints such as common staffs or limited buffer sizes and so forth.