الگوریتم های Karmarkar و الگوریتم های تعاملی/ پیش بینی برای برنامه ریزی تولید سلسله مراتبی برای بالاترین سود کسب و کار

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 plans (assigned to an FAW by ERP/MRP II) into short-term plans (to be executed by FMSs in the FAW) for the highest business benefit. Here, ERP is short for enterprise resource planning and MRP II short for manufacturing resource planning. For practical purposes, the HPP problem is modeled after a linear programming (LP) model. Because the scale of the model for a general workshop is too large to be solved by the simplex method on a personal computer, Karmarkar’s algorithm and an interaction/prediction algorithm 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 programs written by using the above-mentioned algorithms and sufficient HPP examples, Karmarkar’s algorithm, the interaction/prediction algorithm and the LP method in Matlab 5.0 are compared, the results showing that the proposed approaches are very effective.

The problem of production planning (PP) for a flexible automated workshop (FAW) consisting of flexible manufacturing systems (FMSs) (or cells) is an important problem worth examining. In a manufacturing setting, PP is essential to achieving efficient resource allocation over time while 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 [1]. To model PP problems, the existing hierarchical approaches usually employ the following concepts: (1) product disaggregation [2]; (2) temporal decomposition [3], [4], [5], [6] and [7]; (3) process decomposition [8] and [9]; and (4) event-frequency decomposition [10]. However, those approaches are not very suitable for the decomposition of medium-term plans (assigned to an FAW by ERP/MRP II) into short-term plans (to be executed by FMSs in the FAW). To be specific, the product disaggregation only considers the structures of products, but not the organizational structure of a manufacturing department. Although the process decomposition in [8] considers the organizational structure of the manufacturing department, it only considers a manufacturing system (in which each part passes through each workshop in turn) consisting of a chain of workshops linked in a forward direction. Because the relationships among FMSs in an FAW are not always serial and even quite complicated, it is not applicable to the decomposition of medium-term plans for FAWs. Reference [9] explores the performance of linear regression and workload-based models for order acceptance in a decentralized production control structure for batch chemical manufacturing. The order acceptance problem is taken as a planning one for centralized allocation of an order to a specific period. The approaches are methods of combining the principles of both a temporal decomposition and a process one. Although multipurpose (i.e. products follow different routings) [9] is considered, it is not suitable for routings among FMSs in the FAW. Both temporal decomposition and event-frequency decomposition fail to take the organizational structure of the manufacturing department into consideration.

In this paper, we have explored the HPP problem of FAWs. First of all, the HPP problem is modeled after a LP model. The objective is to decompose medium-term plans into short-term plans for the highest business benefit. As 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 employed to solve the model. By implementing the above-mentioned algorithms, many examples of HPP have been studied, which leads to the following conclusions.