مدل های عمومی مستمر برای برنامه ریزی تولید و برنامه ریزی در کشتارگاههای دسته ای: مخلوط فرمولاسیون صحیح برنامه خطی و مسائل محاسباتی

In this work, a continuous time model for optimal planning and scheduling of the production in batch processing plants is developed. The considered plants are general in the sense the products can run through different processing stages and follow different manufacturing routes. Processing stages are represented as operations. They can be viewed as modules of operators accomplishing same tasks and sharing possibly different operational characteristics. The resulting continuous time mixed integer nonlinear program (MINLP) is capable to handle complicating situations such as batch splitting, resource allocation and equipment maintenance. By using known linearization techniques, the MINLP is reformulated as a mixed integer linear program. It is further refined by using a modified version of the reformulation linearization technique and some other equivalent reformulations. The model is also implemented on a real life case: paint production. The computation of optimal production plan and schedule takes only a few minutes for this real case.

In commercial productions, the economical aspect is frequently the most important factor in choosing a processing technology, assuming that the technology is also safe and clean. In the middle two quarters of the twentieth century, continuous processing gained considerable popularity, since it is possible to take advantage of economies of scales. However, continuous processes are lacking processing flexibility; large and expensive plants have to be constructed to produce chemicals with tight specifications in large amounts. In addition, consumers have become more sophisticated and demand for chemical products with variable specifications has increased within the last quarter of the century. This fact has forced the focus again on highly flexible batch processing. In many branches of chemical industry, such as traditional paint, food, pharmaceuticals, specialty chemicals, batch production schemes are always preferred to continuous processes because of their ability to respond quickly to frequently changing market conditions and their ease of control. Furthermore, while introducing a brand new product into the market, if the demand for that product is uncertain and not well established, which is true for such branches, a batch process requiring rather low investment is usually preferred. Therefore, the production of a product with a single (most demanded) specification in large scale has become less desirable. Instead, producing products with varying specifications in small amounts has gained popularity because of the chance for a higher market share it offers. Thus, the demand for the products produced in high volumes with a single specification decreased, which in turn forced producers to produce a variety of recipes in smaller volumes. As a consequence, some of the continuous processes, which used to be popular in the second and third quarter of the century, are nowadays being replaced by batch production schemes. On the other hand, developments in flexible production systems make the production of a wide-variety of specifications of a product (multi-product plants), the simultaneous production of many different products (multi-purpose plants), and the simultaneous production of a variety of specifications of many different products (multi-purpose multi-product plants) in a facility possible. These advantages flexible production systems offer, provide another important reason for the use of batch processing. As a result, batch production schemes still play a very important role in chemical industries, and they seem to continue to be a feasible processing mode in the foreseeable future. To benefit fully from what batch processing schemes offer, in order to maximize the profit of the company, the management should efficiently coordinate the equipment (machines) and human resources, namely determine an optimal product mix, prepare efficient production plans and operation schedules. In short, planning and scheduling of a batch processing plant is a crucial problem. Unfortunately, optimal scheduling and planning of batch production plants is a very hard objective to achieve. In chemical industry, this difficulty arises mainly because of the large variety of processing equipment with varying operational and cost characteristics. As a consequence, a general methodology to cope with this difficult but important problem, namely the determination of production plans and operation schedules in order to maximize profit, is one of the objectives of this work. In the related literature, there is a remarkable number of results on the scheduling of batch process chemical plants. They may be divided into two major categories. The first group examines the effect of scheduling on plant design (Vaselenak, Grossmann and Westerberg, 1987, Cerda, Vicente, Guiterrez, Esplugas and Mata, 1989, Coulman, 1989, Birewar and Grossmann, 1990a, Pinto and Rao, 1992, Povua and Macchietto, 1992, Sahinidis and Grossmann, 1992 and Voudouris and Grossmann, 1996), while the second group is interested in the scheduling of operations of existing plants (Ku and Karimi, 1988, Birewar and Grossmann, 1989, Birewar and Grossmann, 1990b, Huisman, Polderman and Weeda, 1990, Ku and Karimi, 1990, Ku and Karimi, 1991a, Sahinidis and Grossmann, 1991, Cao and Bedworth, 1992, Vickson and Alfredsson, 1992, Kondili, Pantelides and Sargent, 1993 and Pekny, Miller and Kudva, 1993). The works belonging to the first category aim the optimal design of a batch processing plant subject to scheduling restrictions. According to the researchers, scheduling can be considered during the design phase and the sizes and types of equipment may be determined more efficiently (i.e. cheaper). In this approach, the objective of scheduling is either to decrease the production cycle-time (overall completion time) of a product (Voudouris & Grossmann, 1996), or group of products (Vaselenak et al., 1987), or form campaigns (Cerda et al., 1989Coulman, 1989) or minimize idle time rather than to schedule daily operations with respect to the changing market conditions (Birewar & Grossmann, 1990a). In these works, a unified approach applicable to all batch production schemes is not present. The suggested models assume a priori the availability of resources and the stability of market demand structure. Thus, the design attained may not be optimum under varying conditions encountered in daily operations. The second category of publications focuses on the scheduling of existing batch production plants under variable market conditions. Most of these works have been developed for rather limited types of production schemes. While some of the works deal with serial production (Ku and Karimi, 1988, Ku and Karimi, 1990, Ku and Karimi, 1991a and Cao and Bedworth, 1992), some deal with parallel production with identical parallel operators (Sawik, 1988, Kusiak, 1990 and Musier and Evans, 1991). On the other hand, most of the published work is limited to multi-product plants (Ku and Karimi, 1988, Birewar and Grossmann, 1989, Birewar and Grossmann, 1990b, Ku and Karimi, 1990, Ku and Karimi, 1991a and Cao and Bedworth, 1992). In addition, majority of the existing works concentrate on sequencing rather than scheduling of batches. In sequencing, time is not of interest and solution procedures do not have to deal with the complexity introduced because of time restrictions. In other words, in sequencing the order of the batches to be produced, is determined rather than determining the complete timetable of the production (Karimi and Hong-Ming, 1988, Wellons and Reklaitis, 1991a and Wellons and Reklaitis, 1991bPekny et al., 1993). On the other hand, almost all of the available literature dealing with time, uses discrete time intervals (Sahinidis and Grossmann, 1991 and Reklaitis and Mockus, 1995) for simplification and do not consider the realistic situation where time is continuous. There are very recent works considering time as pseudo-continuous (Pinto and Grossmann, 1995 and Mockus and Reklaitis, 1996) and continuous (Ierapetritou and Floudas, 1998a, Ierapetritou and Floudas, 1998b and Ierapetritou and Floudas, 1999). However, they are either heuristic methods or models which are incapable to handle both multi-product and multi-purpose batch plants with identical and nonidentical parallel operators (machines) like other works of this category. In most of the suggested scheduling procedures, the objective is to decrease the completion time of a product (cycle time; Kim, Jung, & Lee, 1996) or the idle-times of the operators. Minimization of a cost function, or maximization of a profit function, is rarely the goal (Birewar & Grossmann, 1989Huisman et al., 1990Patsidou and Kantor, 1991a and Weeda, 1992). Some efforts have also been spent on heuristic methods that do not guarantee an optimal but a near optimal solution, such as simulated annealing (Ku and Karimi, 1991b and Graells, Espuna and Puigjaner, 1996), genetic algorithms (Löhl, Shulz, & Engell, 1998), problem specific heuristics (Yiping, Guoven, & Xien, 1995) and knowledge based methods (Henning & Cerda, 1996). There are also reported simulation studies (Patsidou and Kantor, 1991b, Djavdan, 1993 and Graells, Cuxart, Espuna and Puigjane, 1995). In recent years, computational attention is driven towards decreasing the solution time of the models, and reports on the performance of some mathematical programming techniques have been published (Shah, Pantelides and Sargent, 1993 and Yee and Shah, 1998). Unfortunately, a standard test problem library is still lacking and these performance values depend on subjective test problems, which are not publicized. As a consequence, a unified model for planning and scheduling the production of batch processing chemical plants which is solvable within practically acceptable time limits will be a significant contribution to the field of process engineering. The operational (modular) approach that yields an mixed integer nonlinear program (MINLP) model for planning and scheduling batch processing plants and its exact linearization, which gives an equivalent mixed integer linear programming (MILP) model, is represented together with the computational experience in Section 2. Section 3 consists of alternative formulations and the effects of these alternatives on the integrality gap and solution time. Section 4 illustrates a case study in paint industry, and provide an idea on the performance of the MILP model on real world problems. Finally, concluding remarks with possible research directions are provided in the last section.

In this work, a general continuous time mathematical programming model is developed. The resulting linearized MINLP model can determine production plans and operation schedules for single-product, multi-product and multi-purpose batch processing plants with serial and identical or nonidentical parallel operators. It is also capable to handle complicating situations such as batch splitting, resource allocation and maintenance stops. The formulation is based on a continuous time representation and uses operational (modular) approach. Although it seems similar to state-task networks, this approach differs in its major concern. The operational approach focuses on the operations rather than the batches. Base MILP model is very difficult to solve. Computational difficulty in integer programming has an inherent relation with the bounds obtained through relaxations. In this case, the gap between the upper bound obtained by solving the LP relaxation of the base model is way above the optimal objective value. Such a huge gap means little pruning of the branch and bound tree. As a consequence, the base model is modified to obtain more efficient formulation by either using physical properties of the process, such as the disagregation of the constraints, or adopting general methodologies, such as RLT. As a result, a drastic reduction in the integrality gap and solution time has been obtained. The computational results reported in this work can be obtained by using the test library of Orçun (1999). This library consists of 25 hypothetical problems. To have a better idea on the practical efficiency of the model proposed in this work, a real case implementation of the most efficient modification of the base model, i.e. the one which gives the smallest average integrality gap with Orçun's test problems, is solved. The case is a production planning and scheduling problem obtained from one of the largest paint producers in Turkey. An optimal solution is obtained in less than 10 CPU min, which is very encouraging for the practical usability of the proposed continuous time planning and scheduling model.