On solving stochastic production planning problems via scenario modelling

Summary Linear Porgramming models for stochastic planning problems and a methodology for solving them are proposed. A production planning problem with uncertainty in demand is used as a test case, but the methodology presented here is applicable to other types of problems as well. In these models, uncertainty in demand is characterized via scenarios. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield an implementable non-anticipative policy. Such an approach makes it possible to model correlated and nonstationary demand as well as a variety of recourse decision types. For computational purposes, two alternative representations are proposed. A compact approach that is suitable for the Simplex method and a splitting variable approach that is suitable for the Interior Point Methods. A crash procedure that generates an advanced starting solution for the Simplex method is developed. Computational results are reported with both the representations. Although some of the models presented here are very large (over 25000 constraints and 75000 variables), our computational experience with these problems is quite encouraging.     

Towards the integration of system modelling with scenario planning to support strategy: the case of the UK energy industry

A key aspect of strategy is sense-making of the unfolding uncertainty in the business environment and responding appropriately to achieve organisational objectives. However, uncertainty means that there is more than one future open to an organisation. Sense-making is therefore problematic. Scenario planning is one approach to sense-making that helps to explore and understand uncertainty, aiming for the identification of potential predetermined elements in the business environment. In this paper we propose the integration of systems modelling with scenario planning to support the exploration of uncertainty, identify knowledge gaps that set a (subsequent) research agenda, understand the role and usefulness of historical data, and model research outcomes to help reveal potential predetermined elements. Specifically, scenario planning identifies potential predetermined elements in the business environment; system modelling in the form of behaviour-over-time graphs, causal mapping and feedback loops helps in structuring and linking variables and their interaction to provide an understanding of the systemic drivers of these predetermined elements. Methodological integration of this type enhances modellers’ ability to support strategy in organisations.     

Visual interactive modelling and manpower planning

Following some years extensive use of a Staff Simulation Model by the Personnel Department of Barclays Bank to demonstrate the effect of different staffing policies, it was felt that there was a need to improve the model, both technically and from the point of view of the presentation of the results. It was decided to use Visual Interactive Modelling Systems as in this way, the changes in the assumption could be seen in a colour, pictorial form on a screen. The results could also be shown diagrammatically either on the screen or as a screen print-out. The pictorial output had an immediate impact, and was felt to be a vast improvement on the large number of sheets of numerical computer print-outs previously produced.     

A scenario decomposition approach for stochastic production planning in sawmills

This study considers a real world stochastic multi-period, multi-product production planning problem. Motivated by the challenges encountered in sawmill production planning, the proposed model takes into account two important aspects: (i) randomness in yield and in demand; and (ii) set-up constraints. Rather than considering a single source of randomness, or ignoring set-up constraints as is typically the case in the literature, we retain all these characteristics while addressing real life-size instances of the problem. Uncertainties are modelled by a scenario tree in a multi-stage environment. In the case study, the resulting large-scale multi-stage stochastic mixed-integer model cannot be solved by using the mixed-integer solver of a commercial optimization package, such as CPLEX. Moreover, as the production planning model under discussion is a mixed-integer programming model lacking any special structure, the development of decomposition and cutting plane algorithms to obtain good solutions in a reasonable time-frame is not straightforward. We develop a scenario decomposition approach based on the progressive hedging algorithm, which iteratively solves the scenarios separately. CPLEX is then used for solving the sub-problems generated for each scenario. The proposed approach attempts to gradually steer the solutions of the sub-problems towards an implementable solution by adding some penalty terms in the objective function used when solving each scenario. Computational experiments for a real-world large-scale sawmill production planning model show the effectiveness of the proposed solution approach in finding good approximate solutions.     

Teaching scenario planning: Lessons from practice in academe and business

In this paper, we engage with O’Brien’s [O’Brien, F.A., 2004. Scenario planning – lessons for practice from teaching and learning. European Journal of Operational Research 152, 709–722] identification of both pitfalls in teaching scenario planning and proposed remedies for these. We consider these remedies in relation to our own experience – based on our practice in both the academic and business arenas – and we highlight further pitfalls and proposed remedies. Finally, we propose the use of “hard” multi-attribute decision analysis as a complement to “soft” scenario planning, in order to allow a more formal method of strategy evaluation against a range of constructed scenarios, This approach is intended to remedy biases that are associated with holistic evaluations – such as lexicographic ranking – where undue attention is paid to particular strategic objectives at the expense of others. From this discussion, we seek to contribute to cumulative refinement of the scenario process.     

Production planning in fuzzy environment

This paper describes a fuzzy system designed to support production planning in an industrial unit producing cardboard boxes. In this industrial unit, orders forn boxes of widthw, lengthl, heighth, made ofq layers of typek paper for delivery int units of time are produced. In the production of such orders apart from meeting the orders specifications, it is usually tried to minimize the margin trim loss, the number of machine setups and the holding cost of the finished orders. Considering the dynamism of production systems that are influenced by such factors as market demand fluctuations, changes in commercial priorities, raw material availability and production capabilities, we solve this multi-objective problem by fuzzy set theory.     

SDDP for multistage stochastic programs: preprocessing via scenario reduction

Even with recent enhancements, computation times for large-scale multistage problems with risk-averse objective functions can be very long. Therefore, preprocessing via scenario reduction could be considered as a way to significantly improve the overall performance. Stage-wise backward reduction of single scenarios applied to a fixed branching structure of the tree is a promising tool for efficient algorithms like stochastic dual dynamic programming. We provide computational results which show an acceptable precision of the results for the reduced problem and a substantial decrease of the total computation time.     

Production planning of seasonal demanded products

This paper presents an attempt to find the optimum production rate by factories using seasonally produced raw material. To this effect the Aggregate Production Planning Model suggested by Holt et al. [12], has been applied to a real world case of a factory industrializing agricultural products.Finally, among the feasible solutions applied to this case, the optimum production policy determines the quantities which are forecasted to be sold after the termination of the period of operation of the plant.     

Production planning with time-dependent capacity bounds

In this paper, we examine the problem of finding minimum-cost production schedules that satisfy known demands over a finite planning horizon. A dynamic programming algorithm is developed to find these schedules for cases in which production in each period is constrained by a time-dependent capacity bound. The costs considered are production and inventory holding costs, and all cost functions are assumed to be nondecreasing and concave. The algorithm is an extension of Florian and Klein's method developed for problems in which capacity bounds are the same in all periods. Although the problem with time-dependent bounds is NP-complete, the algorithm is shown to be efficient when the capacity bounds are integer multiples of a common divisor and the largest multiplier is small. Hence, it is useful in applications in which production capacity is periodically increased by adding facilities of the same size.     

A comparison of different modelling approaches to strategic energy planning

In this paper we discuss the role of models in strategic planning, paying special attention to the way perceptions, values and preferences are treated. Starting from an analysis of the specific nature of long term planning we propose two criteria to evaluate the interaction between policy preferences and mathematical models. On basis of these criteria we examine four recent energy studies. The paper concludes with a comparison of these cases and recommendations concerning the interface between models and policy preferences.     

Radiofrequency ablation planning: An application of semi-infinite modelling techniques

In radiofrequency (RF) ablation a needle-shaped probe is inserted into the patient’s body in order to heat and subsequently destroy the malignant tissue around the needle tip. The determination of the optimal probe position poses an intricate problem, as it requires the modelling of the tumour destruction depending on the attained temperature as well as the incorporation of constraints that prohibit puncturing bones or other risk structures.In this work we present a new optimization procedure that reflects both aspects adequately. We assess tumour destruction by solving the underlying system of partial differential equations using a finite element method. Next we show how the probe’s position and orientation can be optimized by gradient-based methods. Ensuring that risk structures are not harmed by the probe is easily modelled using semi-infinite constraints in the optimization problem.Techniques to reduce the semi-infinite problem to a standard nonlinear constrained optimization problem are introduced and demonstrated as a proof-of-concept on real clinical data. The results indicate the high potential of this combination of PDE-based simulation and numerical optimization for RF ablation planning.     

MIP modelling of changeovers in production planning and scheduling problems

The goal here is to survey some recent and not so recent work that can be used to improve problem formulations either by a priori reformulation, or by the addition of valid inequalities. The main topic examined is the handling of changeovers, both sequence-independent and -dependent, in production planning and machine sequencing, with in the background the question of how to model time. We first present results for lot-sizing problems, in particular the interval submodular inequalities of Constantino that provide insight into the structure of single item problems with capacities and start-ups, and a unit flow formulation of Karmarkar and Schrage that is effective in modelling changeovers. Then we present various extensions and an application to machine sequencing with the unit flow formulation. We terminate with brief sections on the use of dynamic programming and of time-indexed formulations, which provide two alternative approaches for the treatment of time.     

Extending the use of scenario planning and MCDA for the evaluation of strategic options

Multi-criteria decision analysis (MCDA) is well equipped to deal with conflicting, qualitative objectives when evaluating strategic options. Scenario planning provides a framework for confronting uncertainty, which MCDA lacks. Integration of these methods offers various advantages, yet its effective application in evaluating strategic options would benefit from scenarios that reflect a larger number of wide-ranging scenarios developed in a time-efficient manner, as well as incorporation of MCDA measures that inform within and across scenario comparison of options. The main contribution of this paper is to illustrate how a more diverse set of scenarios could be developed quickly, and to investigate how regret could be used to facilitate comparison of options. First, the reasons for these two areas of development are elaborated with respect to existing techniques. The impacts of applying the proposed method in practice are then assessed through a case study involving food security in Trinidad and Tobago. The paper concludes with a discussion of findings and areas for further research.     

Forecasting S-shaped diffusion processes via response modelling methodology

Diffusion processes abound in various areas of corporate activities, such as the time-dependent behaviour of cumulative demand of a new product, or the adoption rate of a technological innovation. In most cases, the proportion of the population that has adopted the new product by time t behaves like an S-shaped curve, which resembles the sigmoid curve typical to many known statistical distribution functions. This analogy has motivated the common use of the latter for forecasting purposes. Recently, a new methodology for empirical modelling has been developed, termed response modelling methodology (RMM). The error distribution of the RMM model has been shown to model well variously shaped distribution functions, and may therefore be adequate to forecast sigmoid-curve processes. In particular, RMM may be applied to forecast S-shaped diffusion processes. In this paper, forty-seven data sets, assembled from published sources by Meade and Islam, are used to compare the accuracy and the stability of RMM-generated forecasts, relative to current commonly applied models. Results show that in most comparisons RMM forecasts outperform those based on any individually selected distributional model.     

A scenario for torus T destruction via a global bifurcation

We show a scenario of a two-frequency torus breakdown, in which a global bifurcation occurs due to the collision of a quasi-periodic torus T² with saddle points, creating a heteroclinic saddle connection. We analyze the geometry of this torus-saddle collision by showing the local dynamics and the invariant manifolds (global dynamics) of the saddle points. Moreover, we present detailed evidences of a heteroclinic saddle-focus orbit responsible for the type-II intermittency induced by this global bifurcation. We also characterize this transition to chaos by measuring the Lyapunov exponents and the scaling laws.     

Production planning with load dependent lead times

Lead times impact the performance of the supply chain significantly. Although there is a large literature concerning queuing models for the analysis of the relationship between capacity utilization and lead times, and there is a substantial literature concerning control and order release policies that take lead times into consideration, there have been only few papers describing models at the aggregate planning level that recognize the relationship between the planned utilization of capacity and lead times. In this paper we provide an in-depth discussion of the state-of-the art in this literature, with particular attention to those models that are appropriate at the aggregate planning level. Received: September 2005 / Revised version: November 2005 AMS classification: 46N10 All correspondence to: Stefan Vo?     

Production planning under uncertainty in textile manufacturing

Textile manufacturing consists of yarn production, fabric formation, and finishing and dyeing stages. The subject of this paper is the yarn production planning problem, although the approach is directly applicable to the fabric production planning problem due to similarities in the respective models. Our experience at an international textile manufacturer indicates that demand uncertainty is a major challenge in developing yarn production plans. We develop a stochastic programming model that explicitly includes uncertainty in the form of discrete demand scenarios. This results in a large-scale mixed integer model that is difficult to solve with off-the-shelf commercial solvers. We develop a two-step preprocessing algorithm that improves the linear programming relaxation of the model and reduces its size, consequently improving the computational requirements. We illustrate the benefits of a stochastic programming approach over a deterministic model and share our initial application experience.     

Production planning with discounting and stochastic demands

A general continuous review production planning problem with stochastic demand is considered. Conditions under which the stochastic problem may be correctly solved using an equivalent deterministic problem are developed. This deterministic problem is known to have the same solution as the stochastic problem. Moreover, conditions are established under which the deterministic equivalent problem differs from a commonly used deterministic approximation to the problem only in the interest rate used in discounting. Thus, solving the stochastic problem is no more difficult than solving a commonly used approximation of the problem.     

A 2-approximation for minmax regret problems via a mid-point scenario optimal solution

In this note, a 2-approximation method for minmax regret optimization problems is developed which extends the work of Kasperski and Zielinski [A. Kasperski, P. Zielinski, An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters 97 (2006) 177-180] from finite to compact constraint sets.