برنامه ریزی تولید سلسله مراتبی با محدودیتهای تقاضا

This paper explores the hierarchical production planning (HPP) problem of flexible automated workshops (FAWs), each of which has a number of flexible manufacturing systems (FMSs). The objective is to decompose medium-term production plans (assigned to an FAW by ERP/MRP II) into short-term production plans (to be executed by FMSs in the FAW) so as to minimize cost on the condition that demands have just been met. Herein, the HPP problem is formulated by a linear programming model with the overload penalty different from the underload penalty and with demand constraints. Since the scale of the model for a general workshop is too large to be solved in the simplex method on a personal computer within acceptable time, Karmarkar's algorithm and an interaction/prediction algorithm, respectively, are used to solve the model, the former for the large scale problems and the latter for the very large scale. With the help of the above-mentioned algorithms and HPP examples, Karmarkar's algorithm and the interaction/prediction algorithm are compared and analyzed, the results of which show that the proposed approaches are quite effective and suitable for both ‘push’ and ‘pull’ production.

The problem of production planning for a flexible automated workshop (FAW) consisting of flexible manufacturing systems (FMSs or cells) is important and worth studying. In a manufacturing setting, production planning is essential to achieve efficient resource allocation over time in meeting demands for finished products. Since the scope of PP problems generally prohibits a monolithic modeling approach, a hierarchical production planning (HPP) approach has been widely advocated in the PP literature (Davis & Thompson, 1993). To model PP problems, the existing hierarchical approaches usually employ the following concepts: (1) product disaggregation (Bitran and Hax, 1977, Bitran et al., 1981, Davis and Thompson, 1993, Graves, 1982, Hax and Meal, 1975, Newson, 1975, Saad, 1988, Simpson, 1999, Simpson and Erenguc, 1998 and Yeh et al., 1988), (2) temporal decomposition (Karmarkar, 1988, Malakooti, 1989, Nguyen and Dupont, 1993, Qiu and Burch, 1997 and Tsubone, 1988), (3) process decomposition (Villa, 1989), and (4) event-frequency decomposition (Gershwin, 1988, Kimemia and Gershwin, 1983 and Akella, 1989). However, those approaches are not quite suitable for the decomposition of medium-term production plans (assigned to an FAW by ERP/MRP II short for enterprise resource planning/manufacturing resource planning) into short-term production plans (to be executed by FMSs in the FAW). To be specific, the product disaggregation only considers the structures of products instead of the organizational structure of a manufacturing department. Although the process decomposition considers the organizational structure of the manufacturing department, it only covers the manufacturing system consisting of a forward chain of workshops. As the relationships among FMSs in an FAW are not always serial or even very complicated, the process decomposition is inapplicable to the decomposition of medium-term production plans for FAWs. And the temporal and event-frequency decomposition do not consider the organizational structure of the manufacturing department as such, either. For this end, Yan, 1997 and Yan and Jiang, 1998 proposed two new approaches to the optimal decomposition of production plans for FAWs with respect to delay interaction or not. By building up linear quadratic models of PP problems and using interaction/prediction, their proposed approaches optimally decompose medium-term production plans (assigned to an FAW by MRP II/CIMS short for computer integrated manufacturing system) into short-term production plans (to be executed by FMSs in the FAW) at a high speed. These approaches, combining the principles of both a temporal decomposition and a process decomposition with the organizational structure of the FAW, are capable of solving very-large-scale HPP problems. However, their overload and underload penalty are the same. In practice, the wages for overtime are several times those for the usual hours and the underload only leads to the decrease in the utilization of resources (such as men and equipment), so the overload penalty should be much greater than the underload. Besides, only the manufacturers, that can agilely respond to and completely satisfy users' demands, can win a victory in the keen competition for markets, while the overproduction will lead to the increase in finished-product inventory and production cost. No doubt, it is desirable to just meet product demands without overproduction or underproduction. Thus, a linear programming (LP) model with the overload penalty different from the underload penalty and with demand constraints should be built up, for decomposing medium-term production plans (assigned to an FAW by ERP/MRP II) into short-term production plans (to be executed by FMSs in the FAW). Because the model for a general workshop is of thousands upon thousands of constraints and variables, it is difficult to be solved by the simplex method on a personal computer within acceptable time. For this end, we propose that Karmarkar's algorithm and an interaction/prediction approach based on Karmarkar's algorithm, respectively, should be applied to solving the model, the former for the large scale problems and the latter for the very large scale. The above-mentioned LP problem is also an HPP problem because the Karmarkar's algorithm and interaction/prediction approach based on Karmarkar's algorithm for solving it are in fact the methods to combine the principles of both a temporal decomposition and a process one in HPP with the organizational structure of the FAW.

In this paper, we have addressed the HPP problem of flexible automated workshops. First of all, the HPP problem is formulated by a linear programming model with the overload penalty different from the underload penalty and with demand constraints. The objective is to decompose medium-term production plans into short-term production plans and minimize cost under the condition of demands' being just satisfied. Because the scale of the model for a general workshop is too large to be solved by the simplex method on a personal computer within acceptable time, Karmarkar's algorithm and Algorithm 1 are adopted for solving the model. With the help of the above-mentioned algorithms, some typical examples of HPP have been studied, with the results showing that (1)Karmarkar's algorithm can guarantee the optimal solutions to HPP problems, but Algorithm 1 cannot; (2)Algorithm 1 is on an average 56.49% faster than Karmarkar's algorithm, but the optimal objective values for Algorithm 1 are on an average 0.03% greater than those for Karmarkar's algorithm; (3)Karmarkar's algorithm is suitable for solving large-scale problems, and Algorithm 1 for very-large-scale ones; (4)The proposed approaches are quite effective in that the optimal solutions of the very large scale HPP problems with eight FMSs, 30 types of parts totalling 1960 and 50 planning periods in a planning horizon H can be obtained by Algorithm 1 within 2632.969 s on a Pentium 2.4 GHz personal computer with 256 M memory; (5)The proposed approaches are very suitable for decomposing medium-term production plans into short-term production plans so as to obtain the lowest cost under the condition of demands' being just satisfied. The HPP problem [P3] and Step 2 in Algorithm 1 can also be solved by other interior point methods for linear programming (Megiddo et al., 1998, Renegar, 1988 and Sturm and Zhang, 1998) instead of by Karmarkar's algorithm. However, since those methods have not been demonstrated through a convincing number of computational experiments, we employ Karmarkar's algorithm to solve the HPP problems herein. Problems [P2] and [P4] are for the case that View the MathML source is given, that is, for ‘push’ production. If View the MathML source in Eq. (10b) is moved to the left of Eq. (10b) and View the MathML source in Eq. (12b) moved to the left of Eq. (12b) and if View the MathML source is added to Eqs. (10f) and (12f), then the optimal View the MathML source can also be obtained by solving problems [P2] and [P4], that is, for ‘pull’ production. And the optimal objective values for ‘pull’ production are less than those for ‘push’ production under the same conditions. Only the number of workpieces of planned production by each FMS in each period is determined through Karmarkar's algorithm and Algorithm 1. To develop the real production plan to be executed by each FMS in each period, we must add such parameters as part no, part priority, available machine (or working center), NC program, processing time and tool to the number (Yan et al., 1997 and Yan et al., 1998; Yan, Wang, Zhang & Cui, 1998).