Optimization-based decision support systems for planning problems in processing industries

Summary Optimization-based decision support systems for planning problems in processing industries Nowadays, efficient planning of material flows within and between supply chains is of vital importance and has become one of the most challenging problems for decision support in practice. The tremendous progress in hard- and software of the past decades was an important gateway for developing computerized systems that are able to support decision making on different levels within enterprises. The history of such systems started in 1971 when the concept of Decision Support Systems (DSS) emerged. Over the years, the field of DSS has evolved into a broad variety of directions. The described research in this thesis limits to the category of model-driven or optimization-based DSS. Simultaneously with the emergence of DSS, software vendors recognized the high potentials of available data and developed Enterprise Systems to standardize planning problems. Meanwhile, information oriented systems like MRP and its successors are extended by the basic concepts of optimization based decision support. These systems are called Advanced Planning Systems (APS). The main focus of APS is to support decision making at different stages or phases in the material flow, i.e. from procurement, production, distribution to sales (horizontal-axis), on different hierarchical aggregation levels (vertical-axis) ranging from strategic (long-term) to operational (short- term) planning. This framework of building blocks decomposes planning tasks hierarchically into partial planning problems. This basic architecture of the planning processes in APS is known as the Supply Chain Planning Matrix (SCPM). Compared to, for instance, discrete parts manufacturing, planning tasks are much more complicated in processing industries due to a natural variation in the composition of raw materials, the impact of processing operations on properties of material flows, sequence dependent change-over times, the inevitable decline in quality of product flows and relatively low margins. These specific characteristics gave rise to focus on optimization-based decision support in the domain of processing industries. The problems to be addressed in this field call for (inter-related) decisions with respect to the required raw materials, the production quantities to be manufactured, the efficient use of available resources, and the times at which raw materials must be available. Although different APS modules can interact directly, coordination and integration is often restricted to the exchange of data flows between different modules. Given the need for specific integrated decision support, the research presented in this thesis focusses particularly on medium to short term decision support at production stage in processing industry, including the vertical and horizontal integration and coordination with adjacent building blocks in the SCPM. Extensive reviews from literature show that the gap between research and practice of DSS is widening. As the field of DSS was initiated as an application oriented discipline, the strategy of what is referred to as “application-driven theory” was taken as the preferred approach for this thesis. “Application-driven” refers to a bottom-up approach which means that the relevance of the research should both be initiated and obtained from practice. The intended successful use of the proposed approaches should, where possible, be represented by tests of adequacy. Simultaneously, the contribution to “theory” aims to be a recognizable part of the research effort, i.e. obtained understanding and insights from problems in practice should provide the basis for new approaches. Based on the preceding considerations we defined the following general research objective: General research objective To support medium- to short term planning problems by optimization-based models and solution techniques such that: i) The applicability and added value of (prototype) systems is recognized and carried by decision makers in practice ii) The proposed approaches contribute to knowledge, understanding and insights from a model building and – solving point of view. In order to link the general objective with the different studies in the thesis, we defined five, recurring research premises, i.e. Professional relevance and applicability (P1), Aggregation (P2), Decomposition and reformulation (P3), Vertical integration at production level (P4), and Horizontal coordination and integration (P5). The overarching premise P1 refers to the first part of the research objective. All other premises refer to the second part of the research objective, i.e. model building and/or – solving. Several planning issues are studied to give substance to the research objective and each study is connected to at least two research premises. Study 1: Planning and scheduling in food processing industry The main question in Chapter 2 was:” How to apply aggregation, decomposition and reformulation in model-based DSS at planning and scheduling level such that the aspect of decision support is recognized and appreciated by decision makers in practice, and which level of aggregation is needed to integrate production planning (i.e. lot-sizing) and scheduling problems in a single model? The study consists of two parts. The first part of the study refers to a case study for the bottleneck packaging facilities of a large dairy company. The goal was to develop, implement and test a pilot DSS which was able to deliver solutions recognized and carried by decision makers at lower decision levels. The latter aim implied that a straight-forward aggregation on time, product type, resources or product stage, was not preferred. The key to develop an approach for regular use was to identify and take advantage of specific problem characteristics. Clustering of numerous jobs, while retaining information at order level, could be exploited in a reformulation approach. The inclusion of (combined) generalized- and variable upper bound constraints gave very tight lower bounds and sparse search trees. An extensive test phase in daily practice showed that the main benefit of the DSS was the initial quality of the generated plans including the time needed to generate these schedules. Hence, decision makers could i) postpone their planning tasks, ii) conveniently cope with rush orders or planned maintenance and iii) easily generate alternatives or revised plans when unforeseen disturbances occur. Moreover, the graphical presentation and overview of the (future) working schedule enabled order acceptance to make use of remaining capacity. The study also showed that planning problems in practice cannot be captured exhaustively by a (simplified) model. Decision makers need the opportunity to modify automatically generated plans manually and use human judgement and experience such that the solution is tuned to the actual situation. Hence, the DSS should not be considered as an optimizer but rather as a tool for generating high quality plans to be used for further analysis. Within this context the various options of a user-friendly, graphical, and fully interactive user interface, were of major importance. Although the case study clearly demonstrates the validity of earlier case based DSS research for current days APS, the proposed approach is hardly a generic solution for a complete vertical integration between lot-sizing and scheduling. If lot-size decisions are strongly affected by the sequence of jobs, production planning and scheduling should be performed simultaneously. As the described case refers to an earlier study and today’s APS do not provide modules for integrated lot-sizing and scheduling, the second part of the study gives an overview of developments in literature regarding lot-sizing and scheduling models and assess their suitability for addressing sequence-dependent setups, non-triangular setups and product decay. The review shows a tendency in which so-called Big Bucket (BB) models are currently proposed for short term time horizons too. However, we argue that segmentation of the planning horizon is a key issue for simultaneous lot-sizing and scheduling. The advantage of BB models may become a major obstacle for i) the effectiveness of simultaneous lot-sizing and scheduling, and ii) addressing specific characteristics in food processing industry. Study 2: Vertical integration of lot-sizing and scheduling in food processing industry Chapter 3 focused on a complete integration of lot-sizing and scheduling decisions in a single model. The main question was:” How to integrate production planning (i.e. lot- sizing) and scheduling problems in a single model, such that common assumptions regarding the triangular setup conditions are relaxed and issues of product decay and limited shelf lives are taken into account?” The literature research in Chapter 2 revealed that the computational advantage of time oriented aggregation in BB models may become a major obstacle in addressing the identified characteristics in FPI. In addition, product decay is primarily associated with the “age” of products and consequently relates to the segmentation of the time- horizon. Therefore, two SB models are developed to demonstrate the impact of non- triangular setups and product decay on the generated solutions. Small scale examples were used to demonstrate how a small change in the balance between inventory - and changeover costs may generate significantly different solutions, especially when the triangular setup conditions do not hold. The developed models are potentially very large formulations and, as expected, hard to solve. Exploratory research was conducted with a Relax-and-Fix (R&F) heuristic. The heuristic is based on a decomposition of the time horizon. Numerical results of small to medium sized problem instances are promising. However, solving real-size problem instances is not possible yet. Study 3: Integrated planning between procurement and production The case study in Chapter 4 focussed on the need for horizontal coordination and integration between the phases procurement and production, which is of particular importance in inter-organizational supply chains. The main question was:” How to model and solve an integrated planning problem between procurement and production, both on a mid-term and short-term planning level, in an inter-organizational supply chain? The research question was projected on an illustrative milk collection problem in practice. The aim was to develop a pilot DSS that lifted decision support for a “weaker” partner in a food supply chain to a higher level, and to illustrate the importance of horizontal integration between the phases procurement and production in an APS framework. Problem analysis revealed that the problem can be classified as an extension of the Periodic Vehicle Routing Problem (PVRP). The problem was decomposed into more tractable sub problems on different hierarchical levels, i.e. the daily (vehicle) routing problem was separated from a medium-term planning problem. On the higher planning level, numerous suppliers were aggregated such that total supply within a cluster met (multiple) vehicle loading capacities. The continuous supply of relatively small amounts from many suppliers had to be balanced with strict delivery conditions at processing level. A model was developed to assign a single (stable) collection rhythm to each cluster such that the total, weighted deviation of desired processing levels on various days in the planning horizon was minimized. The applied aggregation on the higher planning level turned out to be very beneficial for the required disaggregation at the lower planning level. Once supplier farms were geographically grouped into clusters and the aggregated supply within a cluster was assigned to a single collection rhythm with fixed collection days, the (initial) daily routing problem was considerably easier to solve for vehicle schedulers. The computational complexity of the problem was reduced by exploiting application-based properties algorithmically in a specific branch-and-bound scheme, i.e. a customized approach of Special Ordered Sets type 1 (SOS1) This approach made it possible to solve the generated problems exactly for real-size problem instances. The various facilities of a user-friendly and interactive man-machine interface (i.e. an input, planning, simulation and analysing module) turned out to be essential. Decision makers could easily change the data, and the generated plans, in a separate simulation module. However, the impact of any modification was immediately visualised by several (conflicting) indicators in the output screens, both on supply and demand level. Study 4: Mixed Integer (0-1) Fractional Programming in Paper Production Industry The study in Chapter 5 focussed on the impact of technical settings of production units on material flows. The main question was:” How to support decision-makers in practice if crucial properties of end products simultaneously depend on (endogenous) types of raw materials with different chemical or physical properties and (endogenous) technical settings of processing units? The goal of the study was to revise and upgrade an existing, locally used DSS, to a tailored and flexible tool for decision support within the enterprise. The study revealed that the aimed extension towards multi-objective decision support, together with new physical insight for calculating properties of end products due to process operations, had a substantial impact on the optimization module. The proposed solution procedure takes advantage of the problem characteristics and gives rise i) to apply and extend a classical reformulation approach for continuous linear fractional programming (FP) problems to a more general class of mixed integer (binary) FP problems and ii) to exploit the special structure between the original non- linear mixed integer model and the continuous, linear reformulation by applying the concept of Special Ordered Sets type 1 (SOS1). Although Chapter 5 focusses in particular on the reformulation and solution approach, the DSS consists of four main building blocks, i.e. the user interface, a scenario manager, a simulation- and optimization routine. The optimization module provides a powerful tool to find feasible solutions and the best (unexpected) recipes for any available set of raw materials. Moreover, it provides an innovative way of decision support for purchasing (new) pulps on the market, for assigning available pulps to different paper grades, and for attuning available stock levels of raw materials to (changing) production targets for different paper grades. The results of the optimization routine are mainly used to obtain alternative recipes for different paper grades. Usually, these recipes are stored as base scenarios and adapted to daily practice in the simulation module. Main conclusions and future research Based on the studies in the Chapters 2 and 3 we conclude that no generically applicable models and/or solution approaches exist for simultaneous planning and scheduling in processing industries. More industry-specific solutions are needed incorporating specificities of different production environments into those models. The key to develop solvable approaches for contemporary practice may be i) to use knowledge and experience from practice and take advantage of specific characteristics in different problem domains during model construction, and/or ii) to identify and exploit special problem structures for solving the related models. We conclude that surprisingly little research has been devoted to issues of coordination and integration between “procurement” and “production”. The studies in the chapters 4 and 5 confirm that sourcing of (raw) materials flows needs more attention in processing industries, particularly in push-oriented, inter-organizational networks. The valorisation of raw materials can be improved even more if the composition of raw materials is considered too in future planning problems at production level. In the second part of this thesis we focused on extensions for the applicability of Special Ordered Sets type 1 (SOS1), both from an algorithmic (Chapter 4) and modelling (Chapter 5) point of view. We conclude that the concept of SOS1 can extend a classical reformulation approach for continuous fractional programming (FP) problems, to a specific class of mixed integer (0-1) FP problems. Moreover, we conclude that a natural ordering of the variables within the sets is not necessary to make their use worthwhile. A separate (user defined) reference row or weights associated to the variables in the sets might be omitted for an efficient use of SOS1 in commercially available mathematical programming packages. However, this requires further research and extensive computational tests.