مقایسه مدل های تعیین اندازه دسته تولید و برنامه ریزی فرایندهای پیوسته تک مرحله ای : تحقیق های عملیاتی و روش های مهندسی سیستم های روند

In the last years, several researchers from two different academic communities, the Operations Research and the Process Systems Engineering, have been developing mathematical formulations for the lot-sizing and scheduling of single-stage continuous processes with complex setup structures. This problem has been intensively studied due to its importance to a wide range of industries where a single-stage approach is suitable for production planning. This is the case of the glass container, beer, and dairy production. Recent works have been performed by both mentioned communities, however, no intense communication between these research efforts has been observed. This work attempts a systematic analysis on recent formulation developments of both communities. Based on the result of this comparison, a reformulation is proposed that outperforms in the majority of the cases the previous existent formulations for a set of systematically generated random instances.

In recent years, it has been verified an efficiency increase associated with both standard mixed-integer linear programming (MIP) solvers and hybrid heuristic methods, creating advantages on the use of mathematical formulations to solve industrial problems (Belvaux & Wolsey, 2001). Moreover, mathematical programming approaches can be more flexible than tailored heuristics to accommodate different problem characteristics that change from industry to industry and from time to time. This context creates the motivation to compare, through exact procedures, formulations that can tackle a very practical problem arising in the industrial production scheduling. This is the case of the lot-sizing and scheduling problem that is widely found in the fast moving consumer goods industry characterized by production systems involving tight capacities and complex setup structures. As an example there is the dairy products production, such as yoghurt. In the production of this good, sequence dependent setup times and/or costs are natural, since for instance changing from producing plain yoghurt to chocolate flavor yields a much smaller setup than the inverse operation. Furthermore, if the company produces the same product for different countries, it then incurs in minor setups while changing between labels on the same flavor, favoring a product family arrangement. Finally, these industries usually work on a continuous basis, and therefore, setup carry-over has a high impact on the final solution. The sequence dependent setups feature forces the simultaneous decision on sizing and scheduling of the lots, because using an hierarchical decision procedure may induce operational infeasibilities due to lack of capacity (Almada-Lobo, Klabjan, Carravilla, & Oliveira, 2007). This problem has been receiving an increasing attention from two research communities: the Process Systems Engineering (PSE) and the Operations Research (OR). PSE has been focused more on problems such as the batch scheduling and planning of production systems based on network topologies. Most of the approaches use state-task network (STN) (Kondili, Pantelides, & Sargent, 1993) or resource-task network (RTN) (Pantelides, 1994), with different time representations. On the other hand, the OR has been developing efforts on the definition of the solution convex hull of very structured production problems (e.g. Wolsey, 2002), understanding the advantages of different formulation approaches (e.g. Fleischmann & Meyr, 1997) and developing and benchmarking different heuristic solution methods (e.g. Almada-Lobo & James, 2010). From a scientific publication point of view, the research conducted by both communities has been published in different research journals. Some of the Journals most used by the PSE community are the Computers and Chemical Engineering and the Industrial Engineering and Chemistry Research, whilst the OR research community prefer Journals, such as the European Journal of Operations Research, the Computers and Operations Research or the OR Spectrum. Despite this publishing behavior, the existent boundaries are sometimes crossed (e.g. Stefansson, Sigmarsdottir, Jensson, & Shah, 2011). In the OR community the formulations related to lot-sizing and scheduling problems are clustered in big and small bucket formulations ( Karimi, Fatemi Ghomi, & Wilson, 2003). The big bucket formulations allow for multiple product setups in a single period, while the small bucket formulations allow for at most one setup in each period (cf. Drexl & Haase, 1995). In the PSE community the sequential processes, as the one under study, are essentially modelled with continuous time formulations and event points representation, which may use either time slots or precedence-based approaches (cf. Mendez, Cerda, Grossmann, Harjunjoski, & Fahl, 2006). Despite the apparent differences among the two communities, a linkage can be made between both used classifications. In the big bucket OR formulations, if sequence dependent setups are to be taken into account, changeover variables are usually used to express consecutive precedence within each period, aspect that has been quite explored within the PSE community. Thus a precedence-based approach is inherent to big bucket formulations tackling sequence dependent setups. On the other hand, the time slots event representation, which is often present in the PSE works, is related to the general lot-sizing and scheduling problem ( Fleischmann & Meyr, 1997) that may be seen in the OR community as a small bucket formulation. This formulation relies on a hybrid time representation with two grids: discrete and continuous. The discrete time grid accounts for external events, such as demand occurrences, whilst the continuous one accounts for the lot-sizing and production sequencing. Within each discrete time period the number of slots is defined as a parameter. This happens to be also the case in the time slot formulations, used by the PSE community. The first aim of this work is to compare and analyze the performance of some existent and well identified formulations, published by the OR and the PSE communities that deal to the operational production planning problem involving lot-sizing and scheduling decisions where a complex setup structure is present. Namely, sequence dependent changeovers, setup families and setup carry-over are considered. The models are solved by a state-of-art MIP solver, and are evaluated by the quality of the upper-bound and of the integrality gap at the end of the run. The choice of the formulations to be compared is arguable. However, it was based on two criteria decided by the authors: the recency of the publications and the usage of the same formulation by different authors. The second aim of this work stems from the comparison and consists of testing a reformulation against the formulation that performs the best on the first computational experiments. The remainder of this paper is organized as follows. In Section 2 the literature review is outlined and the problem definition is given in Section 3. In Section 4, four formulations are presented and compared, two published by the OR community and two by the PSE community. The big bucket formulation proposed by the OR is compared with the precedence-based formulation from the PSE in the first subsection. In the second subsection the other two formulations are assessed, namely the small bucket from OR and the time slot from PSE. In order to perform this comparison some adaptations were made in the original formulations of both communities. This work focuses on the well-known general lot-sizing and scheduling problem (small bucket) and capacitated lot-sizing and scheduling problem (big bucket) from the OR community. With regard to the PSE community formulations, as they are less standardized, two recent formulations were chosen that were proposed by Erdirik-Dogan and Grossmann (2008) and Kopanos, Puigjaner, and Maravelias (2011). These formulations are related to time slot and precedence-based formulations, respectively. Computational experiments on a set of systematically generated random instances of the formulations are provided in Section 5 and the reformulation is presented and tested in Section 6. Finally, some conclusions and directions for future research are drawn in Section 7.

This work adapts and benchmarks state-of-art formulations for the simultaneous lot-sizing and scheduling, handling complex setup structures. Four adapted mathematical models were presented to model decisions and constraints of our problem statement. Two models were taken from the OR community and two other from the PSE community. Both communities have been addressing similar or equivalent problems related to production planning and scheduling. The present work explores simultaneously research performed by the OR and PSE communities on this specific subject. Despite the substantial similarities between the formulations of both communities, computational results showed a significant difference in performance. The formulation proposed by Kopanos, Puigjaner, and Maravelias (2011) achieved consistently better results than the other three. Based on this formulation an improved formulation was proposed, using the simple plant location reformulation typical in the OR community. Thus, by using a standard MIP solver it was possible to obtain very good solutions for instances with a considerable size. Future work should focus on creating or adapting matheuristics based on the proposed reformulation to solve this problem more efficiently.