ابزار بهینه سازی برای برنامه ریزی تولید کوتاه مدت و زمان بندی

A decision support system for short-term production planning and scheduling is presented. The system consists of three modules: an expert system module, an optimization module and a dialog module. The rules defined in the expert module are used to reduce the space searched by the multicriteria genetic algorithm implemented in the optimization module. A set of experiments showed that reducing the search space increases the efficiency of the applied heuristics. Finally, the dialog module supports the decision maker in choosing the best compromise solution from the set of potentially Pareto-optimal solutions generated by the optimization module.

The available ERP systems provide the decision maker with all kinds of production information; however, they usually do not offer any optimization aid. The goal of this paper is to present an optimization tool that can be integrated with an ERP system in order to optimize production plans. The implemented system is designed to operate in rather simple although realistic production environment. The usefulness of the solution was tested in a production plant in Poland. According to Hax and Meal (1975) and Vollman et al. (1997), the tasks of the Manufacturing Planning and Scheduling systems include planning and control of the manufacturing process and related resources such as materials, machines, workforce and other. Both the Manufacturing Planning and Scheduling system and the manufacturing process are designed to meet the market needs and to support the overall company strategy. The Manufacturing Planning and Scheduling system provides information to efficiently manage the flow of materials and effectively utilize the workforce and other resources. The proposed system is consistent with MRPII—the well-known production planning concept. According to this concept, first the product family plan is developed called Sales and Operation Plan (S&OP). On the basis of the S&OP, the detailed schedule is generated called Master Production Schedule (MPS). The task of the proposed system is to disaggregate the family schedule (S&OP) into a detailed schedule (MPS). The developed system is integrated with ERP system—Microsoft Dynamics Axapta and applied in a Polish company producing plastic pipes. Production data are taken directly from Axapta and the production schedule proposed by the optimization module and accepted by the decision maker launches the production orders in Axapta. Reviews of lot sizing and scheduling models can be found in Drexl and Kimms (1997) or Potts and Van Wassenhove (1992). The models differ by taking (or not) into account the following main aspects of the problem: capacity constraints, presence of backlogs, presence of set-up costs and their sequence dependence, number of production stages (single or multistage problems) and number of considered products (Clark and Staggemeier, 2001). In modeling of lot sizing and scheduling problems two terms are often used: macro-periods (big buckets), which can represent a longer time slot e.g. 1 week, and micro-periods (small buckets). In the models with only macro-periods several items may be produced per period. The example of such model is the capacitated lot sizing problem—CLSP (Drexl and Kimms, 1997)—in this case the scheduling decisions are not integrated into the model. Subdividing the macro-periods into several micro-periods leads to the discrete lot sizing and scheduling problem (DLSP) originally formulated by Fleischmann (1990) and further analyzed in Fleischmann (1994). In this model, micro-periods represent short time slots like hours or shifts and only one item can be produced in a micro-period. In addition, there is an assumption in DLSP that the production uses full machine capacity available in a micro-period—this assumption is relaxed in the continuous lot sizing problem—CSLP. In the proportional lot sizing and scheduling problem—PLSP (Drexl and Haase, 1995), production of maximum two products per period is allowed. In these models the micro-periods are ordered and the production of the same product in successive micro-periods forms a lot, so the lot sizing and scheduling decisions are integrated. Fleischmann and Meyr (1997) introduced the concept of mixing macro- and micro-periods called the general lot sizing and scheduling problem (GLSP), later extended (Meyr, 2000) to the GLSP with sequence-dependent setup times (GLSPST) and to the multiple machine case (Meyr, 2002) denoted the GLSP parallel production line (GLSPPL). In this model, the planning period is divided into S macro-periods of a given length, for example 1 day. Each macro-period s is divided into a fixed number of non-overlapping micro-periods with variable length. The ordered set of micro-periods assigned to macro-period s is denoted by Ts. The length of a micro-period is a decision variable, depending on the amount of the product produced in the micro-period. A sequence of the consecutive micro-periods where the same item is produced defines a batch, and the quantity of product produced during these micro-periods defines the size of the batch. Therefore, a batch may continue over several micro- and macro-periods and is independent of the discrete time structure of the macro-periods. Note that micro-periods result from both, the product sequence and the lot sizes and that there is no setup time within a single micro-period. Our model is the extension of the GLSPST to the multiobjective case, with multiple unrelated machines, allowing stockouts. The lot sizing and scheduling problems attract a lot of attention of researches. Many approaches have been used to solve the problem. The CLSP model considers lot-sizing and scheduling problems separately. The problem is NP-hard so only a few exact solution methods were proposed (e.g. Gelders et al., 1986), however there are several heuristics (e.g. Hindi, 1996; Disney et al., 2000; Crauwels et al., 1996; Belvaux and Wolscy, 2000). Scheduling is not integrated into the CLSP model, therefore, the usual approach is to solve CLSP first, and then to schedule each period separately. In Lasserre (1992) and Dauzere-Peres and Lassere (1994) one can find an attempt to hierarchically integrate lot sizing and scheduling. Another solution procedure taking into account sequence-dependent setup costs and times is proposed in Haase and Kimms (2000), where the problem is solved optimally using a tailor-made enumeration method of the branch-and-bound type (notice that the size of the solvable cases ranges from 3 items and 15 periods to 10 items and 3 periods). For the DLSP with sequence-dependent setup costs an exact algorithm is presented in Fleischmann (1994). The problem is transformed into a traveling salesman problem with time windows, which is then used to derive lower bounds as well as heuristic solutions. Solving the DLSP problem optimally is known to be NP-hard as well, so some heuristic procedures are developed (e.g. the dual ascent and column generation heuristics in Cattrysse et al., 1993). The CSLP model, which is very similar to DLSP was considered by Karmarkar and Schrage (1985). The PLSP problem is NP-hard as well. In Drexl and Haase (1995), a regret-based sampling method for the PLSP is proposed to consider the sequence-dependent setup times and costs. In Meyr (2000) the GLSPST problem is solved heuristically using a procedure combining dual reoptimization with local search algorithms (simulated annealing and threshold accepting). The optimization problem considered in this paper is a multiobjective combinatorial optimization problem. The problem is computationally complex, so it is justified to develop heuristic algorithms to find near optimal solutions in reasonable time. There is evidence in the literature (see e.g. Jaszkiewicz, 2001; Jones et al., 2002; Zitzler and Thiele, 1998) that genetic algorithms perform well as heuristics for solving multiobjective optimization problems. Therefore, a multiobjective genetic algorithm was developed to find a set of potentially Pareto-optimal solutions. Genetic algorithms were used to solve lot sizing and scheduling problems as well. Kimms (1999) solves the problem of minimizing the total setup and holding cost in multilevel, multimachine case, Crauwels et al. (1996) solve the problem of minimizing the number of late jobs for the single-machine case. Nevertheless, the attempts to solve the multiobjective problems are very scarce. The examples are Hyun et al. (1998), where the problem of batch sequencing in a mixed model assembly line with three objectives is considered and Duda and Osyczka (2005) where genetic algorithms were proposed to solve the multiobjective lot sizing problem.

We have presented a decision support system for short-term production planning and scheduling. In the first phase a rule-based expert system is used to reduce the space of feasible solutions in two ways. On one hand soft constraints are introduced in form of production rules. On the other hand the expert experience can be used to formulate rules eliminating solutions, which are very likely to be dominated by other solutions. In the second phase, a multiple criteria genetic algorithm is applied to find a set of potentially Pareto-optimal solutions. The genetic algorithm operates on the reduced solution space generated in the first phase. The decision support system is augmented with an interactive interface supporting the choice of the Master Production Schedule for the considered planning period from the set of potentially Pareto-optimal solutions. Practical experiments performed with the system in a production plant in Poland confirm its usefulness.