Capacity constraints in multi-stage production-inventory systems applying material requirements planning theory

Thi Thu Thuy Huynh

CAPACITY CONSTRAINTS IN MULTI-STAGE PRODUCTION-INVENTORY SYSTEMS – APPLYING MATERIAL REQUIREMENTS PLANNING THEORY

PROFIL 23 PRODUCTION-ECONOMIC RESEARCH IN LINKÖPING LINKÖPING 2006

Production-Economcic Research in Linköping (PROFIL) Box 10034 S-58010 Linköping, Sweden affiliated to The Department of Production Economics Linköping Institute of Technology S-581 83 Linköping, Sweden Tel: 013-28 10 00 ISBN 91-974579-2-2 Copyright 2006 Thi Thu Thuy Huynh LTAB Linköpings Tryckeri AB 2006.992

PREFACE The objective of the PROFIL series is to provide information on research and other developments within the field of Production Economics by associates of Linköping Institute of Technology. Production Economics is basically an engineering discipline. It focuses on topics treating the interface between engineering and management and is therefore interdisciplinary in nature. It attempts at a two-way scientific integration; on the one hand to apply economic knowledge and reasoning to engineering and manufacturing problems, on the other, to utilise the arsenal of existing mathematical and quantitative engineering methods for analysing economic and managerial issues. It focuses on various allocation problems, in particular on the optimal use of productive resources within manufacturing and other industries. It encompasses developments in theory and application, wherever engineering and technology meet the managerial and economic environment in which industry operates. From the economic science perspective, the methodological approach is based on the theory of production, a branch of microeconomic theory, and on methods of production and operations management. During the last several decades this theory has been integrated with mathematical and statistical models and methods from operational research and management science. The quantitative economic approach has thereby in a natural manner obtained a firm footing within the field – a development which has been strongly supported and encouraged by many Swedish industrialists and others. Among the multitude of problems covered by this subject area can be found the development of principles for production planning and control on different levels and with varying scope. Rules for scheduling and sequencing work operations, the development of economic criteria for maintenance routines, principles for quality and inventory control etc. are other items of major interests, as well as methods, principles and procedures for investment planning and financial decisions, and also general theoretical frameworks. In this fascinating field of research, a host of interesting and intricate problems are awaiting solution, and their v

practical implementation may often be just round the corner. The field is also experiencing considerable attention today – from the academic as well as the practical point of view. The competitive edge of many world class companies is nowadays gained through manufacturing excellence, for instance from lead time and inventory reductions. Education and research in these areas are therefore important and rewarding, perhaps more so now than ever before. This twenty-third publication in the PROFIL series entitled Capacity Constraints in Multi-Stage Production-Inventory Systems - Applying Material Requirements Planning Theory has been written by Thi Thu Thuy Huynh, who is presenting it as her doctoral thesis in Production Economics at Linköping Institute of Technology. Linköping in January 2006

Robert W. Grubbström FVR RI Professor

vi

FOREWORD I started my doctoral studies in February 2002 in the Department of Production Economics at Linköping Institute of Technology. While being a doctoral student for four years, I owe a lot to my teachers, family and friends. First of all, I would like to express my gratitude to my supervisor, Professor Robert W. Grubbström, who has supported me throughout the whole process. He has contributed to many of the basic ideas of this dissertation. Without his guidance, I never could have finished this. I am greatly indebted to Professor Marija Bogataj and Professor Ludvik Bogataj, who have spent a lot of time with me for discussing suitable models and approaches. My thanks to Professor Ludvik Bogataj are not only for his valuable comments on my work, but also for his willingness to act as Faculty Opponent for this thesis. My appreciation is also expressed to Professor Christopher O'Brien, Professor Lars-Erik Andersson and Professor Anders Segerstedt for their kindness in taking on responsibility as Committee Members. At Billerud Skärblacka AB, I have received enthusiastic help from Ivo Fronzaroli, Marie Ardell and Mats Andersson. I greatly appreciate their help and the time they generously spent with me. I would like to show my deep thanks to Docent Ou Tang who has supported me with several valuable pieces of advice in my work as well as on my conference trips. My thanks go to all my colleagues in Department of Production Economics for making the department a nice place to work in. Living in a foreign country, which is so far away from my home country, is not easy. I would like to thank the family of Son, Tuyet and Viet Ha,

vii

the family of Bo, Gabriella and Filippa, and the family of Märtha. They have given me a lot of help making my life easier and more enjoyable. I would also like to thank Lan, my room mate. We have spent a pleasant time together, which will be remembered all my life. Many thanks go to Phuong, who has helped me in programming the examples of this thesis. I also wish to thank several friends, whom I cannot list here, for sharing with me an interesting time in Sweden. Finally, no word can express my deep gratitude to my parents, my sisters and my brothers for their love and for their encouragement throughout my long period of study.

Linköping in January 2006 Huynh Thi Thu Thuy

viii

CONTENTS 1 1.1 1.2 1.3 1.4

INTRODUCTION ......................................................................... 1 Background and Motives ............................................................... 1 Objectives ...................................................................................... 4 Limitations..................................................................................... 5 Outline and Scientific Contribution ............................................... 7

2 2.1

LITERATURE REVIEW AND RESEARCH FRAMEWORK.. 11 Capacity-Constrained Multi-Stage Production Planning and Inventory Control......................................................................... 11 2.1.1 Deterministic Demand .................................................... 12 2.1.2 Stochastic Demand ......................................................... 14 2.1.3 Models Applied in Industry ............................................ 14 The Application of MRP Theory Employing Laplace Transform and Input-Output Analysis to Multi-Level Multi-Stage Production and Inventory Systems................................................................. 15 Capacity-Constrained Multi-Level Multi-Stage Production Inventory Systems – Some Notation and Explanations ............... 16

2.2

2.3

3 3.1

3.2

3.3 3.4 3.5 3.6

ANALYSIS OF STANDARD ORDERING POLICIES WITHIN THE FRAMEWORK OF MRP THEORY .................................. 21 The Fundamental Equations of MRP Theory .............................. 23 3.1.1 Definitions ...................................................................... 23 3.1.2 Properties of Cumulative Requirements ......................... 24 Time Development of Production for Basic Ordering Policies ... 27 3.2.1 Lot-For-Lot (L4L) Policy ............................................... 27 3.2.2 Fixed Order Quantity (FOQ) Case.................................. 28 3.2.3 Fixed Period Requirements (FPR) Case ......................... 29 Solutions to Non-Negativity Conditions for Available Inventory with Requirements as Discrete Events......................................... 30 Solution to Non-Negative Conditions for Available Inventory with Requirements as Continuous Events............................................ 33 Optimal FOQ and Optimal FPR when External Demand is Stochastic..................................................................................... 36 Summary...................................................................................... 41

ix

4

4.1 4.2

4.3 4.4 5 5.1 5.2 5.3 5.4 6 6.1 6.2 6.3 6.4 6.5

6.6

A HEURISTIC METHOD FOR THE CAPACITY CONSTRAINED PROBLEM WITH NON-ZERO LEAD TIMES ..................................................................................................... 43 Problem Formulation ................................................................... 43 Heuristic Method ......................................................................... 45 4.2.1 Starting Point .................................................................. 46 4.2.2 Moving Procedure .......................................................... 46 4.2.3 Reduction Procedure....................................................... 51 4.2.4 Improvement Procedure.................................................. 52 Numerical Examples.................................................................... 53 Conclusion ................................................................................... 57 CAPACITATED PRODUCTION-INVENTORY SYSTEMS IN DISCRETE TIME WITH NON-ZERO LEAD TIMES .............. 59 Assumptions and Notation........................................................... 60 Basic Model ................................................................................. 61 Numerical Examples.................................................................... 65 Summary...................................................................................... 71 THEORY FOR NON-ZERO LEAD TIMES EXTENDED TO CONTINUOUS TIME FRAMEWORK...................................... 73 Assumptions and Notation........................................................... 74 Objective Function and Constrains.............................................. 75 Preliminary Example: One Product Case and Constant Demand .... ..................................................................................................... 78 Multi-Item Cases with Deterministic External Demand and Given Capacity Limits............................................................................ 84 Numerical Examples.................................................................... 86 6.5.1 Two-level Serial Product Structure................................. 86 6.5.2 Three-level Product Structure......................................... 88 Summary...................................................................................... 90

7

CAPACITY-CONSTRAINED PRODUCTION-INVENTORY SYSTEMS WITH NON-ZERO LEAD TIMES IN CONTINUOUS TIME AND WITH STOCHASTIC DEMAND..... ...................................................................................................... 93

7.1 7.2

Objective Function and Constraints.............................................. 94 Dynamic Programming Solution Procedure ................................. 95 x

7.3 7.4

Interpretation of the State and Other Entities ............................... 98 Summary....................................................................................... 99

8

CAPACITY CONSTRAINTS IN A PAPER MILL (BILLERUD SKÄRBLACKA AB) ................................................................. 101 Introduction................................................................................. 101 Production Planning and Capacity Constraint Problems ............ 104 Some Observation and Suggestions............................................ 110

8.1 8.2 8.3 9 9.1 9.2

CONCLUSIONS AND SUGGESTION FOR FURTHER STUDIES.................................................................................... 113 Summary and Conclusions ......................................................... 113 Suggestions for Further Studies.................................................. 115

REFERENCES ..................................................................................... 119

xi

xii

1

INTRODUCTION

In a company, the role of production economics is to maximise the company’s economic result with respect to existing constraints. Production-inventory control is one of the important techniques of production economics.

1.1 Background and Motives The objective of production-inventory control was stated by George W. Plossl (1985) in the following way: “Production and inventory control is concerned basically with providing the information needed for the day-to-day decisions required to reconcile these objectives (maximum customer service, minimum inventory investment, and low-cost plant operation) in plant operations. The fact that these objectives are in basic conflict was readily apparent to the manager who owned his own small manufacturing company. He had invested his money in the machines and equipment in the plant, controlled his own manufacturing schedules and was his own sales representative. When a customer demanded immediate delivery, his alternatives was clear – either spend money on breaking into machine setups and working overtime or let the customer wait. He also had the alternative of carrying inventory in the future – finished products. Part or raw materials – so that he would be able to give his customer better service. The basic conflicts among these objectives existed in this one manager company and they were not easy to resolve, but at least the manger could see the conflict and weigh the alternatives.”

There are two techniques that a manufacturing enterprise may employ for purposes of inventory management (Orlicky 1975). The first one is stock replenishment, popularly known as statistical inventory control or the order point system. Usually, it is applied for single item models. Under this approach, the depletion in the supply of each inventory item is monitored and a replenishment order is issued whenever the supply drops to a predetermined quantity. The second technique is Material Requirements Planning (MRP), which is used for a multi-level, multi-period production planning and control 1

system. Multi-level production and inventory control is the subject of this work. It is commonly much more difficult to analyse and to control than a single-stage method. MRP was introduced in the 1970’s. Much of the credit goes to three individuals by the names of Joseph Orlicky, George Plossl, and Oliver Wight. The American Production and Inventory Control Society (APICS), which was endorsed by Orlicky, Plossl, and Wight, was also credited with the introduction of MRP. MRP is a system that controls inventory levels, plans production, helps to supply management with important information, and supports the manufacturing control system with respect to the production of assembled parts. Figure 1.1 indicates an overview of how the MRP system works. The Product Structure File, the Master Production Schedule (MPS), and the Inventory Master File are the inputs of the MRP system. The output of the MRP system provides which component items that have to be produced and when, and this output can therefore be converted into the capacities required to produce these items. The MRP system does not, itself, plan capacity requirements, but it provides an input to a capacity requirements planning system without which the latter cannot possibly function effectively (Orlicky 1975). In MRP systems, the MPS represent a plan for the production of all enditems over a given planning horizon. It specifies how much of each enditem that will be produced in each planning period, so that future component production requirements and material purchases can be calculated using the MRP component-explosion logic. As such, the MPS has to be feasible so that components can be produced within the capacity available in each time period. Hence the production-inventory system is governed by the capacity constraints. Capacity constraints are considered in inventory planning for determining optimal target inventory positions.

2

Product Structure File

Master Production Schedule

Inventory Master File

Material Requirements Planning

Manufacturing Orders

Purchase Orders

Various Reports

Figure 1.1. An overview of how the MRP system works. Adopted from Foster (2002). Capacity decisions are related to the performance of the system, e.g. the production lead time (Billington et al. 1983). Lead times are the times required to produce or assemble the items. The study of the MRP system has received a great deal of attention and extensions have been made to connect these studies with other theory. With the objective of obtaining optimal solutions, quantitative aspects of planning and-inventory control have resulted in several pieces of theoretical work on MRP and similar multi-level production-inventory systems. One breakthrough in this direction is the application of Laplace transform and Input-Output Analysis methodology. Combining Laplace transforms and Input-Output Analysis has proved to be advantageous for dealing with complex production-inventory systems (Grubbström and Tang, 2000). The useful relationship between the Laplace Transform and the Net Present Value (NPV) has been known for a considerable time 3

(Grubbström, 1967) and the NPV principle, considered as a more correct approach than the average cost measure, is being applied to productioninventory theory in a rapidly increasing number of articles (Grubbström and Lundquist 1977, Grubbström 1980, Thorstenson 1988, Grubbström and Jiang 1990). Here, we continue with this combined methodology. The Input-Output methodology is used to generalise the product structure as well as the timing relationship between items. The fundamental equations of the production-inventory system are described by the combination of transforms and Input-Output Analysis (Grubbström and Ovrin 1992, Grubbström and Molinder 1994). These equations are balance equations in the frequency domain explaining the development of total inventory, available inventory, backlogs and allocations (items reserved for production). The combined methodology of Input-Output Analysis and Laplace (or z-) transforms applied to production-inventory systems, we name MRP theory. More recent outcomes are the dissertations by Molinder (1995), Tang (2000), and by Wang (2002). Different directions of research within MRP theory have been developed, such as by Horvat and Bogataj (1996), Martin (1997), Bogataj (1999), Bogataj and Bogataj (2004). This work treats the capacitated multi-level, multi-stage production inventory problems within MRP theory. Input-Output Analysis and Laplace transforms or z-transforms are then employed as the essential tools.

1.2 Objectives In this thesis, capacity-constrained aspects of multi-level, multi-stage production planning are investigated. The aim has been to extend Material Requirements Planning Theory (MRP Theory) to cover more general problems dealing with capacity constraints, in particular when non-zero lead times are present and the processes take place in continuous time. The methodology used in this book is the quantitative method, which is based on the principles of Operational Research and Management 4

Science. The models are built on mathematically oriented production planning and inventory theory. In previous studies, the NPV objective function of multi-item production- inventory system has been developed. The optimisation conditions and capacity constraints have been generated. The problem is easy to formulate but difficult to solve for the optimal solution, especially when lead times are non-zero and external demand is considered in continuous time. Our aim is to extend our study to situations explaining how productioninventory system should works under capacity constraints when lead times are non-zero. First we develop a heuristic approach to get an inaccurate, but simple, result. Then, we state optimisation approaches for the models in several steps. This thesis also examines the fundamental equations of MRP Theory in order to analyse the possibility to obtain closed-form expressions for the time development of the system, when standard ordering policies of MRP are applied. Input-Output Analysis is used for capturing the Bill of Materials (the product structure) and Laplace transforms for describing the advanced timing requirements (lead times).

1.3 Limitations Multi-level production and inventory control causes several problems and difficulties in practice. Hence we have simplified the models with some assumptions. The product structures which are used in our work are assembly type (left part of Figure 1.2) only. Other types of production such as arborescent structures (right part of Figure 1.2) are not treated in this thesis. The assembly type of product structure is the prevailing type in manufacturing industries, whereas extraction industries, such as mining, often have product structures of the arborescent type. In various process industries there are often different mixtures of these types of structures. In a sequential structure, each item produced has only one predecessor

5

and only one successor. A sequential structure is therefore both of an assembly and an arborescent type.

Assembly structure

Arborescent structure

Figure 1.2. The two basic types of product structures. End products are represented by top-level boxes, and subassemblies or semi-processed products by lower-level boxes. We focus on the multi-period production planning and control system applying MRP theory. Other alternative techniques such as inventory control and order point systems is not the subject of this work. We used the NPV instead of total or average cost as our objective functions. NPV is useful when we apply the Laplace transform. The only “uncertain” aspect considered here is stochastic demand. We mostly assume that lead times are given constants, even if lead times often can be stochastic in the real system. We also ignore other kinds of uncertainty such as machine reliability and production costs changing over time. Other limitations will be explained in the chapters to follow. Often such limitations are consequences of assumptions set forth. 6

1.4 Outline and Scientific Contribution As mentioned above, the multi-stage, multi-level capacity-constrained production-inventory problems have been treated in some previous studies. In Table 1.1, we have described the contribution from previously completed studies and the current contributions from this dissertation. The systems considered are classified with respect to properties of demand, properties of the time scale and with respect to whether or not the lead times are zero (or unity) or not in discrete time, or zero or nonzero in continuous time. The papers relevant to this development are listed in Table 1.1.

Deterministic demand

Discrete time Continuous time Varying τ Varying τ GrubbströmGrubbströmHuynh(2005a) Huynh (2006) τ=0 τ≤1 Segerstedt (1996) Varying τ

Varying τ Huynh (2006)

Stochastic demand τ≤1 Grubbström-Wang (2003)

τ=0

Table 1.1. Contributions to the development of multi-stage, multi-level capacity-constrained production-inventory theory with respect to demand, time framework and lead times τ.

Segerstedt (1996) built a dynamic programming model to solve the capacitated multi-level, multi-stage production-inventory problem under the assumption that lead times either all are zero or all have a length of one period in discrete time. Later, Grubbström and Wang (2003) presented a model in discrete time when external demand is stochastic

7

and production lead times are zero. From 2002 until now, we develop the other cases in turn. This thesis consists of nine chapters. This first chapter is an introduction to the report. Here is presented the background and motives, the objectives, the limitations and the general contents of other chapters. Chapter 2 discusses the major research framework of this work. It also presents a literature review on the topics of multi-stage production inventory planning which focuses on capacity constraints. Our basic model for multi-level, multi-stage production inventory is also presented in this chapter for providing the general formulas of the model and the notation applied. Chapter 3 examines the fundamental equations of MRP Theory. These equations are balance equations in the frequency domain explaining the development of total inventory, available inventory, backlogs and allocations (items reserved for production). The objective is to analyse the possibility to obtain closed-form expressions for the time development of the system, when standard ordering rules of MRP are applied. Standard ordering policies presented are Lot-For-Lot (L4L), Fixed Order Quantity (FOQ), Fixed Period Requirements (FPR) which are mostly used when demand is considered to be deterministic. However, this chapter also analyses aspects of the Economic Fixed Order Quantity policy and the Optimal Fixed Period Requirements when assuming demand to be stochastic. The approaches analyse the problems both in the time domain and in the frequency domain. This chapter is based on Grubbström and Huynh (2005b). In Chapter 4 we present a heuristic methodology for solving a capacity constrained production-inventory model. This chapter extends the Grubbström and Wang (2003) model to the case when lead times are non-zero. It applies the heuristic method of França et al (1996) to solve lot-sizing in a multi-stage system. Firstly, the uncapacitated model is solved by dynamic programming to get an initial solution. If the initial solution is capacity infeasible, a smoothing procedure and an improvement procedure are applied to obtain feasible solution. This gives an inaccurate, but simple solution. The contents of this chapter are rewritten from Grubbström and Huynh (2002). 8

From Chapter 5 to Chapter 7, we solve the capacitated multi-level, multistage problems. The Laplace transform together with Input-Output Analysis are employed as tools for modelling the production-inventory system. This approach has been successfully used for formulating a theoretical base for Material Requirements Planning. The development follows the steps described below. In Chapter 5, we assume that demand is deterministic. The model is considered in discrete time and production lead times are non-zero. A dynamic programming model is formulated for the purpose to solve the optimisation of our objective function. The objective function is the NPV in this and the two following chapters. Here is the first time we introduce an efficient state space for dynamic programming, in which historical values of cumulative production and cumulative demand are given state variables. This chapter is based on Grubbström and Huynh (2006). In Chapter 6, we turn to continuous time theory and develop the corresponding methodology for the case that lead times are non-zero, while keeping external demand deterministic. Our emphasis is on the design of the state space, the properties of which depend on the product structures (the input matrix), the distribution of lead times among the production processes (the lead time matrix), and on the historical sequences of production and demand vectors. Once an efficient state space is designed, dynamic programming once again is applied as the solution method. The Net Present Value Principle is applied. This chapter is based on Grubbström and Huynh (2005a). In Chapter 7, we cover a model with stochastic demand in continuous time. The lead times are allowed to be non-zero. This is the most general system treated, and all other theory referred to, may be considered as special cases hereof. In Table 1.1, the thick-line triangle represents this theory. Appropriate states for applying dynamic programming are also designed. Once again, the Net Present Value is applied. The Laplace transform together with Input-Output Analysis have been employed as tools in constructing the model. The content of this chapter comes from Huynh (2006).

9

In addition, in Chapter 8, the production planning procedures applied in a paper mill have been studied, and they are here presented in the form of a case study. We investigate the production planning and related capacity-constraints of this plant. Chapter 9 summarises our work and states some of our conclusions. There we have also listed some further issues suggested for future research.

10

2

LITERATURE REVIEW AND RESEARCH FRAMEWORK

Production planning has a fundamental role in any manufacturing operation. The problem is to decide what type of product, and how much of each product that should be produced in future time periods. The decisions should be based on many factors, including period machine capacity, production lead times, holding costs, etc. Of primary importance is the estimate of demand for manufacturer's products in upcoming periods. Multi-stage production planning and inventory control is one of the most challenging problem areas in the field of manufacturing management (Axsäter et. al., 1986). One of the problems concerned is the application of MRP Theory to multi-stage lot sizing. MRP should be ranked at the top for analysing multi-level production-inventory control (Axsäter and Rosling, 1994). The widespread and popular use of MRP systems in industry has also resulted in an increased interest in the topic of decision making in capacitated multi-stage production-inventory system. This chapter provides a literature review of work treating capacitated multi-stage production-inventory systems and the application of MRP theory and Input-Output Analysis together with Laplace transforms to production-inventory systems.

2.1 Capacity-Constrained Multi-Stage Planning and Inventory Control

Production

We structure this section in the following areas: - Deterministic demand, multi-stage production planning and inventory control, - Stochastic demand, multi-stage production planning and inventory control. - Multi-stage production planning and inventory models applied in industry. 11

2.1.1 Deterministic Demand Throughout this literature review of deterministic demand models, only discrete-time approaches have been found. Billington et al (1983) modelled the general MRP problem with capacity constraints. They presented an integer linear programming model of a general capacityconstrained multi-level MRP system. They limited themselves to very few constrained facilities (one or two), since they used a simple heuristic optimisation method. In 1994, also Tempelmeier and Helber used a heuristic for solving multi-item, multi-level lot-sizing problems with multiple capacity constraints. França et al (1996), have used a heuristic method for solving lot-sizing in multi-stage systems. First, they used the Wagner-Whitin dynamic lotsizing algorithm for each item of the system. Subsequently, a smoothing procedure and an improvement procedure are introduced for finding feasible capacity solutions. Segerstedt (1996) dealt with an optimisation approach for the multilevel, multi-stage capacity problem. Demand was assumed to be deterministic and the discrete production lead time either zero or unity. Dynamic programming was applied to find the optimum solution using the NPV as objective function. Ip et al. (2000) solved the earliness and tardiness production scheduling and planning problems. They applied a genetic algorithm in order to obtain an optimal solution to the multi-product production environment. Their objective was to find an optimal lot-size production schedule within a production planning and scheduling horizon such that the total cost of earliness and tardiness penalties could be minimised while satisfying the manufacturing process capacity constraints. Both a genetic and a linear programming approach were used and compared. A heuristic genetic algorithm for capacitated lot-sizing problems was developed by Xie and Dong (2002). With a zero lead time assumption, they built a model to minimise the total cost for a multi-stage production-inventory model. Their product structure could be a single level system, or a serial or an assembly system, and other variants. The capacity constraints could be of several types: uncapacitated, capacitated 12

single resources and/or capacitated multiple resources. It should be noted that the cost of computations and computation time for this algorithm is significant, since the complexity of problem is very high. Recently, Clark has built some models for capacity-constrained multilevel MRP systems with deterministic demand. In Clark (2003), three mixed integer programming (MIP) models and solution methods were developed to assists in identifying a capacity feasible MPS in MRP systems. An optimisation of capacity utilisation model was formulated and then solved using two approaches based on model approximation and sequential decomposition. The objective function applied was the traditional cost principle. Lead times were here assumed to be zero. In contrast, not avoiding lead times, Clark and Armentano in their report (1993) explicitly dealt with lead times in their multi-stage lot sizing problems treated. The limited capacity manufacturing system also was treated by Bouhia and Abernathy (2003). In this paper, they defined a list of ordering and scheduling policies in a multiple product, multiple plant case to maximise profits subject to capacity limits of the system. Their solution method was based on simulation methodology. Pongcharoen et al. (2002) introduced a genetic algorithm for the finite capacity scheduling of complex products with multiple levels in the product structure. Their algorithm including problem encoding, chromosome representation and initialisation, genetic operation, repair process, fitness measurement and chromosome selection is described in detail. A statistical analysis showed that the size of the problem has a major influence on the penalty costs concerned. Jolayemi and Oloruniwo (2004) developed a deterministic model for planning production and transportation quantities in a multi-plant and multi-warehouse environment, where opportunities to increase capacity levels were available. A mixed integer linear programming model was applied to analyse this model.

13

2.1.2 Stochastic Demand In practice, almost every production-inventory is subject to influences with uncertainty. This may be external demand, the supply lead time or other operational parameters (Tang, 2000). Here, we will be dealing with the uncertainty of external demand only. Albritton, M., et al (2000) considered a multi-product system in a single stage model, each resource having a finite capacity. The demand for each product was stochastic with log-normal distributions. When demand for a product exceeded the available inventory for that product, the manufacturer would lose sales. They solved this problem with two variants of Monte Carlo sampling-based optimisation techniques, to which they refer as simulation-based optimisation methods. However, they did not consider any multi-stage aspect. Grubbström and Wang (2003) have developed a capacity-constrained multi-level multi-stage production-inventory system with stochastic demand and zero lead times. Their optimisation methodology was dynamic programming. In their results stated, a comparison was made between the capacitated and uncapacitated problems indicating the value of adding new capacity. Brander et al (2005) have presented a simulation study under stationary stochastic demand. They used a heuristic approach to calculate the lot size for the economic lot scheduling problem. In this study, the actual demand had a uniform distribution. The purpose of this paper was to examine if a deterministic model could be used when demand has a stationary stochastic distribution. The authors concluded that the model used for determination of lot size was of lesser importance than the decision rule used for identifying the item to produce and, in particular, when to produce it.

2.1.3 Models Applied in Industry. There are some papers dealing with multi-product multi-period problems in industrial systems. Yan (2000) presented a hierarchical stochastic production planning for flexible automation workshops. Their software 14

package, named as stochastic interaction/ prediction algorithm, was developed as a result of this study. A capacity planning system that considered both the capacity and the capability of equipment was developed for multi-product semiconductor fabs (Chen et al, 2005). Recently, Mula et al (2006) presented a new linear programming model for medium term production planning in a capacity constrained MRP, multi-product, multi-level and multi-period manufacturing environment. This paper provided three fuzzy models with flexibility in the objective function. The paper demonstrated the usefulness and significance of MRP modelling with flexible constraints under uncertainty in demand. Their model was tested using real data from an automobile seat manufacturer.

2.2 The Application of MRP Theory Employing Laplace Transform and Input-Output Analysis to Multi-Level Multi-Stage Production and Inventory Systems The idea of applying Input-Output Analysis to MRP and multi-level production and inventory systems has been studied for some years in the Department of Production Economics at Linköping Institute of Technology. In Grubbström and Lundquist (1989), the relationships between InputOutput Analysis, MRP and production function were discussed. They concluded that there was an obvious relationship between master production scheduling, MRP, the bill of material (BOM), manufacturing resource planning (MRP II), and a general linear production-economic system interpreted in terms of an input-output model. The useful relationship between the Laplace Transform and the Net Present Value (NPV) was presented by Grubbström (1967). Moreover, the NPV principle, considered as a more correct approach than the average cost measure, has been applied to production-inventory theory in 15

an number of articles (Grubbström and Lundquist 1977, Grubbström 1980, Thorstenson 1988, Grubbström and Jiang 1990), Van der Laan (2003), and Teunter (2003). Applying the combination of transforms and Input-Output analysis to production-inventory was presented in Grubbström and Ovrin (1992) and Grubbström and Molinder (1994), and was further developed in Molinder (1995). In Grubbtröm and Ovrin (1992), the theory was originally introduced using the z-transform for application in discrete time. In Grubbström and Molinder (1994) and Molinder (1995), the theory was converted from discrete time to continuous time by introducing the Laplace transform. The advantages from combining the Laplace transform and Input-Output Analysis when dealing with complex production-inventory systems have been argued in Grubbström and Tang (2000). Grubbström and Tang (1997) have reviewed some early writings related to the topics of MRP and Input-Output Analysis. They also presented simple examples to further explain the interrelationship between these two methodologies. Recently, a few publications on capacitated multi-stage productioninventory applying MRP theory have appeared (Grubbström and Wang (1999), Grubbström and Wang (2000a), Grubbström and Wang (2000b), and Grubbström and Wang (2003)). There are also other recent outcomes such as the theses of Molinder (1995), Tang (2000), and of Wang (2002).

2.3 Capacity-Constrained Multi-Level Multi-Stage Production Inventory Systems – Some Notation and Explanations. We now describe the capacity-constrained multi-level multi-stage production inventory systems. Our basic notation is introduced for the application in all chapters to follow.

16

time until given horizon.

T N ’

number of all items in the system.

N

number of end items

M

number of resources constraining production.

s

complex Laplace frequency.

ni

number of set-ups for the production of batches of item i.

tij

time at which batch no j of item i is completed (decision variable), i = 1, 2, ... , ni . lead time for the production of item i.

τi  s) τ(

ν ij

( N × N ) -dimensional lead time matrix with a lead time operator e sτ i in its ith diagonal position and zeros elsewhere. jth set-up of the production of item i referred to completion time tij . As a time function ν ij may be written as a sequence of Dirac impulses δ (t − tij ) , j = 1, 2, ... ni .

ν ( s ) Ki

ρ

hij′ hkj′′ ri ci wk Ck(t)

vector of all completion times in Laplace transform notation set-up cost for producing a batch of item i,. continuous interest rate per time unit. number of units of item i required to produce one unit of its immediate successor j. Collected into the input matrix H′ . capacity of resource k needed to produce one unit of item j collected into the input matrix H′′ . H′ and H′′ make up the joint input matrix H. sales price per unit of end product i collected into the row vector r. echelon production cost per item i collected into the column vector c. variable cost for using resource k per time unit collected into the column vector w. Available capacity of resource k at time t.

17

Di

external demand rate of item i at time t.

Di (t )

external cumulative demand per time unit of item i from t

time 0 to t, Di (t ) = ∫ Di (α ) dα . 0

Pij

number of units of item i (lotsize of batch no j) completed at time tij .

Pi (t ) Bi(t)

cumulative number of units of item i produced from time 0 to t. level of stockouts of item i at time t.

Ri(t)

Available inventory of item i at time t.

NPV

Net Present Value, objective function.

E (·)

expectation operator.

x (t )

short-hand notation for a time derivative of x(t).

Tildes or the operator £ { ⋅ } are used to denote Laplace transforms of the corresponding time functions, i. e.

f ( s ) = £ { f (t )} =

∞

∫ f (t )e

− st

dt =

0

∞

∑fe n=0

− stn

for a continuous f (t ) or a discrete

n

time function f n , t

respectively, and bars for cumulative functions, like f (t ) =

∫ f (α )dα

or

0

fn =

n

∑f

k

.

k =0

In Grubbtröm (1999), an NPV approach for the general model of multilevel multi-stage production-inventory problem was presented. The following expression is the NPV of the cash flow,

( (

)

(

)

 ( ρ ) − ρ E B ( ρ ) − E ( B(T ) ) e − ρT E ( NPV ) = r E D

−(c + w )P ( ρ ) − Kτ ( ρ )ν ( ρ ) ,

) (2.1)

18

where r and K are N-dimensional row vector containing the components rj (sales prices) and Kj (set-up costs), respectively, and (c + w) an (N + M)-dimensional row vector with components ci + wi. The lead time matrix τ ( ρ ) appearing in the last term accounts for allocating the set-up costs to the beginning of the lead time, since ν ( ρ ) is defined from the completion dates. The production costs have been allocated to the completion dates by using the (N + M)-dimensional column production vector P ( ρ ) .

(

)

 ( ρ ) is an N-dimensional column vector of component In (2.1), E D

presenting expected external demand discounted to time zero with no consideration to stockouts, ρ E B ( ρ ) is a similar vector of discounted

(

)

changes in backlogs, and E ( B(T ) ) e contains correction terms for the sake of backlogs not being satisfied at the horizon T, since the process then terminates and no more production is planned. − ρT

To get the optimal solution, we search for the maximal value of (2.1) subject to the following constraints.  ( s ) is cumulative production P ( s ) less The available inventory R  ( s ) and cumulative internal demand cumulative demand D

Hτ ( s )P ( s ) and must be non-negative. +

   ( s ) = ⎡ R (0) − B(0) + (I − H′τ ( s))P( s) − D( s) ⎤ , R ⎢ ⎥ s ⎣ ⎦

(2.2)

[·]

 ( s ) is the total is the maximum operator Max{0, ⋅} , P production of all items and Hτ ( s )P ( s ) is the internal demand. In (2.2), all vectors are N-dimensional

where

+

If external demand cannot be satisfied, we assume that this demand is backlogged and satisfied at the time available inventory starts to become positive one again. 19

 (s) + D  (s) ⎤ + ⎡ ′  − − − B (0) R (0) ( I H τ ( s )) P B ( s ) = ⎢ ⎥ s ⎣ ⎦

(2.3)

Regarding end items (the N’ first components), the non-negativity is taken care of by the backlogging opportunity. For lower-level items, the backlogs are only allowed for external demand, but internal demand must always be met in order for the production plan to be feasible (the available inventory constraint):

  ( s) = £ −1 ⎧⎨ R (0) − B(0) + (I − H′τ ( s ))P( s ) ⎫⎬ ≥ 0 , £ −1 R s ⎩ ⎭

{

}

(2.4)

where £ −1 { ⋅ } denote the inverse Laplace transform. The second constraint is that of the capacity limitations, ⎧ H′′( τ ( s ) − I )P ( s ) ⎫ £ −1 ⎨C (s) − ⎬≥0. s ⎩ ⎭

(2.5)

In the next chapters, we will search for the optimal solution to (2.1) subject to constraints (2.4) and (2.5) following several steps of development.

20

3

ANALYSIS OF STANDARD ORDERING POLICIES WITHIN THE FRAMEWORK OF MRP THEORY

In MRP theory the time development of the production-inventory system is determined by a set of fundamental equations on the one hand, and external demand and production decisions, on the other. The fundamental equations are balance equations applicable to available inventory, total inventory and backlogs, using Input-Output Analysis for capturing the Bill of Materials and Laplace transforms for describing the advanced timing requirements (lead times). This chapter aims to examine the fundamental equations of MRP Theory into in order to obtain closed-form expressions for the time development of the system, when standard ordering policies of MRP are applied. The fundamental equations of MRP Theory have been developed in several earlier papers, beginning with Grubbström and Ovrin (1992) and in some earlier unpublished studies. These equations are balance equations in the frequency domain explaining the development of total inventory, available inventory, backlogs and allocations. Input-Output Analysis is used for capturing the Bill of Materials and Laplace transforms for describing the advanced timing requirements (lead times) In Grubbström and Tang (2000) an overview is presented. This chapter analyses the question of developing closed-form expressions for production when applying basic ordering rules. Order sizes are to be decided in time when inventories are zero or near to zero. In Grubbström and Ovrin (1992) the problem treated here was touched upon. In that paper the processes took place in discrete time, and the ztransformation was applied. Grubbström and Molinder (1994) and Molinder (1995) also followed up some research into this issue in the continuous time case.

21

In Orlicky (1975), some standard ordering policies such as Lot-For-Lot (L4L), Fixed Order Quantity (FOQ), Fixed Period Requirements (FPR) are defined. The L4L rule, being the simplest (also called “as required”) involves an order to be placed exactly large enough to cover requirements. This means that available inventory is kept at a zero level (assuming no initial inventories). In L4L, both the size of the order and the interval between orders will vary over time in a general case. Production, by this rule, is therefore adapted directly to requirements. With the FOQ policy, the order size is always the same. An order is placed as soon as there is not enough available inventory to cover requirement. If demand fluctuates, the interval between orders also must fluctuate. In general, available inventory will only reach a zero level on occasion. Applying the FPR policy, the interval during which total demand is generated and which the order should cover is constant. An order is placed just large enough to cover the total requirements during each such interval. At the end of these intervals, available inventory will have dropped to zero. We present a brief overview of the fundamental equations of MRP Theory in Section 3.1. This is followed by deriving the basic properties of production for the three ordering policies in relation to this theory in Section 3.2. Sections 3.3 and 3.4 are devoted to solving for the production development. In Section 3.5, the optimal FOQ and optimal FRP are presented when demands are stochastic.

22

3.1 The Fundamental Equations of MRP Theory 3.1.1 Definitions

Figure 3.1. Flowchart of the fundamental equations of MRP Theory (Grubbström and Tang 2000). The fundamental equations of MRP Theory are balance equations describing the time development of total inventory, available inventory, backlogs, and allocations (see Grubbström and Tang, 2000). With the policies we are studying, backlogs will not occur in deterministic demand cases. In such cases, the fundamental equations for total inventory and available inventory may be written:

 (s) S(0) + ( I − H ) P ( s ) − D , S ( s ) = s

(3.1)

    ( s ) = R (0) + ( I − Hτ ( s ) ) P ( s ) − D( s) , R s

(3.2)

where S is the column vector of items in inventory (including  is the column vector of items in available inventory allocations), R  is the vector of external demand, P (total inventory less allocations), D is the vector of items produced, H is the input matrix (the Bill of Materials), and I is the identity matrix. The lead time matrix τ ( s ) is a matrix with lead time operators in its diagonal positions:

23

⎡ e sτ1 ⎢ 0 τ ( s ) = ⎢ ⎢ # ⎢ ⎣⎢ 0

0 e

sτ 2

# 0

" 0 ⎤ ⎥ " 0 ⎥ . % # ⎥ ⎥ " e sτ N ⎦⎥

(3.3)

Internal (dependent) demand is given by Hτ ( s )P ( s ) , since the input matrix and lead time matrix together determine all advanced requirements of sub-components in amount and timing, given a production schedule P ( s ) . The main problem treated in this chapter, is how production P is determined by each of the policies, when facing a given external  . (independent) demand D In one-item systems, there is no internal (dependent) demand and, thus, independent and dependent demand, on the one hand, and available and total inventory, on the other, will coincide. The fundamental equations (1)-(2) then collapse into: R (0) + P ( s ) − D ( s ) . R ( s ) = s

(3.4)

3.1.2 Properties of Cumulative Requirements The minimum necessary production to meet external (independent) requirements is always given by

( I −Hτ )−1 D ( s ) = ⎛⎜⎝ I + Hτ +( Hτ )2 +( Hτ )3 + ... ⎞⎟⎠ D ( s ) ,

(3.5)

where the Neumann expansion has been used. This expansion is valid as long as the numerical values of all characteristic roots of H are less than unity. For assembly systems, in which H is triangular with zeros along its main diagonal and above, this is indeed so. The expansion will converge in at most N terms, where N is the dimension of H. 24

Assuming only one end product at the top level, we have ⎡ D1 ⎤ ⎢ ⎥  (s) = ⎢ 0 ⎥ , D ⎢# ⎥ ⎢ ⎥ ⎣⎢ 0 ⎦⎥

(3.6)

and minimum cumulative requirements become ⎡ I − Hτ −1 ⎤ D / s = ⎡I + Hτ + Hτ 2 + Hτ 3 + ... ⎤ D / s ) ⎥ 1 ( ) ( ) ⎢⎣( ⎣ ⎦ col 1 1 ⎦ col 1

(3.7)

The triangular nature of H for an assembly system creates the following first elements ⎡ I − Hτ −1 ⎤ ) ⎥ D1 / s = D1 / s ⎢⎣( ⎦ row1 (3.8) ⎡ I − Hτ −1 ⎤ ( ) ⎥ D1 / s = e sτ1 H 21D1 / s ⎣⎢ ⎦ row 2

(

(3.9)

)

⎡ I − Hτ −1 ⎤ ( ) ⎥ D1 / s = e sτ1 H13 + H 32 H 21e sτ 2 D1 / s ⎣⎢ ⎦ row 3 (3.10) ⎡ I − Hτ −1 ⎤ ( ) ⎥ D1 / s ⎣⎢ ⎦ row 4

(

)

= e sτ1 H14 + H 42 H 21e sτ 2 + H 43 H 31e sτ 3 + H 43 H 32 H 21e s (τ 2 +τ 3 ) D1 / s (3.11) This reveals that requirements occur at times in advance of external demand in such a way that steps are generated sums of lead times ahead of top-level requirements. The further down in the product structure tree, the more opportunities for additional steps exist. For instance, on level 4, if all relevant H ij are non-zero, then, generated by an external demand

25

event at t , items will be required at the points in time t − τ 1 , t − τ 1 − τ 2 , t − τ 1 − τ 3 , and t − τ 1 − τ 2 − τ 3 , whereas on level 3, items may be required only at t − τ 1 and t − τ 1 − τ 2 . The total number of possible times increases geometrically, but all need not exist. One may also note that all possible times at a higher level are repeated again at all lower levels. Therefore the set of possible times for the entire system can be found by studying the lowest level in the system. But zeros in the matrix below the diagonal will rule out some combinations. A sequence of external demand events together with the set of lead times will thus generate a sequence of possible internal demand events. On levels above the lowest level, the sequence will be a subset of the sequence at the bottom level. Certain points in time may be covered more than once at least two reasons, (i) if external demand includes events at distances equal to combinations of lead times, and (ii) if combinations of lead times happen to be equal (such as if τ 2 were equal to τ 3 above).

Figure 3.2. Cumulative requirements as a staircase. In total, we can therefore regard cumulative requirements on any level (including the top level) to be made up of a staircase of steps occurring at the times t0 , t1 , t2 , … , of which several steps may have a zero height.

26

These requirements are given by  ˆ ( s ) = Hτ ( s )P ( s ) + D  /s, D

(

)

(3.12)

for a general production policy, and in the general L4L case by (see Section 3.2.1 below)   /s ˆ ( s ) = ( I − Hτ ( s ) )−1 D D

(3.13)

When there is only one end item in the L4L case, we have  ˆ ( s ) = ⎡( I − Hτ ( s ) )−1 ⎤ D / s D ⎣ ⎦ col 1 1 The staircase is illustrated in Figure 3.2 for an individual item.

(3.14)

3.2 Time Development of Production for Basic Ordering Policies 3.2.1 Lot-For-Lot (L4L) policy

Figure 3.3. The Lot-for-Lot Policy. Production of an item (thick staircase) follows exactly total requirements (sum of independent and dependent demand, thin staircase). 27

In the L4L case, with zero initial available inventory R(0) = 0, the solution is perfectly simple, also in the multi-item case with non-zero lead times. It is then just a matter of keeping available inventory at a zero level. This means     ( s ) = R (0) + ( I − Hτ ( s ) ) P( s ) − D( s ) = 0 , R s

(3.15)

from which production is determined as −1 ˆ ( s) ,  (s) = D P ( s ) = ( I − Hτ ( s ) ) D

(3.16)

as is illustrated in Figure 3.3. If there are non-zero initial available inventories, the expression needs to be adjusted slightly. 3.2.2 Fixed Order Quantity (FOQ) case A fixed order quantity policy may be specified for any item in an MRP system. However, in practice it would be applicable to items with ordering cost sufficiently high to rule out ordering in net requirement quantities, period by period. The replenishments occur as available inventory approaches to zero. With the FOQ policy, having Q as the fixed order size, production for an individual item will behave according to nˆ −1

P ( s ) = Q ∑ e − sTn ,

(3.17)

n =0

where Tn is the time when the nth batch is completed (made available), see Figure 3.4. These are the variables that need be determined by the policy. When production is other than L4L, the requirements on lower levels will depend on production on levels above. This implies, in the general case, that new sets of possible times of requirement events might be introduced.

28

Figure 3.4. The Fixed Order Quantity Policy (FOQ). Production of an item is made in equally-sized batches as late as possible when avoiding negative available inventory.

Available inventory of this individual item will then be nˆ −1 ⎛  ⎞ R ( s ) = ⎜ R(0) + Q ∑ e − sTn − Dˆ ( s ) ⎟ s −1 , n =0 ⎝ ⎠

(3.18)

and the policy is to make all Tn as late as possible without causing R(t) to become negative.

3.2.3 Fixed Period Requirements (FPR) case Under the FPR policy, the ordering interval is constant and the quantities are allowed to vary. Production of a certain item will thus obey nˆ −1

P ( s ) = ∑ Qn e − snT

(3.19)

n =0

29

where T denotes the constant time interval between orders and Qn is the batch size at time Tn = nT . The FPR policy is demonstrated in Figure 3.5.

Figure 3.5. The Fixed Period Requirements Policy (FPR). Production of an item is made in as small batches as possible to cover future requirements during a constant period, without creating a negative available inventory. The FPR policy requires the Qn to be made as small as possible without violating the non-negativity condition for available inventory. This implies that available inventory is likely to take on a zero value during finite time intervals, which is not the case, other than by chance (or at the end), with the FOQ policy, as seen when comparing Figures 3.4 and 3.5.

3.3 Solutions to Non-Negativity Conditions for Available Inventory with Requirements as Discrete Events As shown above, the L4L policy provides an immediate explicit expression for the production on all levels. For the other two policies, this is not equally simple.

30

In the FOQ case we need to solve for the latest as possible batch times T0 , T1 , T2 , … , such that available inventory R(t) is kept non-negative. The solution in the time domain is simple for the individual item, given ˆ (t ) at the times when there are steps t , t , t ,… the requirements D 0

i

1

2

Examining, for successive values of n, arg max Dˆ (ti −1 ) ≤ nQ < Dˆ (ti ) ≥ 0 , there will be a unique index i ti

)

(

assigned to each n, which we denote in . So, Tn = tin will be the latest time that batch n can be produced. Hence, the solution to the FOQ production staircase is: nˆ −1

− sT P ( s ) = Q ∑ e in / s .

(3.20)

n =0

In the FPR case instead, we need to solve for the smallest possible batch size at times 0, T, 2T, … , not violating the non-negativity of available inventory. The sequence of batches Qn generated by n −1

Qn = Dˆ (( n + 1)T ) − ∑ Qi ,

(3.21)

i =0

or, equivalently, Qn = Dˆ (( n + 1)T ) − Dˆ ( nT ) ,

(3.22)

for successive values of n = 0, 1, 2, … , will uniquely determine the production staircase satisfying the conditions. Hence, the production staircase becomes: nˆ −1

(

)

P ( s ) = ∑ Dˆ (( n + 1)T ) − Dˆ (nT ) e − snT / s . n =0

(3.23)

Until now, we have investigated consequences of the non-negativity requirements in the time domain. 31

A corresponding set of non-negativity conditions in the frequency domain is given in Feller (1971) as the following provisions. If a time function f (t ) having the transform f ( s ) is non-negative in the time domain, then the following property must hold

( −1)

j

d j f ( s ) j = ( −1) f ( j ) ( s ) ≥ 0 , j ds

(3.24)

for all integers j > 0 and all real s. In our case, we are looking at available inventories which for the FOQ policy are given by (assuming initial available inventory to be zero) ⎧⎛ nˆ −1  ⎞ ⎫ R (t ) = £ −1 R ( s ) = £ −1 ⎨⎜ Q ∑ e − sTn − Dˆ ( s) ⎟ s −1 ⎬ = ⎠ ⎭ ⎩⎝ n = 0

{

}

)

(

⎧⎛ nˆ −1 = £ −1 ⎨⎜ Q ∑ e − sTn − ∑ ⎛⎜ Dˆ (tl ) − Dˆ (tl −1 ) e − stl l =1 ⎝ ⎩⎝ n = 0

⎞ ⎞ s −1 ⎫ ≥ 0 ⎟⎟ ⎬ ⎠⎠ ⎭

(3.25)

Choosing the situation for the interval of the ith requirements step and mth batch, and writing m −1

(

)

f ( s ) = Q ∑ e − sTn −∑ ⎛⎜ Dˆ (tl ) − Dˆ (tl −1 ) e − stl ⎞⎟ , ⎠ n =0 l =1 ⎝

(3.26)

g ( s ) = s −1 ,

(3.27)

i

we apply Euler’s formula

(

f ( s ) g ( s )

)

( j)

j ⎛ j⎞ = ∑ ⎜ ⎟ f ( s )( k ) g ( s)( j − k ) k =0 ⎝ k ⎠

(3.28)

to Eq. (3.26). Differentiating f ( s ) and g ( s ) the number of times required, we obtain

32

m −1

i

n=0

l =1

)

(

k k f ( s )( k ) = Q ∑ ( −Tn ) e − sTn −∑ ( −tl ) Dˆ (tl ) − Dˆ (tl −1 ) e − stl ,

(3.29)

g ( s ) j − k = (−1) j − k ( j − k )!s −1− j + k ,

(3.30)

and thus

( −1)

j

(

f ( s ) g ( s )

)

( j)

= ( −1)

j

j

j!

∑ k !( j − k )! f (s)

(k )

g ( s )( j − k ) =

k =0

k j i j ! ⎛ m −1 − sTn j ( sTn ) ˆ (t ) − Dˆ (t ) e − stl ( stl ) ⎜ Q e D − ∑ ∑ ∑ ∑ l l −1 k! s j +1 ⎜ n =0 k! k =0 l =1 k =0 ⎝ j! → j +1 mQ − Dˆ (tl ) ≥ 0 , s k

=

)

(

)

(

⎞ ⎟ ⎟ ⎠ (3.31)

for large values of j. This again provides the result in (3.20).

3.4 Solutions to Non-Negativity Conditions for Available Inventory with Requirements as Continuous Events In cases when the cumulative requirements are assumed to be a continuous time function given by an analytical expression, we may apply Cauchy’s Residue Theorem for solving for production in the FOQ and FPR policy cases. A residue is the coefficient of the first negative power in a Laurent expansion around a pole, i. e. where the numerator of an expression evaluates to zero. For the FOQ policy, we need to solve for the points in time when available inventory drops to zero.

{

}

R (t ) = £ R ( s )

−1

−1

⎧⎛ nˆ −1  ⎞ ⎫ = £ ⎨⎜ Q ∑ e − sTn − Dˆ ( s ) ⎟ s −1 ⎬ . ⎠ ⎭ ⎩⎝ n = 0

33

(3.32)

Assuming zero initial inventories and writing the Laurent expansion of

 Dˆ ( s ) as

 Dˆ ( s ) =

∞

∑ds

j =−∞

j

(3.33)

j

for the nth batch, we have

R (t ) =

1 β + i∞ ⎛ ⎞ wt ˆ ⎜ nQ / w − D( w) ⎟ e dw , ∫ w = β − i ∞ 2π i ⎝ ⎠

(3.34)

which evaluated by the Residue Theorem will be  1 β + i∞ ⎛ ⎞ nQ / w − Dˆ ( w) ⎟ e wt dw = ⎜ ∫ = − ∞ β w i 2π i ⎝ ⎠ ⎛  ⎞ ⎛ nQ ⎞ = Res ⎜ − ∑ ⎜ Dˆ ( w)e wt ⎟ = ⎟ w=0 ⎝ w ⎠ residues ⎝ ⎠ ∞ ⎛ ∞ ( wt ) k ⎞ = nQ − ∑ ⎜ ∑ d j w j ∑ ⎟ = 0. k! ⎠ residues ⎝ j =−∞ k =0 R (t ) =

(3.35)

As an example, when requirements increase linearly and cumulative requirements therefore increase quadratically, cumulative requirements  behave according to Dˆ ( s ) = as −3 , where a is the slope of the linearly increasing requirements. Then, the Laurent expansion collapses into ∞

∑d w

j =−∞

j

j

= aw−3 ,

(3.36)

with the only non-zero coefficient d −3 = a . In this case, the only pole is at w = 0, so

34

∞ ∞ ⎛ ∞ ⎛ ( wt ) k ⎞ ( wt ) k Res ⎜ ∑ d j w j ∑ = Res ⎜ aw−3 ∑ ⎟ w=0 k ! ⎠ w=0 ⎝ k! k =0 k =0 ⎝ j =−∞

⎞ 2 ⎟ = at / 2! , ⎠

(3.37)

and R (T ) = nQ − aT 2 / 2 = 0 .

(3.38)

The time of the nth batch will be T = 2nQ / a . Hence, cumulative production in the FOQ case will follow P ( s ) = Q ∑ e − s

2 nQ / a

/s.

(3.39)

n

In the FPR case instead, production has the structure nˆ −1

P ( s ) = ∑ Qn e − snT ,

(3.40)

n =0

and available inventory will be

{

}

R (t ) = £ R ( s )

−1

−1

⎧⎛ nˆ −1  ⎞ ⎫ = £ ⎨⎜ ∑ Qn e − snT − Dˆ ( s ) ⎟ s −1 ⎬ . ⎠ ⎭ ⎩⎝ n = 0

(3.41)

At the end of the nth step of the production staircase (at t = nT), we have R (nT ) =

 1 β + i∞ ⎛ n −1 ⎞ Qm / w − Dˆ ( w) ⎟ e wnT dw , ∑ ⎜ ∫ w i β = − ∞ 2π i ⎝ m=0 ⎠

which evaluated by the Residue Theorem will be R (nT ) =

 1 β + i∞ ⎛ n −1 ⎞ Qm / w − Dˆ ( w) ⎟ e wnT dw = ∑ ⎜ ∫ w i β = − ∞ 2π i ⎝ m=0 ⎠

⎛ n −1 ⎞ ⎛  ⎞ = Res ⎜ ∑ Qm / w ⎟ − ∑ ⎜ Dˆ ( w)e wnT ⎟ = w=0 ⎠ ⎝ m=0 ⎠ residues ⎝ 35

(3.42)

n −1

= ∑ Qm − m=0

∞ ⎛ ∞ ( wt ) k ⎞ j d w ⎟ = 0. ⎜ ∑ ∑ j ∑ k! ⎠ residues ⎝ j =−∞ k =0

(3.43)

In the quadratically increasing requirement case with cumulative



requirements Dˆ ( s ) = as −3 , we thus obtain n −1 ⎛ ( wnT ) 2 R (nT ) = ∑ Qm − Res ⎜ d −3 w3 w=0 2! m=0 ⎝ n −1 ( nT ) 2 = ∑ Qm − a =0. 2! m=0

⎞ ⎟= ⎠ (3.44)

The size of the nth batch is therefore

( (n + 1)T ) − ( nT ) 2

Qn = a

2

2

= ( n + 1/ 2 ) aT 2 ,

(3.45)

and the cumulative production staircase becomes: nˆ −1

nˆ −1

n =0

n =0

P ( s ) = ∑ Qn e − snT = aT 2 ∑ ( n + 1/ 2 ) e − snT .

(3.46)

3.5 Optimal FOQ and Optimal FPR when External Demand is Stochastic We now assume that external demand is a stochastic process D(t) of the renewal type, i.e. D (t ) =

∞

j

j =1

k =1

∑ δ (t − ∑τ k ) ,

(3.47)

which is made up of sequence of unit impulses δ (⋅) , i.e. Dirac delta functions. Here τ k is the stochastic interval between the (k-1)th and kth

36

demand event, τ k ≥ 0 , k = 1, 2, 3... These are considered stochastically independent for different values of k.

Let £ { f (t )} = f ( s ) be the Laplace transform of the probability density function of any individual τ k . From Grubbström (1996), we then obtain the probability of demand during any given interval t to have the value: Q

Pr(

∑τ

k

k =1

{

}

= t )dt = ⎡ £ −1 f Q ( s ) ⎤ dt . ⎣ ⎦t

(3.48)

The transform of expected cumulative demand is therefore 1 E( D ( s )) = s

∞

∑j j =0

1 f . f j (1 − f ) = ⋅ s 1 − f

(3.49)

Assuming a zero safety stock, the FOQ policy implies that Q is ordered at Ti +1 , whenever Q ≥ D(Ti +1 ) − D (Ti ) . Total production will now have the transform; P ( s ) = Q

∞

∑e

− sTi

= Q + Qe − sT1 + Qe − sT1 − sT2 + Qe− sT1 − sT2 − sT3 + ... .

(3.50)

i =0

Because the Ti are independent, we may drop the index i: E ⎡e ⎣

− sT j

⎤ = E ⎡e − sTk ⎤ = E ⎡e − sT ⎤ . ⎣ ⎦ ⎣ ⎦ ⎦

(3.51)

We also have E ⎡⎣e − sT ⎤⎦ =

∞

∫

T =0

Q

Pr(

∑τ

k

= T )e − sT dT =

k =1

37

∞

=

∫ ⎡⎣£ { f (s) }⎤⎦ −1

e − sT dT = f ( s )Q ,

Q

T =0

(3.52)

T

so that expected total production obeys:

(

E ⎡⎣ P ( s ) ⎤⎦ = Q 1+E ⎡⎣e − sT1 ⎤⎦ + E ⎡⎣e − sT1 ⎤⎦ E ⎡⎣ e− sT2 ⎤⎦ + ... Q Q = = . Q − sT 1 − E ⎡⎣ e ⎤⎦ 1 − f ( s )

) (3.53)

Let ν (t ) denote the setup frequency (Molinder, 1996, p. 41), ⎛ ⎜ ⎝

∞

i

⎞ ⎟ ⎠

ν (t ) = ∑ δ ⎜ t − ∑ T j ⎟ , i =0

j =0

(3.54)

where δ ( ⋅) again denotes the Dirac delta function. Then we have the expected setup frequency: E [ν ( s ) ] =

1 1 = . Q − sT  1 − E ⎡⎣ e ⎤⎦ 1 − f ( s )

(3.55)

By multiplying E ⎡⎣ P ( s ) ⎤⎦ by s and taking the limit s → 0 , we obtain the long-term average of production:

sQ Q = lim . Q   s →0 1 − f ( s ) s →0 − f ´( s )Qf ( s )Q −1

Paverage = lim s E ⎡⎣ P ( s ) ⎤⎦ = lim s →0

(3.56)

But from the moment generating property of the transform (Grubbström and Tang, 2006), we also have f (0) = 1,

38

f ′(0) = − lim f ′( s ) = − lim s →0

f ′′(0) = lim s →0

s →0

∞

∫ (−t ) f (t )e

− st

t =0

= − E ⎡⎣τ j ⎦⎤ = − μτ ,

∞

∫ ( −t )

2

f (t )e− st = μτ2 + σ τ2 ,

t =0

where μτ and σ τ2 are the mean value and variance of τ respectively. Then, the average production and setup frequency may be written: Paverage =

1

μτ

,

(3.57)

ν average = lim s E [ν ( s )] = s →0

1 . Q μτ

(3.58)

Assuming the net present value (NPV) of out payments to be minimised, we investigate the optimal value of Q = FOQ . The NPV of the cash flow can be written: cQ + K cQ + K = = NPV= ⎡cE ⎡⎣ P ( s ) ⎤⎦ + KE [ν ( s ) ]⎤ , ⎣ ⎦ s = ρ 1 − E ⎡e − ρT ⎤ 1 − f ( ρ )Q ⎣ ⎦

(3.59)

where c is unit production cost and K is setup cost. On differentiating NPV with respect to Q we obtain

( cQ + K ) f ( ρ )Q ln f ( ρ ) = ∂NPV c + = 2 ∂Q 1 − f ( ρ )Q 1 − f ( ρ )Q =

(

)

(

)

c 1 − f ( ρ )Q + ( cQ + K ) f ( ρ )Q ln f ( ρ )

(1 − f ( ρ ) ) Q

2

39

=0.

(3.60)

which is the necessary optimisation condition. Using a second-order approximation of f ( ρ ) provides us with the following optimal order quantity: EOQ =

2 KDaverage 2K = , ρ cμτ ρc

(3.61)

which has the standard format. Instead, in the fixed period requirement (FPR) case, the quantity Qn = D(tn + T ) − D(tn ) is ordered at the beginning of each interval of length T. Expected production will then be: ⎡∞ ⎤ E ⎣⎡ P ( s ) ⎤⎦ = E ⎢ ( D(tn + T ) − D(tn ) ) e stn ⎥ = ⎣ n =0 ⎦ T 1 . = E ⎡⎣ D(T ) ⎤⎦ 1 + e − sT + e− s 2T + ... = μτ 1 − e − sT

∑

(

)

(3.62)

Average production is obtained as: Paverage = lim s E ⎡⎣ P ( s ) ⎤⎦ = lim s →0

s →0

sT

1 T 1 = , = − sT − sT μτ 1 − e μτ μτ Te

(3.63)

and the average setup frequency s 1 = . − sT s →0 1 − e T

ν average = lim s E [ν ( s) ] = lim s →0

(3.64)

The net present value of the cash flow will be: T 1 K =c + . NPV= ⎡cE ⎡⎣ P ( s ) ⎤⎦ + KE [ν ( s ) ]⎤ − ρT ⎣ ⎦ s= ρ μτ 1 − e 1 − e − ρT 40

(3.65)

To find the optimum interval T, we take the derivative of NPV with respect to T: c ∂NPV μτ = ∂T

(1 − e

− ρT

)

− T ρ e − ρT − K ρ e − ρT

(1 − e ) − ρT

=0.

2

(3.66)

Using again a second-order approximation of e− ρT , the following optimal interval is obtained: T* =

2 K μτ = ρc

2K . ρ cDaverage

(3.67)

This shows that in both of the cases FOQ and FPR, the optimal policies are obtained as when using the traditional average inventory approach with the inventory holding cost interpreted as ρ c , i.e. interest rate times unit production cost.

3.6 Summary The objective of this chapter has been to analyse the previously developed fundamental equations of MRP Theory concerning the basic ordering policies Lot-For-Lot (L4L), Fixed Order Quantity (FOQ) and Fixed Period Requirements (FPR). Our aim has been to find closed-form Laplace transform expressions for the time development of production, when given external demand. When leaving the L4L policy, it is shown that the expressions are possible to derive, but they become considerably more complicated.

41

42

4

A HEURISTIC METHOD FOR THE CAPACITY CONSTRAINED PROBLEM WITH NON-ZERO LEAD TIMES

This chapter extends Grubbström and Wang (2003) by proposing a heuristic method to solve the case when lead times are non-zero. The model is stochastic demand and the lead times are assumed to be constant. The model is treated in a discrete time framework. As before, and in several other publications, the Laplace transform together with Input-Output Analysis are employed as tools for modelling the production-inventory system. This approach has been successfully used for formulating a theoretical base for Material Requirements Planning (MRP). The use of the transform in this chapter is limited to formulating the objective and constraint functions, but the method, as such, operates in the time domain. The objective function is chosen as in Grubbström (1999), and we now search for the optimum solution. The results are decisions concerning the produced amounts and production timing. The objective is to maximise the net present value (NPV) of the cash flow associated with production and demand.

4.1 Problem Formulation In continuous time, the objective function to be maximised is suggested in Grubbström (1999)

(

)

 ( ρ )) − ρ E(B ( ρ )) − E(B (Tˆ ))e − ρTˆ − cР ( ρ ) − Kν ( ρ ), (4.1) E(NPV) = r E( D

subject to capacity constraints

{

}

{}

 ,   ≤ £ −1 C £ −1 H′′τP

(4.2)

43

where, as before, H′′ is the part of the input matrix capturing capacity requirements and C is the transform of capacities

available. Available inventory is non-negative

{

}

 (s) ≥ 0 . £ −1 R

(4.3)

In discrete time instead, Grubbström and Wang (2003) have presented the objective function T

E ( NPV ) = ∑ n =1

N

∑ i =1

ri E

(D −(B in

in

− Bi ( n −1) )

)

e − ρ nΔ

M ⎡ ⎛ ⎤ ⎞ − ⎢ ∑ ⎜ ∑ (ci Pin + K iν in ) + ∑ wk cˆkn ⎟ e − stn ⎥ , k =1 ⎠ ⎣ n =1 ⎝ i =1 ⎦ s=ρ T

N

(4.4)

and suggested the available inventory in discrete time to be written  = R

1  ,  ⎤ = R 0 + (I − Hτ)P ⎡ R + (I − Hτ)P   −D   −D − sΔ ⎣ 0 ⎦ 1 − e− sΔ 1− e

(4.5)

where Δ is the length of the discrete period, since for our discrete process we have cumulative production P = P / 1 − e− sΔ and and

(

(

)

)

 =D  / 1 − e− sΔ , and where R is the vector of cumulative demand D 0

initial available inventory. The capacity constraints (4.2) are reformulated as:

{

}

  ≤ Cnδ (t − nΔ ) , £ −1 H′′τP

(4.6)

where δ (⋅) is the Dirac impulse function.

44

4.2 Heuristic Method The procedure we propose to use follows França et al (1996). This is a heuristic method for finding the best solution for the production quantity of each item in each period. The method involves four procedures, of which the first is finding a starting solution. The three others are named “Moving”, “Reduction” and “Improvement” and are explained after the outline of the algorithm is described. We introduce some additional notation: m = iteration counter S[m] = set of solution variables obtained at iteration m NPV(S[m]) = expected net present value of S[m] mmax = maximum number of iterations of the heuristic. S* = incumbent solution. We have the pseudo-code: m=0 S[m] = starting solution

{procedure P1}

For m = 1 to mmax If S[m] is infeasible then S[m] = Moving {procedure P2} If S[m] is still infeasible then {procedure P3} S[m] = Reduction End If End If If S[m] is feasible then {procedure P4} S[m] = Improvement If NPV (S[m]) > NPV (S*) then S* = S[m] End If Next m. The four procedures are explained in the following sections.

45

4.2.1 Starting Point The starting solution is the solution for the uncapacitated problem which is obtained by optimising (4.4) by dynamic programming as WagnerWhitin algorithm applied to each component of the product structure. First, the algorithm is applied to the end item which has only external demand. Next, the algorithm is applied to lower-level items which have both internal and external demand. The results are the production quantities of each item at each period. If such a solution is capacity feasible, then procedure P4 (Improvement) is called, otherwise, the Moving procedure P2 is applied.

4.2.2 Moving Procedure If procedure P1 yields a capacity infeasible solution and total capacity requirements is smaller than total available capacity, then the Moving procedure P2 tries to find a feasible solution by moving production from an infeasible period to some other period. The period is infeasible if a capacity requirement exceeds capacity available. Given an infeasible period t, an attempt is made to transfer a production quantity qi , t +τ i of the production Pi , t +τ i of component i in period

t + τ i to another period tl + τ i . For each component i that is produced in an infeasible period t + τ i , two alternative quantities are considered for possibly being moved to period tl + τ i : (i) Wi , tl +τ i = the maximum quantity of the production Pi , t +τ i that ensures that the available inventory constraints still are satisfied. (ii) Qi , t +τ i ,k =

the exact quantity of the production Pi , t +τ i which

eliminates the overload of resource k in period t.

46

Qi , t +τ i ,k =

N

∑ ⎡⎣ h′′ P jk

j =1

j ( t +τ i )

+

− Ckt ⎤⎦ / h′′jk ,

(4.7)

where a + = max {a,0} . The amount Qi , t ,k indicates if there is a quantity less than Wi , tl +τ i which can reduce the overuse of resource k in period t to zero. We define the moving quantity as follows

{

qi , t +τ i = Qi , t +τ i , k , Wi , tl +τ i

}

−

(4.8)

where {a, b} = min {a, b} . −

Backward shifts Production shifts from period t = T, T - 1, ..., 2 are analysed. Portions of production, which affect an infeasible period t, are moved to earlier periods until period t becomes feasible. If, after having repeated these moves, period 1 is feasible, then we have a feasible solution. For a given infeasible period t, we consider moving a quantity qi , t +τ i of the production Pi , t +τ i of each item i from period t + τ i to earlier target periods tl + τ i . These periods are such that τ ≤ tl + τ i ≤ t + τ i − 1 , where τ = max {1, the latest period in which there is production of item i prior to period t}. The inventory constraint shows that if qi , t +τ i is moved from period t + τ i to earlier periods tl + τ i , then the available inventory Rij, j =

tl + τ i , ... , t − 1 will increase by an amount qi , t +τ i . We must ensure that the constraints (4.3) are satisfied after such a move:

47

N

Pi (tl +ti ) − ∑ hij′ P j (tl +τ j ) ≥ 0

(4.9)

j =1

Thus, we have N ⎧ ⎫ qi , t +τ i ≤ Wi , tl = min ⎨ Pi (tl +ti ) − ∑ hij′ P j (tl +τ j ) , Pi , t +τ i ⎬ j =1 ⎩ ⎭

(4.10)

The choice of quantity, item, and target period ( q, i, tl + τ i ) is based on a ratio test, (described below), which takes into account the NPV variation and the use of resources, if the quantity qi , t +τ i were moved to

tl + τ i . If, after these moves, period 1 is still infeasible, then we apply a step consisting of forward shifts. Otherwise, an improvement step is considered. Forward shifts Production shifts from periods t = 1, 2, …, T - 1 are considered in that order. Portions of the production which affect an infeasible t are moved from period t + τ i to later target periods tl + τ i . For a given infeasible period t, we consider moving a quantity qi , t +τ i of the production Pi , t +τ i of each item i to later target periods tl + τ i . These periods are such that

t + τ i + 1 ≤ tl + τ i ≤ τ , where τ = min {T, the first period in which there is production of item i after period t}. The moving procedure must ensure that the inventory constraints are satisfied as mentioned above.

48

Ratio test This test is used to choose the quantity, item and target period ( q, i, tl + τ i ) , i.e., the quantity qi , t +τi of the production Pi , t +τ i of item i in period t + τ i to target periods tl + τ i . chosen for smallest ratio test:

Ratio 1(t ) =

The triple

NPV Decrease Value + β Penalty(t ) Excess Capacity Reduction

( q, i, tl + τ i )

is

(4.11)

The term Penalty(t) and its factor β are defined in (4.16) and below. The NPV Decrease Value is the ratio between the change in NPV and total NPV, where the change in NPV is the NPV variation caused shifting quantity qi , t +τ i from period t + τ i to periods tl + τ i . The expression for NPV follows (4.4). When we move amount qi , t +τ i in period t + τ i to target periods tl + τ i , the cumulative production changes from E(Pt +τ i ) to E(Ptl +τ i ) by an amount qi , t +τ i . It causes a decrease of the net present value ΔNPV:

ΔNPV = NPVbefore moving − NPVafter moving , which is calculated as:

49

∑τ E ( ( D t +τ i

ΔNPV = r

n =tl +

in

i

((

+r

∑τ

n = tl + i +1

−

−

M ⎛ ⎞ − ⎜ ci q + K iν i1 + ∑ wk cˆkt ⎟ e − ρt k =1 ⎝ ⎠ − ⎡ r E Di (tl +τ i ) − ( Pi (tl +τ i ) + q ) ⎢⎣ t +τ i −1

)

− Pin ) − ( Di ( n −1) − Pi ( n −1) ) e − ρ nΔ

) −(D −

((

E Di (tl +τ i ) − ( Pi (tl +τ i ) + q )

((

+ r E Di (t +τ i ) − ( Pi ( t +τ i ) − q )

− Pi (tl +τ i )

i ( tl +τ i )

) −(D −

) −(D −

i ( t +τ −1)

i ( n −1)

)

−

)e

− ρ ( tl +τ i )

)

− ( Pi ( n −1) + q ) ) e − ρ nΔ

− ( Pi (tl +τ i −1) + q )

−

)

−

)e

− ρ ( t +τ i )

M ⎤ ⎛ ⎞ − ⎜ ci q + K iν i 2 + ∑ wk cˆkt ⎟ e − ρ tl ⎥ , k =1 ⎝ ⎠ ⎦

(4.12) with

⎧1, if qit = Pit ,

ν i1 = ⎨

(4.13)

⎩0, otherwise, ⎧1, if Pi tl = 0,

and ν i 2 = ⎨

(4.14)

⎩0, otherwise.

When the amount qi , t +τ i is moved from period t + τ i to periods tl + τ i , there will be a variation in the use of the resource in such a period. Let, ⎧ N ⎫ − Ckt ⎪ h′′ P K ⎪ ∑ kj j ( t +τ j ) ⎪ j =1 ⎪ Excess(t ) = ∑ ⎨ ⎬ Ckt k =1 ⎪ ⎪ ⎪⎩ ⎪⎭

+

50

(4.15)

denote the proportion of overuse of the resource in period t. The Penalty term in (4.11) considers the variation of the use of resources caused by the quantity qi , t +τ i being moved from period t + τ i to periods tl + τ i . Defining as:

Penalty = Excess after (t ) + [ Excess after (tl ) − Excess before (tl ) ] , (4.16) where

Excess after (t ) = Excess (t ) after the move , Excess before (t ) = Excess (t ) before the move , and,

Excess Capacity Reduction = Excess before (t ) − Excess after (t ) . Let a cycle denotes a sequence of a backward step and a forward step in the moving procedure. In the first cycles, we set β = 1 . If a feasible is not found in the first cycle, we consider a second cycle with β = 2 . In general, in cycle n, we set β = n . The increase of the factor β at each cycle reflects a greater importance to the overuse of a resource. The maximum number of cycles is specified. If this number is reached and a feasible solution not found, then we change to the Reduction procedure P3. If the solution P2 is infeasible, then the external demand cannot be satisfied. Because backlogs are allowed for end items, we can reduce a production amount of end items. We now turn to the Reduction procedure.

4.2.3 Reduction Procedure For a given infeasible period t, we consider reducing a quantity qi , t +τ i of the production Pi , t +τ i of each item i at period t + τ i . The reducing 51

amount qi , t +τ i is defined as in (4.8). We choose the item and target period ( q, i, tl + τ i ) , by applying a smallest second ratio test:

NPV Decrease Excess Capacity Reduction

Ratio 2 (t ) =

(4.17)

with NPV Decrease defined by:

ΔNPV = NPVbefore reduction − NPVafter reduction , calculated by ΔNPV = r

∑τ E ( ( D T

n = tl +

in

((

T

∑τ

n = tl + i +1

E

−

−

i

M ⎛ ⎞ − ⎜ ci q + K iν i1 + ∑ wk cˆkt ⎟ e − ρ t k =1 ⎝ ⎠ Di ( t +τ i ) − ( Pi ( t +τ i ) − q) −r ⎡ E ⎢⎣

+

)

− Pin ) − ( Di ( n −1) − Pi ( n −1) ) e − ρ nΔ

(( D

i ( tl +τ i )

) − (D −

i ( t +τ −1)

− ( Pi ( tl +τ i +1) − q)

− Pi ( tl +τ i −1)

) − (D −

i ( n −1)

)

−

)e

− ρ ( t +τ i )

)

⎤ − − ( Pi ( n −1) − q ) ) e − ρ nΔ ⎥ . ⎦ (4.18)

After the reduction procedure, if all periods are feasible, we have a feasible solution and we turn to the improvement procedure P4. Otherwise, we conclude that the model is infeasible. 4.2.4 Improvement Procedure Starting from a feasible solution this procedure tries to find a lower cost by moving production to earlier or later periods. The procedure is similar to the moving procedure, also has a backward and a forward step. However, we allow only feasible and improving moves. That means the moving neither causes any capacity restriction to be violated, nor any decrease of the NPV. 52

The procedure ends, when no improved solution which is feasible, can be found.

4.3 Numerical Examples A

1* B

1* C

2* X 1*

1* X

2* X

Figure 4.1. The three-level product structure, one resource requirement In this section, we provide numerical examples to explain our heuristic method. Consider the genaral structure as Fig. 4.1 (N = 3) constrained by one resource (M = 1), over a 10-period planning horizon with the parameters as in Table 4.1. The lead times of A, B and C are 1, 1 and 0, respectively.

Planning hoizon T Interest rate ρ Demand outcome dL, dH Outcome probability Average demand E[DA] Sale revenue rA Set up cost KA, KB, KC Unit production costs cA, cB, cC Variable capacity cost wX B

B

10 0.05 2, 8 0.3, 0.7 6.2 800 50, 50 , 20 100, 50, 50 20

Table 4.1. Parameters of the example

53

Available capacity Cx is constant in each period. We change this level in different cases of the example. From figure 4.1, we have input and lead time matrices:

A ⎡0 0 0 ⎤ A ⎡0 0 0 ⎤ A ⎡e s 0 0 ⎤ ⎢1 0 0 ⎥ ⎢ ⎥ B ⎥ , τ = B ⎢ H′ = B ⎢⎢1 0 0 ⎥⎥ ; H′′ = X [1 1 1] , H = ⎢ s 0 e 0⎥ . C ⎢1 0 0 ⎥ ⎢ ⎥ C ⎢0 0 1 ⎥ C ⎢⎣1 0 0 ⎥⎦ ⎢ ⎥ ⎣ ⎦ X ⎣1 1 1 ⎦ The initial solution is shown in Table 4.2, which was obtained by applying a dynamic programming method to the uncapacitated model. T Item A Item B Item C X

1

2 0

52

0 26 26 78

3 26 0 0 32

4 0 16 16 48

5 16 0 0 20

6 0 10 10 30

7 10 0 0 28

8 0 14 14 42

9 14 0 0 0

10 0 0 0 0

Table 4.2. Initial solution (infeasible, NPV = 203,487) The step of moving procedure are show in table 4.3. Firstly, we choose Cx = 38

t = 10 t=9 t=8

Moving procedure, backward Excess(t) = 0 Excess(t) = 0 Excess(t) = 0.105. Consider PA,9, PB,9, PC,8 Item A: PA,9=14, WA,9 = 0, WA,8 = 0, WA,7 = 0, WA,6 = 0, WA,5 = 0, WA,4 = 0, WA,3 = 0, WA,2 = 0. Hence no production of item A can be transferred to any previous periods. Item B: PB,9 = 0. No production of item B can be transfered to previous periods item C: PC,8= 14.

54

tl + 0 = 7 WC,7 = 14, QC,8 = 4, ⇒ q = 4, ratio = 5.929 tl + 0 = 6 WC,6 = 14, QC,8 = 4, ⇒ q = 4, ratio = 4.935 tl + 0 = 5 WC,5 = 14, QC,8 = 4, ⇒ q = 4, ratio = 11.488 tl + 0 = 4 WC,4 = 14, QC,8 = 4, ⇒ q = 4, ratio = 12.139 tl + 0 = 3 WC,3 = 14, QC,8 = 4, ⇒ q = 4, ratio = 17.990 tl + 0 = 2 WC,2 = 14, QC,8 = 4, ⇒ q = 4, ratio = 18.166 tl + 0 = 1 WC,1 = 14, QC,8 = 4, ⇒ q = 4, ratio = 26.170 Hence, we transfer q = 4 of item C from t +0= 8 to tl +0 = 6. t=7 t=6 t=5 t=4

Excess(t) = 0 Excess(t) = 0 Excess(t) = 0 Excess(t) = 0.026. Consider PA,5, PB,5, PC,4 Item A: PA,5=16, WA,5 = 0, WA,4 = 0, WA,3 = 0, WA,2 = 0. Hence, no production of item A can be transferred to previous periods. Item B: PB,5 = 0. Hence, no production of item B can be transferred to previous periods. Item C: PC,4= 16 tl + 0 = 3 WC,3 = 16, QC,3 = 10, ⇒ q = 10, ratio = 11.900 tl + 0 = 2 WC,2 = 16, QC,3 = 10, ⇒ q = 10, ratio = 16.818 tl + 0 = 1 WC,1 = 16, QC,3 = 10, ⇒ q = 10, ratio = 19.693 We transfer q = 10 of item C from t +0= 4 to tl + 0 = 3.

t=3

Excess(t) = 0.105. Consider PA,4 , PB,4, PC,3 Item A: PA,4=0. Item B: PB,4 = 16 tl +1= 3 WB,3 = 16, QC,3 = 4, ⇒ q = 4, ratio = 15.537 tl +1= 2 WB,2 = 16, QC,3 = 4, ⇒ q = 4, ratio = 8.749 Item C: PC,3= 0 We transfer q = 4 of item B from t+1 = 4 to tl +1= 2.

t=2

Excess(t) =2.158. Consider PA,3 , PB,3 , PC,2 Item A: PA,3=26, WA,3 = 0, WA,2 = 0

55

Item B: PB,3 = 0 Item C: PC,2 = 30 We transfer q = 30 of item C from t +0 = 2 to tl +0 = 1.

After 6 cycles of backward and forward steps, we obtain a feasible solution as listed in Table 4.3. T Item A Item B Item C X

1 0 0 0 38

2 0 19 19 37

3 9 0 6 38

4 0 16 5 37

5 9 7 26 38

6 6 0 0 38

7 9 10 0 38

8 5 14 10 38

9 14 0 0 28

10 14 0 0 0

Table 4.3. A feasible solution ( NPV = 18,708). Next, we make some backward and forward cycles to find improvement solutions. In our case, no new improved solution could be found. Therefore, we choose the solution from Table 4.3 as a final solution. The results are shown in Table 4.4 where we compare four levels of available capacity: • • • •

Tight capacity: available capacity Cx = 33 Normal capacity: available capacity Cx = 38 Loose capacity: available capacity Cx = 45 And uncapacitated model. Uncapacitated model

NPV Ratio =NPV/CX %

20 348 100

Tight capacity Cx= 33 16 425 497.73 80.7%

Normal capacity Cx= 38 18 708 492.32 91.9%

Loose capacity Cx= 45 20 052 445.60 98.5%

Table 4.4. NPV from four levels of available capacity.

56

In Table 4.4, the NPV is compared for cases when the capacity level is varied from 33 to 45 units of capacity and when model is uncapacitated.

4.4 Conclusion In this chapter, we have proposed a model for a capacity-constrained production-inventory system extended with non-zero lead times. The net present value is employed as the objective function. The solution procedure applies a heuristic method, which we applied to three-level product structure. The results in Table 4.4 show that the NPV increases, when the available capacity increases, but with a small degressive element showing "diminishing returns to scale" (Table 4.4 and Figure 4.2). 800

NPV

20000

Ratio

NPV 18000

700

16000 600

14000 12000

Ratio

10000

500

8000 400 6000 4000

300

2000 0 32

34

36

38

40

42

44

200 46

Capacity

Figure 4.2. NPV and NPV over Capacity as Functions of Capacity

57

58

5

CAPACITATED PRODUCTIONINVENTORY SYSTEMS IN DISCRETE TIME WITH NON-ZERO LEAD TIMES

This chapter deals with the non-zero lead time problem. The developments are presented within a discrete time framework. Lead times are assumed to be given constants and the Net Present Value Principle is applied. In some previous papers (Segerstedt (1996), Grubbström and Wang (2003)), although the theory developed concerned situations in which the lead times could be any non zero constants, in order to design an analytical solution procedure, the assumption was made that lead times were zero, in order to be able to apply dynamic programming. Cumulative production and cumulative demand were taken as state variables. In this chapter, we remain in the discrete time framework and develop a methodology for the case that lead times are non zero, whereas demand is deterministic. Our emphasis is on the design of the state space, the properties of which depend on the product structures (the input matrix), the distribution of lead times among the production processes (the lead time matrix), and on the historical sequences of the production vectors. We also now apply a dynamic programming procedure in order to solve the non-zero lead time problem. The objective is to choose the best production plan maximising the net present value of the cash flow associated with production and demand. We thus extend the treatment from Grubbström and Wang (2003) in one dimension, at the same time limiting our attention to deterministic demand situations. The main novelty in this chapter is the design of the state space necessary to handle arbitrary non-zero lead times. Whereas cumulative production of all items, at the point when production decisions were to be taken, could be used in the zero-lead time solution procedure as a state description, we now extend the state space to include a sequence of prior cumulative production vectors. This sequence has a sufficient 59

number of elements to cover all opportunities that decisions might have had to limit future opportunities and affect the economic outcome. This chapter is based on Grubbström and Huynh (2006). However, the example in Section 5.3 is more extensive (four levels) as compared to the example included in Grubbström and Huynh (2006) (three levels).

5.1 Assumptions and Notation We consider a complex production-inventory system operating within a discrete finite time horizon T. The following assumptions are made: • • • • • • • •

Demand is deterministic and assumed to take place at discrete points in time. Production of all items concerned take place in batches of arbitrary size at the same discrete points in time. For each item, external demand is deterministic No backlogs are allowed for internal demand. For externally demanded items, backorders are allowed and are satisfied whenever a replenishment takes place. Capacity constraints are assumed to be of the momentary kind, meaning that capacity may neither be borrowed, nor lent, between different periods, see Grubbström and Wang (2000b). Only assembly-type product structures are considered. No setup times are considered

In addition to the notation previously introduced in Section 2.3, the following symbols are introduced:

τi

lead time for the production of item i,

τˆ

maximum lead time of all items,

wˆ i

variable cost for each unit of item i to use capacity resources determined by the requirements H′′ , collected in the row ˆ, w ˆ = wH′′ , vector w available capacity of resource k in period n, collected in a column vector Cn ,

Ckn

60

cˆkn Wn Q n −1

amount of capacity of resource k used in period n, collected in a column vector cˆ n , maximum expected NPV contributed from stage n onwards, when all subsequent decisions are chosen optimally, state array immediately prior to production decisions at stage n.

5.2 Basic Model In the capacity-constrained multi-level production-inventory problem treated in this paper, non-zero lead times are considered. The decision variables are Pin , i =1, 2, ... , N, n =1, 2, ... ,.T. However, since, at time n, previous cumulative production Pn −1 is known, we might equally well choose the elements of current cumulative production Pn = Pn −1 + Pn as decision variables. Our objective is to maximise the net present value of the total cash flow involved, subject to non-negative available inventory constraints and to limits on the available capacities of different resources. The cash flow is generated by a cash-inflow and a cash-outflow. The cash-outflow is calculated from the production costs for all items and the cash-inflow from the sales revenues of products (as in Grubbström and Wang (2003)). The NPV of the cash-outflow is thus obtained as M ⎡T ⎛ N ⎤ ⎞ NPVproduction = − ⎢ ∑ ⎜ ∑ ( ci Pin + K iν in ) + ∑ wk cˆkn ⎟ e− stn ⎥ k =1 ⎠ ⎣ n =1 ⎝ i =1 ⎦ s=ρ

and the NPV of the cash-inflow as

(

NPVsales = ∑∑ ri Din − ( Bin − Bi ( n −1) ) T

N

n =1 i =1

)

61

e − ρ nΔ

(5.1)

(

)

 − (1− e − sΔ ) B − B e − s (T +1) Δ ⎤ = r ⎡⎣ D T ⎦ s= ρ ,

(5.2)

where the deferred revenues due to backlogs are taken care of. This provides the objective function: NPV = NPVsales + NPVproduction .

(5.3)

Our choice of solution procedure is dynamic programming. Since the lot sizes are possible to choose arbitrarily, there is never more than one setup of a particular item in any period. As pointed out above, the decision variables in period n are chosen as cumulative production Pn . In order to define our state space, we introduce the symbol τˆ for the maximum of all production lead times:

τˆ = Max (τ i ) .

(5.4)

i

We then define the array Q n −1 as a sequence of τˆ previous cumulative production vectors:

⎡ P1( n −τˆ ) P1( n −τˆ +1) .... P1( n −1) ⎤ ⎢ ⎥ P2( n −τˆ ) P2( n −τˆ +1) .... P2( n −1) ⎥ ⎢ Q n −1 = ⎢ # ⎥ ⎢ ⎥ ⎣⎢ PN ( n −τˆ ) PN ( n −τˆ +1) .... PN ( n −1) ⎦⎥

(5.5)

This array represents the state prior to taking the nth production decision Pn . The transition from state Q n −1 to state Q n may then conveniently be written:

62

⎡ P1( n −τˆ ) P1( n −τˆ +1) .... P1( n −1) ⎤ ⎡0 0 ... 0 ⎤ ⎡ 0 0 ... P1n ⎤ ⎢ ⎥ ⎢ ⎥ P2( n −τˆ ) P2( n −τˆ +1) .... P2( n −1) ⎥ ⎢1 0 ... 0 ⎥ ⎢ 0 0 ... P2 n ⎥ ⎢ ⎢ ⎥ + , Qn = ⎥ ⎢ # ⎥ ⎢# .... ⎥ ⎢ # ⎥ ⎢ ⎥⎢ ⎥ ⎢ 0 1 0 ⎦⎥ ⎣⎢ 0 0 ... PNn ⎦⎥ ⎢⎣ PN ( n −τˆ ) PN ( n −τˆ +1) .... PN ( n −1) ⎥⎦ ⎣⎢

 

  

  Q n−1

ˆ τ) ˆ square matrix (τ,

(5.6)

N rows, τˆ columns

⎡ 0 0 ... 0 ⎤ ⎢1 0 ... 0 ⎥ ⎥, where the post-multiplication by the ( τˆ × τˆ )-matrix ⎢ ⎢# .... ⎥ ⎢ ⎥ ⎢⎣ 0 1 0 ⎥⎦ having unit elements in the diagonal below the main diagonal, moves the columns in Q n −1 one step to the left, discarding the left-most column and emptying the right-most column to be filled with Pn in the summation. Using this formula for the transition from Q n −1 to Q n shows the transition to be dependent on the current decision variables Pin alone, making the transition equation suitable for dynamic programming. The available inventory constraints are written:

{ }

 ≥ 0, £ −1 R

(5.7)

with 1  ⎤ = R 0 + (I − Hτ)P  , ⎡ R + (I − Hτ)P   −D   −D (5.8) − sΔ ⎣ 0 ⎦ 1 − e − sΔ 1− e since for our discrete process we have P = P / 1 − e − sΔ and  = R

(

(

)

)

 =D  / 1 − e − sΔ , and where R is the vector of initial available D 0 inventory. The capacity constraints are formulated as:

63

{

}

  ≤ Cnδ (t − nΔ) , £ −1 H′′τP

(5.9)

  (during which are interpreted as internal demand for resources H′′τP any period) being limited to available given capacity levels collected in   is the inverse transform of H′′τP  . the vector Cn , and where £ −1 H′′τP

{

}

The comparison in (6.9) is interpreted as a comparison of the coefficients of the impulses. As shown in Grubbström and Wang (2000), all constraints (available inventory as well as capacity) may be collected  ≥ 0 by extending R with M additional into a single relation R =£ −1 R n

{ }

rows in a suitable way. We let ΔNPVn be the contribution to the NPV from the nth stage, when given Q n −1 . Furthermore, let Wn be the maximum NPV contributed from stage n onwards, when all subsequent decisions are chosen optimally. Adopting the NPV as our objective function, thus leads us to the recursive equation: Wn (Q n −1 ) = Max [ ΔNPVn + Wn +1 (Q n )]

(5.10)

Pn , R n ≥ 0

where ΔNPVn depends on the given Q n−1 and the decision Pn :

(

ΔNPVn = ∑ ri Din − ( Bin − Bi ( n −1) ) e − ρ nΔ N

i =1

)

M ⎡N ⎛ ⎞ − ⎢ ∑ ⎜ ci + ∑ wˆ ki e sτ i ⎟ ( Pin − Pi ( n −1) ) + K i vin k =1 ⎠ ⎣ i =1 ⎝

⎤ + ⎥ e − ρ nΔ , ⎦

(5.11)

with ⎧⎪1, if Pin > Pi ( n −1) , vin = ⎨ ⎪⎩0, if Pin = Pi ( n −1) .

(5.12)

Since the process ends after stage T, we have WT +1 = 0 , and therefore: 64

WT (QT −1 ) = Max ΔNPVT .

(5.13)

PT , RT ≥ 0

Working backwards in time, at each stage determining an argument Pn that maximises ΔNPVn + Wn +1 (Q n ) , given the state Q n −1 , provides us with the optimum policy: Pn* = Pn (Q n −1 ) .

(5.14)

If we depart from the initial situation Q 0 , we thus choose the following optimal production plan constituted by a sequence of decisions obeying this policy: P1 (Q 0 ) , P2 (Q1 ) , ..., PT (QT −1 ) .

(5.15)

Since we are dealing with processes constrained by capacity limitations, the choice of decision Pn is restricted by available capacity (5.9), this having an impact on the set of available opportunities to choose from.

5.3 Numerical Examples In this section, we provide a few numerical examples to explain and illustrate our basic model in Section 5.2. Consider the four-level product structure shown in Figure 5.1. With A, B and C being items and X a resource with limited momentary capacity, the input matrices and the lead time matrix will be the following: A ⎡0 0 0 ⎤ H′ = E ⎢⎢1 0 0 ⎥⎥ , C ⎢⎣1 1 0 ⎥⎦

A ⎡1 0 0 ⎤ ⎢ ⎥ 2s H′′ = X [ 2 1 1] , τ = B ⎢ 0 e 0 ⎥ , C ⎢⎣ 0 0 e s ⎥⎦

assuming that the top-level item A has a zero lead time, item B has a lead time of two periods and that item C has a lead time of one period. 65

A

1* B

1* C

2* X

1* X 1*

X

1*

C

1*

X

Figure 5.1. Four-level product structure with one type of capacity requirement. A computer program was developed to solve the recursive equations (5.10) with parameters given values according to Table 5.1. On the one hand, available capacity was varied between three constant levels, on the other, a separate run with varying demand was carried out. When solving the dynamic programming recursion, a complete enumeration procedure for integral values of the feasible production volumes was used.

planning horizon (time periods) T initial inventory RA0 , RB0 , RC0 interest rate ρ per time period demand outcomes DA sales revenue rA set-up costs K A , K B , K C unit production costs cA , cB , cC variable capacity cost wX variable product capacity costs wˆ A , wˆ B , wˆ C

10 0, 6, 3 0.05 3 1000 50, 50, 50 100, 50,50 20 40, 20, 20

Table 5.1. Parameter values for the numerical examples 66

Item n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 A External 3 3 3 3 3 3 3 3 3 3 demand 3 6 9 12 15 18 21 24 27 30 Cumulative demand Cumulative 2 4 6 8 10 12 14 17 19 21 production -1 -2 -3 -4 -5 -6 -7 -7 -8 -9 Net inventory 4 4 4 4 4 4 4 6 4 4 Capacity requirement B Internal 2 2 2 2 2 2 2 3 2 2 demand 2 4 6 8 10 12 14 17 19 21 Cumulative demand Cumulative 0 0 0 4 5 7 9 11 13 15 production 6 4 2 0 2 1 1 1 0 0 0 Net inventory 0 4 1 2 2 2 2 2 0 0 Capacity requirement C Internal 2 6 3 4 4 4 4 5 2 2 demand 2 8 11 15 19 23 27 32 34 36 Cumulative demand Cumulative 0 5 7 11 15 19 23 27 29 31 production 5 3 2 1 1 1 1 1 0 0 0 Net inventory 5 2 4 4 4 4 4 2 2 0 Capacity requirement 9 10 9 10 10 10 10 10 6 4 Total capacity requirements Table 5.2. Results from example with constant demand DA =3 and constant capacity CX = 10. Resulting NPV=10503.12

67

Item n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 A External 3 3 3 3 3 3 3 3 3 3 demand 3 6 9 12 15 18 21 24 27 30 Cumulative demand Cumulative 2 5 8 11 14 17 20 23 27 30 production -1 -1 -1 -1 -1 -1 -1 -1 0 0 Net inventory 4 6 6 6 6 6 6 6 8 6 Capacity requirement B Internal 2 3 3 3 3 3 3 3 4 3 demand 2 5 8 11 14 17 20 23 27 30 Cumulative demand Cumulative 0 0 3 6 9 12 15 18 21 24 production 6 4 1 1 1 1 1 1 1 0 0 Net inventory 3 3 3 3 3 3 3 3 0 0 Capacity requirement C Internal 5 6 6 6 6 6 6 6 4 3 demand 5 11 17 23 29 35 41 47 51 54 Cumulative demand Cumulative 0 6 12 18 24 30 36 42 46 49 production 5 0 0 0 0 0 0 0 0 0 0 Net inventory 6 6 6 6 6 6 6 4 3 0 Capacity requirement 13 15 15 15 15 15 15 13 11 6 Total capacity requirements Table 5.3. Results from example with constant demand DA =3 and constant capacity CX = 15. Resulting NPV=13468.56

68

Item n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 A External 3 3 3 3 3 3 3 3 3 3 demand 3 6 9 12 15 18 21 24 27 30 Cumulative demand Cumulative 2 6 9 12 15 18 21 24 27 30 production -1 0 0 0 0 0 0 0 0 0 Net inventory 4 8 6 6 6 6 6 6 6 6 Capacity requirement B Internal 2 4 3 3 3 3 3 3 3 3 demand 2 6 9 12 15 18 21 24 27 30 Cumulative demand Cumulative 0 0 3 6 9 12 16 21 21 24 production 6 4 0 0 0 0 0 1 3 0 0 Net inventory 3 3 3 3 4 5 0 3 0 0 Capacity requirement C Internal 5 7 6 6 7 8 3 6 3 3 demand 5 12 18 24 31 39 42 48 51 54 Cumulative demand Cumulative 0 7 13 19 26 34 37 46 46 49 production 5 0 0 0 0 0 0 0 3 0 0 Net inventory 7 6 6 7 8 3 9 0 3 0 Capacity requirement 14 17 15 16 18 14 15 9 9 6 Total capacity requirements Table 5.4. Results from example with constant demand DA =3 and constant capacity CX = 20. Resulting NPV=13857.21

69

Item n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 A External 3 4 0 5 0 4 3 5 3 3 demand 3 7 7 12 12 16 19 24 27 30 Cumulative demand Cumulative 2 5 8 11 14 17 20 23 27 30 production -1 -2 1 -1 2 1 1 -1 0 0 Net inventory 4 6 6 6 6 6 6 6 8 6 Capacity requirement B Internal 2 3 3 3 3 3 3 3 4 3 demand 2 5 8 11 14 17 20 23 27 30 Cumulative demand Cumulative 0 0 3 6 9 12 15 18 21 24 production 6 4 1 1 1 1 1 1 1 0 0 Net inventory 3 3 3 3 3 3 3 3 0 0 Capacity requirement C Internal 5 6 6 6 6 6 6 6 4 3 demand 5 11 17 23 29 35 41 47 51 54 Cumulative demand Cumulative 0 6 12 18 24 30 36 42 46 49 production 5 0 0 0 0 0 0 0 0 0 0 Net inventory 6 6 6 6 6 6 6 4 3 0 Capacity requirement 13 15 15 15 15 15 15 13 11 6 Total capacity requirements Table 5.5. Results from example with varying demand DA and constant capacity CX = 15. Resulting NPV=13017.10

70

Type of demand

NPV

Available capacity CX 10 15 20 15

Constant DA=3 Varying DA

Ratio = NPV/ CX

10503.12 13468.56 13857.21 13017.10

1050.31 897.90 692.86 867.81

Table 5.6. Ratio of NPV and available capacity.

The resulting production plans in these four numerical cases are depicted in Tables 5.2 – 5.5. Table 5.6 shows the NPV and the ratio of NPV per available capacity level as functions of the capacity level. The production levels PA, PB, PC are defined according to completion times (as in current theory). The similarity with traditional MRP tableaus is apparent, as one would have expected. B

5.4 Summary When introducing non-zero lead times into the capacitated lot-sizing problem, the complexity of the model grows significantly. However, as shown in Section 5.2, the theoretical analysis is still manageable and requires only small additional conditions, when choosing an appropriate definition of the state space. Therefore, we can conclude the existence of a non-zero lead time extension of MRP Theory. But from a numerical perspective, the volume of computations and associated memory requirements increases substantially, when leaving the zero (or unit) lead time assumption. Still, for some limited structures the problems are still solvable such as three-level product structure (Grubbström and Huynh (2006)) and four-level product structure (Section 5.3).

The four cases chosen have all given solutions that essentially used up all available capacity and produced hardly any inventory or backlogs. The NPV, resulting from these examples, behaves as one might have 71

expected intuitively, namely a close to linear relation between available capacity and NPV, but with a small degressive element showing "diminishing returns to scale" (Table 5. 6 and Figure 5.2). 1100 14000

1050

NPV 1000

12000

950 900

10000

Ratio

850

8000

800

NPV

Ratio

750

6000

700 4000

650 600

2000

550 500

0 10

12

14

16

18

20

Capacity constant demand varying demand

Figure 5.2. NPV and NPV over Capacity as Functions of Capacity (fourlevel product structure).

72

6

THEORY FOR NON-ZERO LEAD TIMES EXTENDED TO CONTINUOUS TIME FRAMEWORK

The solution methodology concerning capacity constraints has been developed in the following steps. In Grubbström and Wang (2003) the problem with stochastic demand, with or without non-zero lead times, was addressed in the discrete time case. In order to find a solution methodology (dynamic programming), lead times were then assumed to be zero. This zero lead time assumption was relaxed in Chapter 5, at the same time limiting the treatment to deterministic demand. The main problem treated below, is to turn from the discrete time deterministic case into the continuous time deterministic case. We thus attempt to find amounts to produce of each item in a multilevel/multi-stage capacity-constrained production-inventory system, which has a known development of external demand. As before, in this chapter we also apply a dynamic programming procedure in order to solve the non-zero lead time problem. The objective is to choose the best production plan maximising the net present value of the total cash flow associated with production and demand. We thus extend our treatment from Chapter 5 in one dimension, still limiting our attention to deterministic demand situations. This extension to include the continuous timing of production adds to complexity, in particular a need to extend the design of the state space to handle arbitrary non-zero lead times embedded in continuous time. As objective function, the Net Present Value (NPV) has often been chosen. Combining Laplace transforms and Input-Output Analysis has proved to be advantageous for dealing with complex productioninventory systems (Grubbström and Tang, 2000). Here, we continue with this combined methodology. Whereas cumulative production of all items, at the point when production decisions were to be taken, could be used in the zero-lead time solution procedure as a state description, the state space was needed 73

to include a sequence of prior cumulative production vectors when enabling non-zero lead times. This sequence had a sufficient number of elements to cover all opportunities that decisions might have to limit future opportunities and affect the economic outcome. In the current study the state space needs to be slightly modified, but, since we are retaining the assumption that production takes place at discrete points in continuous time, the modification required is limited.

6.1 Assumptions and Notation In this chapter we extend the theory from chapter 5 from discrete to continuous time. A complex production-inventory system operating within a finite time horizon T is considered. Basic assumptions are: • External demand is deterministic and is assumed to take place as known processes in continuous time. • Production of all items concerned take place in batches of arbitrary size at discrete points embedded in continuous time. • No backlogs are allowed for internal demand. • For externally demanded items backorders are allowed. • Capacity constraints are assumed to be of the momentary kind, meaning that capacity may neither be borrowed, nor lent, at any time, see (Grubbström and Wang, 2000). • Only assembly-type product structures are considered. We introduce some additional notation for the current continuous time model: wˆ i

nˆ

Q j −1

variable cost per time unit for each unit of item i to use capacity resources determined by the requirements H′′ , ˆ, w ˆ = wH′′ . This notation collected in the row vector w ˆ in Chapter 5, differs slightly from w number of cumulative production vectors used for describing state of system. state of system immediately prior to jth decision. Q j is chosen as a matrix made up of a sequence of nˆ consecutive cumulative production vectors. 74

6.2 Objective Function and Constraints Using the convention that no time functions are truncated at the horizon t = T, when computing the Laplace transforms, we state the following expression for the Net Present Value of the payments concerned. This is the continuous version of Eq. (5.1) in Chapter 5. T

n

NPV = ∑ ri i =1

−∑

∑⎜c P

i =1

j =1

(

− T

i

i

i

t =0

i ij

⎝

− t

i

⎛

ni

N

ρ ρ ∫ ( D (t ) − B (t ) ) e dt − r B (T )e M

+ K iν ij + ∑ wk hk′′i k =1

e ρτ i − 1

ρ

) (

⎞ − ρt Pij ⎟ e ij = ⎠

)

 − sB − ( c + wH′′( τ − I ) / s ) P + Kν ⎤ = ⎡⎣r D ⎦ s=ρ .

(6.1)

The terms of this expression are explained as follows. The following part is the net present value of revenues taking backlogs into account: n

∑ ri i =1

T

∫ ( D (t ) − B (t ) )e i

− ρt

i

t =0

 − sB ⎤ . dt − ri Bi (T )e − ρT = r ⎡⎣ D ⎦ s= ρ

(6.2)

During an interval in which there is a stockout of item i, the backlog changes as demand, and we have Bi (t ) = Di (t ) , and during the interior of this interval there will be no revenues. If there is a momentary replenishment −ΔBi at t ′ , reducing or eliminating Bi (t ) , revenues having the NPV of ΔBi e − ρt ′ will be obtained. When Bi (t ) at t ′ is interpreted as B (t ′) = ΔB δ (t − t ′) (where δ (t − t ′) is a Dirac impulse i

i

function at t ′ ), the contribution to the NPV from the sudden change in Bi (t ) will thus be accounted from the reduction in backlog t′

−ri

∫

t =t ′−0

Bi (t )e − ρ t dt = −ri

t′

∫

ΔBiδ (t − t ′)e − ρ t dt = −ri ΔBi e− ρ t ′ . If there is a

t =t ′− 0

remaining backlog at the horizon Bi (T ) , there has been no, or at least not a sufficient, replenishment at the horizon. This will account for lost sales

75

at T creating a reduction in the NPV by −ri Bi (T )e − ρT as compared to when all demand at the end is satisfied. The production cost term ci Pij + K iν ij is easily interpreted and this cost is timed at tij . It may be questioned if this is the correct timing for the setup, but a modification locating the set-up to the beginning of the lead time rather than at the completion time, would be straightforward and would only add slightly to notational complexity. The variable capacity M e ρτ i − 1 Pij is explained below. cost term ∑ wk hk′′i k =1

ρ

There are two types of constraints involved in this problem. On the one hand, available inventory must be non-negative, in order for the production plan P to be feasible. Available inventory, before external  , may be written as cumulative production less internal demand D  )/s demand. In transform terms, this will be written (R (0) + P − H′τP = (R (0) + (I − H′τ )P ) / s , where I is the identity matrix. Here, R (0) / s is   is internal (dependent) the vector of initial available inventory, H′τP demand of subcomponents required by the production plan P , appropriately timed the relevant lead times in advance of the completion times defining P . Dividing (I − H′τ )P ) by s, represents a time integration of the difference between production and internal demand. This difference, together with initial available inventory, may be used to satisfy external demand and must be non-negative as a time function. Secondly, there is the set of capacity constraints. The demand for capacity is always internal (not considering any external sales of surplus capacity) and, in transform terms, the momentary capacity requirements   . If the capacity of different resources is given may be expressed as H′τP as a vector of time functions C(t), the capacity constraint will be the condition

{

}

 ( s) − H′τ ( s )P ( s ) ≥ 0 . £ −1 C

(6.3)

76

This representation is useful in a discrete time case, when C(t) can be interpreted as a sequence of existing capacities at each point in discrete time. Then H′′ would contain the number of capacity units required per unit of items completed. However, for a continuous time case, it appears more natural to consider capacity requirements to be spread out over the lead time of the production process, rather than located as a spike at the beginning of the lead time. With such an interpretation, H′′ would contain requirements of various types of resources per unit time and per item unit completed. With this representation, the capacity requirements from a resource k for a given completed production Pi of item i at time tij would be hki′′ Pi per time unit during the interval ⎡⎣tij − τ i , tij ⎤⎦ . In transform terms, this requirement can be written: hki′′

e

− s ( ti j −τ i )

s

−e

− sti j

Pi = hki′′

e sτ i − 1 − sti j e sτ i − 1  ′′ Pi . Pe = h i ki s s

(6.4)

Considering all capacity requirements from a total plan P , these would H′′( τ ( s ) − I ) P ( s ) , where I is the identity be given by the expression s matrix, rather than by H′′τ ( s )P ( s ) . The two input matrices H′′ in (6.3) and (6.4) have different dimensions, the former having resource units per item unit alone, and the latter, resource units per item unit and time unit. The overall capacity constraints when given C(t), are thus ⎧ H′′( τ ( s ) − I )P ( s ) ⎫ £ −1 ⎨C (s) − ⎬≥0. s ⎩ ⎭

(6.5)

Our basic problem is to choose values of the components of P including their timing properties tij , such that the objective function NPV in (6.1) is maximised subject to the available inventory (6.3) and available capacity (6.5) constraints.

77

6.3 Preliminary Example: One Product Case and Constant Demand As an introductory example, we choose a very simplified case with only one item and a constant demand rate D(t ) = Dˆ . At first, capacity is unlimited, and backlogging is not allowed, B(t)=0. Because there is only one item, the subscript i may be dropped and the remaining subscript j refers to the stage. Variable capacity cost may be included in the unit production cost c. The net present value is T

n

ˆ − ρ t dt − ∑ NPV = ∫ r De j =1

0

=

r Dˆ (1 − e− ρT )

ρ

n

−∑ j =1

( cP + K ) e

− ρt j

j

( cP + K ) e

− ρt j

j

=

,

(6.6)

where Pj refers to the jth batch completed at time t j . Our problem is to choose all values of Pj and t j that maximise the NPV. Without loss of generality, we define tn +1 = T (although there might be a production decision at tn = tn +1 = T ). The production decision at stage j is thus the pair of decision variables Pj = Pj − Pj −1 and t j . Just before a production set-up at time t j , cumulative production is Pj −1 and this level may be chosen as the state variable. Taking a production decision at that time, the contribution to the NPV (disregarding the constant revenues) will be ΔNPVj ( Pj −1 , Pj , t j ) = − ( cPj + K ) e

− ρt j

.

(6.7)

Since, in this example with unlimited capacity, there is never any advantage to produce more than what is demanded until the next replenishment, cumulative production will always equal cumulative demand just before each such point in time (the so called "inner corner condition" when viewing cumulative production as a staircase function 78

in the same diagram as cumulative demand), Pj −1 = D(t j ) = Dˆ t j ,

(6.8)

so the timing decision t j is forced to be t j = Pj −1 / Dˆ . The contribution to NPV from stage j may therefore be written

ΔNPVj ( Pj −1 , Pj ) = − ( cPj + K ) e

− ρ Pj −1 / Dˆ

,

(6.9)

and the transition between the states Pj = Pj −1 + Pj .

(6.10)

Let W j +1 ( Pj ) be the contribution from stage (j + 1) and onwards, when optimal decisions are chosen based on the state Pj . At stage j we therefore choose Pj so that ΔNPVj ( Pj −1 , Pj ) + W j +1 ( Pj ) = ΔNPV j ( Pj −1 , Pj ) + W j +1 ( Pj + Pj −1 )

is maximised, W j ( Pj −1 ) = max ΔNPVj ( Pj −1 , Pj ) + W j +1 ( Pj + Pj −1 ) .

(6.11)

Pj

At the final set-up at tn , the remaining contribution to the NPV is

(

)

ˆ ˆ − P ) + K e − ρ Pn−1 / Dˆ . ΔNPVn ( Pn −1 , Pn ) = − ( cPn + K ) e − ρ Pn−1 / D = − c( DT n −1

(6.12) Since T is given, and Pn −1 is the current state determined from past decisions, this contribution is given by the state variable and not subject to any maximisation procedure, so

79

(

)

ˆ − P ) + K e− ρ Pn−1 / D . Wn ( Pn −1 ) = ΔNPVn ( Pn −1 , Pn ) = − c( DT n −1 ˆ

(6.13)

The solution to this recursive equation is not so simple as it might seem at first glance. The equation stated here offers a multitude of opportunities. Details of the structure of the solution are found in Grubbström and Kingsman (2004). We now introduce the opportunity of backlogging. This means that the inner corner condition may be violated. At time t j , just before a possible ˆ production decision Pj , cumulative demand is Dt j and cumulative

ˆ − P if production Pj −1 , and there might be a backlog B (t j − 0) = Dt j j −1 ˆ > P . A batch completion of P will reduce the backlog, possibly Dt j j −1 j eliminate it. The state at t j , just before the decision is interpreted as the pair of variables Pj −1 and its timing t j −1 . There are now also two decision variables, when to produce t j and how much to produce Pj . The contribution to the NPV from this decision at t j will be ΔNPV j (t j −1 , Pj −1 , t j , Pj ) = − ( cPj + K ) e

( (

))

(

ˆ −P + r min Pj , max 0, Dt e j j −1

(

(

− ρt j

− ρt j

+

(

+ Dˆ e

− ρ t j −1

) )

− e− ρt ′ / ρ ,

(6.14)

))

where t ′ = max t j −1 , min t j , Pj −1 / Dˆ . The terms are explained as follows. Production costs account for a negative contribution to the NPV − ρt − ρt ˆ −P e j is the by − ( cP + K ) e j . The term r min P , max 0, Dt

(

( ˆ contribution from when there is a backlog max ( 0, Dt j

j

)) − P ) just before j −1

j

j

j −1

t j to be satisfied by the replenishment Pj . If Pj does not suffice to cover the whole backlog, the revenue contribution to the NPV will be − ρt ˆ − P e− ρt j . r Pj e j , otherwise r max 0, Dt The term j j −1

(

80

)

(

)

− ρt Dˆ e j −1 − e − ρ t ′ / ρ accounts for the revenue contribution to the NPV

from current sales between t j −1 and t ′ , the latter time being when a new backlog is incurred. The time t ′ is at least t j −1 and at most t j and depends on the state ( t j −1 , Pj −1 ) . Introducing W j +1 (t j , Pj ) as the contribution to the NPV from stage (j + 1) and onwards, when optimal succeeding decisions are chosen based on the state ( t j , Pj ) , we have the recursive optimisation problem to maximise ΔNPVj (t j −1 , Pj −1 , t j , Pj ) + W j +1 (t j , Pj ) by a suitable choice of t j and Pj : W j (t j −1 , Pj −1 ) = max ( ΔNPVj (t j −1 , Pj −1 , t j , Pj ) + W j +1 (t j , Pj −1 + Pj ) ) . (6.15) t j , Pj

( t , P ) together determines the new state ( t , P ) = ( t , P

The pair of decisions

j

j

j

j

j

j −1

with the old state + Pj ) .

(t

j −1

, Pj −1 )

Let us now introduce capacity constraints into this problem including a fixed lead time τ . Let C(t) be available capacity of one resource required in the amount of h′′ per item unit and time unit during the lead time. A completion of Pj units at time t j will therefore require the availability of h′′Pj units of capacity per time unit during the interval [ t j − τ , t j ]. The condition on Pj from capacity limitations will then be h′′Pj ≤ C (t ) for t j − τ < t ≤ t j . However, if the lead time τ is sufficiently long (or the completion times short apart), there might have been one or more other earlier set-ups during the interval [ t j − τ , t j ] also requiring capacity. Then the limitations on the choice of Pj will be more restrictive and need take into consideration earlier capacity commitments. In order to determine the state at t j , prior to the decision Pj , the history of the

81

production decisions (including their timing) during the lead time need to be included. In the discrete time case treated in Chapter 5, a matrix Q j −1 was introduced to represent the state immediately prior to the jth production decision. This matrix (in our current one-item example, a row vector) was defined as the sequence of the τ preceding cumulative production levels Q j −1 = ⎡⎣ Pj −τ , Pj −τ +1 , ..., Pj −1 ⎤⎦ . In Chapter 5, the maximum of all

lead times τˆ was used for the definition, but with only one item considered in this example, the maximum will be the single lead time τ . The transition from state Q j −1 to state Q j could then conveniently be written: ⎡0 0 ... 0 ⎤ ⎢1 0 ... 0 ⎥ ⎥ + ⎡ 0,0,..., P ⎤ , Q j = ⎡⎣ Pj −τ , Pj −τ +1 ,..., Pj −1 ⎤⎦ ⎢ j   ⎢ # .... ⎥ ⎣  ⎦ τ columns Q j −1 ⎢ ⎥ ⎢⎣0 1 0 ⎥⎦   

(6.16)

square matrix (τ × τ )

where the post-multiplication by the ( τ × τ )-the columns in Q j −1 one step to the left, discarding the left-most column and emptying the rightmost column to be filled with Pj in the summation. In the current continuous time case, the description of a state transition will be more involved, since there is not necessarily the same number of earlier decisions to account for during the given lead time for different transitions. Some decisions, on occasion, might be closer in time than at other times. However, a list of the cumulative production vectors representing decisions during the interval τ will always suffice. Due to the fixed set-up cost K, there can never be an infinite number of optimum production decisions within any finite time interval. Therefore, by choosing a sufficiently large but finite number nˆ of earlier cumulative production vectors as the state description, this will suffice for our purposes, and the transition between states may be written:

82

⎡ 0 0 ... 0 ⎤ ⎢1 0 ... 0 ⎥ ⎥ + ⎡ 0,0,..., P ⎤ . Q j = ⎡⎣ Pj − nˆ , Pj − nˆ +1 ,..., Pj −1 ⎤⎦ ⎢ j   ⎢ # .... ⎥ ⎣  ⎦ Q j −1 nˆ columns ⎢ ⎥ ⎢⎣ 0 1 0 ⎥⎦   

(6.17)

square matrix ( nˆ × nˆ )

The information about the timing of each Pk , i. e. tk , may also be included in Q j . A simple method for this purpose would be to add an extra component tk to each Pk in Q j . The possible variable costs of capacity utilisation, with the interpretation that capacity is used during the lead time τ , are considered to incur a wˆ (e ρτ − 1) − ρt Pj e j . The contribution to the NPV at stage j by −

ρ

contribution to the NPV from decisions at stage j will then be − ρt ΔNPV j (Q j −1 , t j , Pj ) = − ( (c + wˆ (e ρτ − 1) / ρ ) Pj + K ) e j +

( (

))

(

) )

(

− ρt − ρt ˆ −P + r min Pj , max 0, Dt e j + Dˆ e j−1 − e − ρ t ′ / ρ , j j −1

(6.18)

and the recursive optimisation problem W j (Q j −1 ) = max ( ΔNPVj (Q j −1 , t j , Pj ) + W j +1 (Q j ) ) .

(6.19)

t j , Pj

Furthermore, without loss of generality, we may choose cumulative production Pj , including timing t j , rather than Pj (and t j ), as decision variables, since Pj and the state Pj −1 would then define the decision. This shortens our argument notation somewhat: ΔNPV j (Q j −1 , Pj ) = − ( (c + wˆ (e ρτ − 1) / ρ )( Pj − Pj −1 ) + K ) e

( (

(

))

(

− ρt j

) )

− ρt − ρt ˆ −P + r min Pj − Pj −1 , max 0, Dt e j + Dˆ e j −1 − e − ρ t ′ / ρ , j j −1

83

W j (Q j −1 ) = max ( ΔNPVj (Q j −1 , Pj ) + W j +1 (Q j ) ) ,

(6.20)

Pj

where the maximisation is subject to the capacity constraint for t in the interval t j − τ < t ≤ t j , i.e. £ −1 ⎡ h′′ ( e sτ − 1) Pj − Pj −1 / s ⎤ ≤ C (t ) . Finally, ⎣⎢ ⎦⎥ we introduce internal (dependent) demand into this introductory example.

(

)

Let there be requirements of a second item, which is a sub-component, amounting to h′Pj , when Pj is the end item planned to be completed at t j . The timing of this requirement is at t j −τ − τ . Available inventory of this second item must be non-negative throughout. This requires knowledge about available inventory of this second item immediately prior to t j −τ − τ . Thus available inventory, which is given by cumulative production of the component and cumulative earlier production of the end item generating internal demand (and also possibly initial available inventory), will need to be added to the state description. However, we are now leaving the one-item example and proceeding into the general multi-item case of the next section.

6.4 Multi-Item Case with Deterministic Demand and Given Capacity Limits

External

Turning to the general deterministic continuous-time case, the objective function is written

(

) (

)

 − sB − ( c + wH ′′( τ − I ) / s ) P + Kν ⎤ , NPV = ⎡⎣r D ⎦ s=ρ

(6.21)

where r, c, w and K are row vectors capturing economic consequences in the form of external item sales prices, unit production costs, unit variable capacity costs per time unit and set-up costs for batches of each item. D, B, P and ν are column vectors for external demand, backlogs, production and set-ups and H′′ is the input matrix for capacity requirements and τ the lead time matrix, the latter having e sτ i as its 84

diagonal elements and zeros elsewhere. The production and cumulative production vectors may be written n

n

j =1

j =1

− st − st P = ∑ P j e j , P = ∑ P j e j / s ,

(6.22)

and the set-up vector n

− st ν = ∑ ν j e j .

(6.23)

j =1

The timing t j is interpreted to cover any production completion at t j and items that are not relevant at that time will have zero components in their position in P j . Similarly, the set-up vector ν j will contain a unit value for an item completed at time t j and zeros elsewhere. The available inventory and capacity constraints for the whole process are

⎧ R (0) + (I − H′τ )P ⎫ £ −1 ⎨ ⎬≥ 0, s ⎩ ⎭

(6.24)

where R(0) is the vector of initial available inventory and H′ the input matrix for component requirements, and

⎧ H′′( τ ( s) − I )P ( s ) ⎫ £ −1 ⎨C (s) − ⎬≥0, s ⎩ ⎭

(6.25)

 ( s) is the resource vector of available capacity. where C In order to apply dynamic programming, at stage j we need to determine the contribution to the NPV from the current decision P j (or, equivalently, P j ) when given the state Q j −1 just prior to t j , ΔNPVj (Q j −1 , Pj ) , where Q j −1 is a matrix of nˆ previous cumulative

85

production vectors P j −1 , P j − 2 , ... , P j − nˆ , and where nˆ is sufficiently large to capture all production decisions that could have taken place during the longest lead time τˆ = max τ i . The revenue (and backlog) i

consequences need to be split up into their respective contributions to the NPV at the particular stage, whereas the contributions from production costs, capacity costs and set-up costs are obtained in an immediate straightforward way. As in our introductory example, the recursive optimisation for each stage will be given by W j (Q j −1 ) = max ( ΔNPV j (Q j −1 , Pj ) + W j +1 (Q j ) ) ,

(6.26)

Pj

where the decision P j must satisfy conditions (6.24)-(6.25).

6.5 Numerical Examples To calculate these examples we have made use of the Swedish National Super Computer. A program was written in C++.

6.5.1 Two-level Serial Product Structure. In our first example, the product structure is given by Figure 6.1 A

2* X Figure 6.1 Two-level serial product structure.

The parameters are assumed to have values according to Table 6.1.

86

Planning horizon (time periods) T Lead time of A τ A . Interest continuous rate ρ Demand rate Dˆ

10 2 0.05

Sales revenue rA Set-up costs K A Unit production costs cA Variable capacity cost wX per time unit Variable product capacity costs wˆ A per time unit

500 70

3

A

100 20 40

Table 6.1. Parameter values for one product case.

Cumulative production Production time

4 5 9 10 14 15 19 20 2.1 3.1 4.1 5.1 6.1 7.1 8.1 9.1

Table 6.2. Results from example with constant demand Dˆ A =3 and constant capacity CX = 10. Optimum number of batches= 8. Resulting NPV= 3799.03.

Cumulative production Production time

5 2.1

7 3.1

12 4.1

14 5.1

15 6.1

21 7.1

22 8.1

26 9.1

Table 6.3. Results from example with constant demand Dˆ A =3 and constant capacity CX = 15. Optimum number of batches= 8. Resulting NPV= 4845.18.

87

Cumulative production Production time

7 10 17 20 27 30 2.1 3.3 5.3 6.6 9 10

Table 6.4. Results from example with constant demand Dˆ A =3 and constant capacity CX = 20. Optimum number of batches = 6. Resulting NPV=5573.40.

Demand Constant DA=3

Available capacity CX NPV Ratio = NPV/ CX 10 3799.03 379.90 15 4845.18 323.01 20 5573.40 278.67

Table 6.5. Ratio of NPV and available capacity of two-level serial product structure. .

6.5.2 Three-level Product Structure The lead time of A and B are assumed to be τ A = 1, τ B = 2 , and the product structure given as in Figure 6.2.

A

1*

B

1*

X

2*

X

Figure 6.2. Three-level product structure

88

Planning horizon (time periods) T Initial available inventory RA0 , RB0 Interest rate ρ per time period Sales revenue rA Set-up costs K A , K B Unit production costs cA , cB Variable capacity cost per time unit wX Variable capacity cost produced per time Unit wˆ A , wˆ B

10 0, 6 0.05 1000 80, 50 100, 70 20 40, 20

Table 6.6. Parameter values for the three-level product structure.

Item A Cumulative production Production time B Cumulative production Production time

4 6 8 11 14 16 18 22 24 1.1 2.1 3.1 4.1 5.1 6.1 7.1 8.1 9.1 2 6 8 10 12 16 18 2.1 3.1 4.1 5.1 6.1 7.1 8.1

Table 6.7. Results from example with constant demand Dˆ A =3 and constant capacity CX = 10. Optimum number of batches of A = 9, and of B = 7. Resulting NPV=12449.94.

Item A Cumulative production Production time B Cumulative production Production time

6 8 12 15 18 22 27 1.5 3.1 4.1 5.1 6.3 8.0 9.0 3 7 10 16 19 21 24 2.1 3.1 4.1 5.3 7.0 8.0 9.0

30 10

Table 6.8. Results from example with constant demand Dˆ A =3 and constant capacity CX = 15. Optimum number of batches of A = 8 and of B = 7. Resulting NPV=14718.63.

89

Item A Cumulative production Production time B Cumulative production Production time

6 10 1.5 3.3 7 10 2.3 4

16 5 15 5

21 6 18 7

24 8 24 9

30 10

Table 6.9. Results from example with constant demand Dˆ A =3 and constant capacity CX = 20. Optimum number of batches of A = 6 and of B = 5. Resulting NPV=14903.58.

Demand Constant DA=3

Available capacity CX NPV Ratio = NPV/ CX 10 12449.94 1244.99 15 14718.63 981.24 20 14903.58 745.18

Table 6.10. Ratio of NPV and available capacity of three-level product structure.

6.6 Summary When applying dynamic programming to the non-zero lead time capacitated lot-sizing problem in continuous time, the complexity of the states increase enormously. In Section 6.3 and Section 6.4, the theoretical analysis is introduced when choosing an appropriate definition of the state space. In the continuous time case, there is not necessarily the same number of earlier decisions to account for during the given lead time for different transitions. Due to the fixed set-up cost K, there also can never be an infinite number of optimum production decisions within any finite time interval. Therefore, by choosing a sufficiently large but finite number nˆ of earlier cumulative production vectors as the state description, this will suffice for our purposes, and the transition between states may be written as matrix Q j −1 in a similar way as in Chapter 5.

90

But from a numerical perspective, the volume of computations and associated memory requirements has increased substantially. Therefore, we have been forced to examine only very limited structures as in Section 6.4.1 (two-level) and Section 6.4.2 (three-level). In both structures, the three cases chosen have all given solutions the relation between NPV and capacity is close to linear, but with a small degressive element showing "diminishing returns to scale" (Table 6.5, Table 6.10 and Figure 6.3). Ratio of NPV and Capacity 1300 1200 1100

Three-level product structure

1000 900 800 700 600 500

Two-level product structure

400 300 200 100 10

12

14

16

18

20

Capacity

Figure 6.3. NPV over Capacity as Functions of Capacity.

91

92

7

CAPACITY-CONSTRAINED PRODUCTION-INVENTORY SYSTEMS WITH NON-ZERO LEAD TIMES IN CONTINUOUS TIME AND WITH STOCHASTIC DEMAND

We now finalise our attempt to find amounts to produce of each item in a multi-level/multi-stage capacity-constrained production-inventory system in the most general of the cases considered. Below we introduce stochastic external demand to the continuous time case. This is an extension of Chapter 6 by adding stochastic properties to external demand and it represents the thick-line triangle of Table 1.1. We are now turning to the most general, but also most complicated case, and our treatment will therefore be limited to an outline of the procedures involved, and no numerical examples will be provided. The model is based on the assumption that external demand is stochastic. An example treated in Grubbström (1996) concerned demand being a renewal process made up of stochastic events separated by independent stochastic time intervals with a common given probability density function. In this chapter we need to modify our dynamic programming procedure in order to propose a solution to the non-zero lead time problem. The objective is to choose the best production plan maximising the expected net present value of the total cash flow associated with production and demand. However, since the problem now is stochastic, the plan chosen will be an optimal plan as seen from the initial point of time. The decisions computed, are based on maximising the expected NPV from the events taking place later on, not yet known, before the horizon T is reached. Therefore, in a practical case, only the first decision in the plan would be realised, the remaining decisions being part of the strategy determined by the calculations. Which future decisions that will be taken will depend on the realisation of the demand process and the consequences this and previous decisions have on the state at each point in time.

93

Here, we continue applying the combination of Laplace transforms and Input-Output Analysis.

7.1 Objective Function and Constraints In the model developed here, stochastic demand events are assumed to take place as known processes in continuous time. We state the following expression for the expectation of the Net Present Value of the payments concerned. This follows the deterministic model in Chapter 6. N

NPV = −∑ i =1

N

T

i =1

t =0

+ ∑ ri

(

∫

ni

⎛

∑⎜ c P j =1

⎝

i ij

M

+ K iν ij + ∑ wk hk′′i k =1

e ρτ i − 1

ρ

⎞ − ρt Pij ⎟ e ij ⎠

E ⎣⎡ Di (t ) − Bi (t ) ⎤⎦ e − ρ t dt − ri E [ Bi (T ) ] e − ρT =

) (

)

 − sB ⎤ ⎤ , = ⎡ − ( c + wH′′( τ − I) / s ) P + Kν + r E ⎡⎣ D ⎦ ⎦ s=ρ ⎣

(7.1)

where E[ ] is the expectation operator. The decision variables are the production vectors P which need be determined as a function of the state, and the setup vectors ν which are given, when the P are given (roughly speaking, ν = sgn(P ) ). Equation (7.1) can be looked upon as the net present value consequence of a realisation of the process. The sequence of vectors P , in general, will not have unique values at different points in time, since their realisation will depend on the prior stochastic development of the state. Instead, the optimal sequence will be proposed decisions to take as functions of what the state happens to be at a particular point in time. As before, there are two types of constraints involved in this problem. On the one hand, available inventory must be non-negative in order for the production plan P to be feasible. For any realisation, this can be written ⎧ (R (0) + (I − H′τ )P ( s )) ⎫ £ −1 ⎨ (7.2) ⎬≥ 0, s ⎩ ⎭

94

  always is satisfied. meaning that at least internal demand H′τP

Secondly, there is the set of capacity constraints. The demand for capacity is always internal ⎧ H′′( τ ( s ) − I)P ( s) ⎫ −1  £ −1 ⎨C ( s) − ( s ) − H′′τ ′( s )P ( s) ≥ 0 , ⎬=£ C s ⎩ ⎭

{

}

(7.3)

where τ ( s ) is the original diagonal lead time matrix having e ρτ i in its ith diagonal position, and where we have introduced the short notation τ′( s ) = ( τ ( s ) − I ) / s

(7.4)

for a modified diagonal lead time matrix τ′( s ) when assuming capacities to be used constantly throughout the lead time, rather than as impulses at the point of completion (as previously explained in Section 6.2).  including Our basic problem is to choose values of the components of P their timing properties tij , as functions of the state, such that the expectation of the future contribution to the objective function NPV in (7.1) is maximised subject to these two sets of constraints.

7.2 Dynamic Programming Solution Procedure As our point of departure, we introduce the state Q(t) as a time dependent set of variables defining the current situation at each point in time. As yet, we have not specified what, or how much information that is contained in Q(t). In the deterministic case, earlier treated (Sections 5.2 and 6.3), we defined Q(t) to be a sequence of past cumulative production vectors, but this definition will not suffice in this stochastic setting. For the moment, we simply assume the existence of a Q(t) containing a sufficient amount of information, so that an optimal production decision P(t) (and ν (t ) ) can be taken when Q(t) is known. 95

The state Q(t) will develop stochastically based on stochastic external demand D(t). The NPV function in (7.1) is an integral over time. It is therefore the sum of a set of contributions from intervals of the time scale. Consider a small interval [t, t + dt]. If the state, just prior to the decision at t, is Q(t), the contribution to the NPV may be written

ΔNPV(Q(t ), P(t , Q(t ))) ,

(7.5)

since it will depend on the state Q(t) and on the current decision P(t), which at t is to be chosen optimally as a function of t and Q(t), hence the notation P(t, Q(t)) for the second argument of ΔNPV . As a result of the decision P(t, Q(t)), Q(t) will change to Q(t+dt), but this new state also depends on how stochastic demand develops. We therefore need to have probabilities available for the state transition from Q(t) to Q(t+dt). Let these probabilities be written pQ ( t ), q ( Q(t ), P(t , Q(t )) )

(7.6)

where q is one of the opportunities that the new state will take, when given the old state Q(t). These opportunities we collect in the set Q (t + dt ) . If we now introduce E [ NPVt + dt | q ] for the expected contribution to the NPV from time (t + dt) onwards, if the new state is q and if the remaining sequence of decisions are taken optimally (knowing how they should be when given each future state), then the expected contribution to the NPV from t and onwards will be ΔNPV(Q(t ), P (t , Q(t ))) +

+

∫∫∫

pQ ( t ), q ( Q(t ), P (t , Q (t )) ) E [ NPVt + dt | q ] dq ,

q∈Q ( t + dt )

96

(7.7)

where the triple integral symbolically represents taking the expectation of the maximum future NPV over all possible developments of the state during the interval [t, t + dt]. Finally, let us introduce the notation P (Q(t )) for the set of available decisions P(t) when the state at t, i.e. Q(t), is known, and when available inventory and capacity constraints are taken into account appropriately. The problem at t is thus to choose an optimal P(t) from the set P (Q(t )) .

Hence, the recursive equation governing this optimisation, may be written E [ NPVt | Q(t )] =

= +

max

P ( t ,Q ( t ))∈P ( Q ( t ))

∫∫∫ Q

q∈

( t + dt )

⎡ ⎢ ΔNPV(Q(t ), P(t , Q(t ))) + ⎣

⎤ pQ (t ), q ( Q(t ), P(t , Q(t )) ) E [ NPVt + dt | q ] dq ⎥ . ⎥⎦

(7.8)

This is a differential equation determining the development of E [ NPVt | Q(t ) ] . If, for instance, the value of E [ NPVT | Q(T ) ] is known to be zero (since the process has ended there), in principle, the whole development of E [ NPVt | Q(t ) ] going backwards from T to t = 0 is given by the equation.

7.3 Interpretation of the State and Other Entities The immediate consequences from taking a decision P(t) at t as regards production, are easily found to be N M ⎛ ⎞ − ρt ⎛ e ρτ i − 1 ⎞ ΔNPVproduction = −∑ ⎜⎜ K iν i (t ) + ⎜ ci + ∑ wk hk′′i ⎟ Pi (t ) ⎟⎟ e dt , (7.9) ρ ⎠ i =1 ⎝ k =1 ⎝ ⎠

97

where Pi (t ) (and ν i (t ) ) includes a Dirac function at t, if a batch of the ith item is completed in this interval. Furthermore, we have the consequences from sales and backlogs which are generated by the influence of the state Q(t)

ΔNPVsales = ∑ ri ( Di (t ) − Bi (t ) ) e − ρ t dt . N

(7.10)

i =1

At the very end t = T, there might also be the additional lost sales term −ri E [ Bi (T )] e− ρT δ (t − T )dt . The term ΔNPV ( Q(t ), P ( t , Q(t ) ) ) in (7.8) will thus be ΔNPV ( Q(t ), P ( t , Q(t ) ) ) = ΔNPVproduction + ΔNPVsales .

(7.11)

Let us now examine the set of possible production decisions P ( Q(t ) ) . Production is limited by the availability of components, as expressed by the available inventory constraint (7.2). It is also limited by the need for capacity usage (7.3). The amount of information needed therefore goes back at most to the longest lead time prior to the point of decision, i.e. to t − τˆ , where τˆ , as previously, is defined by

τˆ = max τ i .

(7.12)

i

Therefore, Q(t) needs to contain available inventory information of the interval [t − τˆ, t ] . This requires information on cumulative production P and cumulative demand D during the interval. If Q(t) contains this information, it will suffice to determine all opportunities for the current production decision as expressed by P ( Q(t ) ) . We finally have the state transition probabilities pQ ( t ), q ( Q(t ), P ( t , Q(t ) ) ) . As regards production, it is obvious how the future cumulative production depends on the earlier sequence and on the current decision 98

(in the same way as in Chapters 5 and 6). Only specific combinations will provide an opportunity for a positive probability. However, as regards demand, the transition is dependent on what new demand that appears at t. The transition probabilities must therefore be computed from properties of the demand process. The opportunities for Q(t) to take on new values q in Q (t + dt ) , are also expressed by these

considerations.

7.4 Summary In this chapter we have attempted to extend our previous theory to the case of stochastic demand, when the processes take place within a continuous time framework and lead times are non zero. Our treatment has resulted in an outline for such a development, but it is clear that the theory has become so very complex and that the investigation is far from complete. In particular, the concept of the state Q in this stochastic situation needs a substantial amount of additional careful attention.

99

100

8

CAPACITY CONSTRAINTS IN A PAPER MILL (BILLERUD SKÄRBLACKA AB)

8.1 Introduction Skärblacka AB is one of four paper mills of the Billerud company. It is located in Skärblacka, Norrköping, Sweden. The mill was originally built in 1872, but the foundations for the modern mill were laid in the early 1960s. Today the mill comprises three pulp lines, four paper machines and a drying machine for market pulp. Production is focused on brown sack paper, white MG paper, and fluting. Having a large production capacity, the mill consumes huge resources of Wood: 3900 m3/24h Oil: 68 m3/24h Electricity 1200 MWh/24h Water 75000 m3/24h Truck loads 104/24h In Table 8.1 is shown the production capacity of the mill in 2004.

Product Sack Kraft paper MG Kraft paper Fluting Market pulp Number of employees

Quantity (tons) 150 000 88 000 90 000 80 000 720

Table 8.1. The production capacity of Billerud Skärblacka AB (2004) The company buys materials from the suppliers of wood. When the logs reach the mill they enter into the wood room. The bark is removed in a rotating drum. Then the logs are cut into chips and the chips are stored in

101

large silos or piles. The bark is used as fuel. The chips are then sent to a digester. In the pulp cooking process, the cellulose fibres in the wood chips must be parted from each other carefully. This takes place by cooking the chips under pressure together with chemicals. The cooking liquid, or white liquor, becomes black during this process. Around half of the wood becomes pulp. The remainder is dissolved in the black liquor and is used as biofuel in a recovery boiler. During subsequent washing and screening stages, the black liquor and chips that have not dissolved in the pulp are washed and screened in several stages to ensure that no impurities remain. The pulp then continues either to a bleaching station or straight to a paper machine if the product is unbleached. Bleaching is a process that produces a cleaner, whiter and more durable pulp. The process takes place in several stages and the chemicals used are oxygen, chlorine dioxide, hydrogen peroxide and caustic soda. The bleached cellulose fibres are now ready to become white paper. The cooking liquid, or black liquor, is first dried, and then burnt in the recovery boiler. This produces heat for creating steam and electricity, during which the chemicals form a solution at the bottom of the boiler. This solution is dissolved in water to produce green liquor. The green liquor is treated with lime and converted into new cooking liquor (white liquor), which can be returned to the pulp digester. This circulation of chemicals in different eco cycles is a key element in the environmental impact as well as for the economy of the mill as a whole. During paper production stages, cellulose fibres are mixed with water and chemicals, and ground together. This mixture (“stock”), is poured onto the wire of the paper machine where it forms a paper web. The web is then led through the paper machine through a system of filters and rollers, where the paper is dewatered, pressed and dried. At the end of the machine, the paper is wound onto massive reels.

102

Sawmill chips, Softwood, Hardwood

Wood Room Sulphate cooking 1 Washing Screening

Reject from Screening

Reject Handling

Oxygen Bleaching

Sulphate cooking 2

Semi-chemical Pulp Cooking

Washing

Defibration

Screening

Washing

Washing

Washing

Bought Fibre

Final Bleaching

PM 8 MG Kraft

PM 7 MG Kraft

TM 1 Bleached Pulp

PM 9 Sack Paper

PM 4 Fluting

Figure 8.1. The production flowchart of Billerud Skärblacka AB. PM 8, PM 7, PM 9, PM 4 are paper machines, and TM 1 is a drying machine for market pulp. Depending on customer demand, some of the paper is coated in special coating machines. By adding a thin coat of white colouring, the paper becomes smoother and better sealed and thus easier to print on.

103

Winding and packaging are the finishing stages. In the winding stage, the large paper reels (popes) are cut into smaller sizes, and in the packaging stage they are packed to protect the products during storage and transport to the customers. In addition to measures carried out inside the mill to reduce emissions from the various production stages, waste water is also treated externally. The wastewater first enters sedimentation ponds, where particles (mainly wood fibres) are separated from the water. Then the water is treated in a biological process, in which micro organisms break down pollutants.

8.2 Production Planning and Capacity Constraint Problems. At the mill, production takes place 24 hours a day, every day of the year. Machinery and environmental protection equipment are fine-tuned continuously to meet requirements concerning product quality and the environment. There are several constraints in the mill. Here, we shall focus mainly on production capacity constraints. The pulp cooking equipment always runs at 100% capacity. With a wide range of paper products, the production planner copes with several set-up selections at the bleaching stage and at paper machines. Depending on customers’ demand, there are several different kinds of products according to bleaching grade and extensible (cf Table 8.2) grades. The product must be designed to fulfil the requirements of a multitude of industries, materials, filling machines, climatic conditions and market exposure. The sack paper, for instance, is classified according to some special indices such as Table 8.2 indicates. The fact that capacities are fully utilised corresponds to strict equalities in the relevant rows of the capacity constraint inequalities (such as in (6.3)):

{

}

 ( s ) − H′τ ( s )P ( s ) ≥ 0 . £ −1 C

(8.1)

104

White and Brown grades

Stretch MD

TEA index geom.

Tear index geom.

Printability

Runability at Stiffness at converting filling

Natural grades White Performance N

••

•••

••••

••

•••••

•••••

Brown Performance N

••

•••

••••

•

•••••

•••••

White NK

••

•••

••••

••

•••••

•••••

Duo white

••

•

••

•••

••••

••••

Triple white

••

•

••

•••

••••

••••

Print

••

••

•

••••

•••

•••

GlossPrint

•

•

•

•••••

••

••

White Performance SE

••••

•••••

••••

••

••••

••••

Brown Performance SE

••••

•••••

••••

•

••••

••••

White SQ

••••

••••

••••

••

••••

••••

White XZ

••••

••••

••••

••

••••

••••

Semi-extensible grades

Table 8.2. Characteristics of sack paper for open mouth sacks. Explanations to Terminology used in Table 8.2 Bendtsen ml/min: A measure of surface roughness. Roughness significantly affects the printing quality, lamination and other demanding surface treatment Porosity/air resistance, Gurley seconds: Air resistance is a measurement of the time taken for 100ml of air, under constant pressure, to pass through a specified area of a paper sheet. Short time signifies a highly porous paper. TEA (Tensile Energy Absorption), J/m2: the most important sack paper strength property. This is verified by the correlation between TEA and drop tests. When a sack is dropped, the contents will move when hitting the floor. This movement causes strain on the sack wall. To withstand this strain, the TEA should be high. The energy will then be absorbed by a combination of the tensile strength and the stretch in the paper. Tensile strength, kN/m: The tensile strength is the maximum force that the paper is able to withstand without breaking. Tensile strength is one parameter in the measurement of TEA. Stretch, %: the elongation of the paper extended to rupture.

105

Production in these paper machines is planned depending on customer orders every week (short-term planning) with the aim to minimise the inventory of finish products. In the production planning department, there are two main factors taken into account, in order to hold production cost down.

Tons 350 300 250 PM 9

200

PM 8

150

PM 7

100

PM 4

50 0 Jan

Feb

Mar

Apr

May June July

Aug

Sep

Oct

Nov

Dec

Figure 8.2. Loss of paper quantity due to setup time.

Hours 30 25 20

PM 9 PM 8

15

PM 7 10

PM 4

5 0 Jan

Feb

Mar

Apr

May June July

Aug

Sep

Oct

Nov

Dec

Figure 8.3. Loss of machine time due to setup time. 106

On the one hand, there are setup costs due to setup times. When changing from one kind of product to another kind, there is always some loss at the setup stage. Therefore, to lower the production losses (shown in Figures 8.2 and 8.3), the production planner aims at minimising the frequency of setup changes. Apart from these consequences, there are trimming losses. During the packing stage, this type of loss is incurred, when the orders do not match the pope’s dimension, for instance as illustrated in Figure 8.4. The planner tries several different combinations until he is satisfied with the resulting smaller loss.

loss

Order A

Order B

Figure 8.4. Pope Cutting.

The average total loss per annum because of setup and packing at machines PM 7, PM 8, PM 9 is shown in Table 8.3. Loss at setup (tons)

Loss at packing (tons)

Total

Loss percentage (%)

PM 7

2842.2

3041.6

5883.8

11.2

PM 8

1813.2

2519.3

4332.5

9.0

PM9

1270.1

1506.9

2777.0

9.6

Table 8.3. Average total loss per annum in paper machines PM7, PM8, PM9. 107

The company always attempts to satisfy all customer demand. In the short term, sometimes the demand is higher than production capacity. The sales department must discuss with customers before accepting an order. The production planning department has to make sure that all machines run as close to 100% capacity as possible. Following the main production flow, various capacity limitations are revealed: •

The storage space for wood is limited. As a total, it is possible to store 80,000 cubic metres of wood, which are distributed according to round timber, purchased chips, and chips made from round timber, which then are stored in chip silos. The normal volume of wood is around 50 % of this maximum limitation. As a whole, around 1,500,000 cubic metres of wood is consumed per annum. Hence, the maximum storage corresponds to approximately three weeks’ requirements and the normal storage to some 1.5 weeks’ requirements. The main limitations are due to the area of the wood yard and to the size of the chip silos.

•

In the wood room, there are essentially no capacity limitations. This stage is currently run according to a continuous two-shift schedule. Occasionally, when running during a third night shift, the noise level of this stage could limit capacity according to environmental regulations. Currently, there is no need for a night shift.

•

Externally purchased chemicals, energy, water and other factor inputs are never envisaged as subject to limitations.

•

The sulphate cooking process is basically a chemical/energy process, which affects the succeeding production stages. If this process shows a lower performance, it will have an immediate effect on the maximum capacity of the paper machines, since both energy (steam) and the fibre raw materials are produced in the sulphate process. Reasons for a lower performance would be related to occasional technical problems, such as sedimentation,

108

breakdown, or similar disturbances. On occasion, the sulphate cooking stage needs to be run at a reduced rate due to environmental considerations, for instance if the threshold values for emissions have been reached. •

In the paper machines, the number of different products (according to different recipes and grammage (basis weight) are around 50 per machine. On top of this, there are the dimensions of width, diameter and reel, which make the diversification extremely large. The latter kind of customisation takes place at the packing stage where the popes are cut, and this only indirectly affects the paper machines. The winding machine might limit the overall capacity, when the frequency of changes in paper variants becomes high. Then, this might also create a storage limitation for the popes between the paper machine and the winding machine. Such an occurrence, however, is extremely rare.

•

In the vast majority of cases, a certain product variant will only be manufactured in a predefined paper machine. There are rare exceptions, when an order might be run in either of two paper machines, but these cases are negligible.

•

The storage space of the end product inventory is limited. For sack paper, the area is around 2,700 square metres and for white MG paper around 3,500 square metres. The internal transportation service within the end product inventory (using fork trucks) also has a limited capacity. This service unit is common for all types of products. If the storage area becomes over full, there are options to rent additional storage space, for instance in the harbour of Norrköping, or elsewhere.

•

A final capacity limitation concerns the delivery services from the mill. These take place either by rail, or by truck.

109

8.3 Some Observations and Suggestions When having investigated the types of capacity constraints occurring in practice in a paper mill, they may be classified into essentially two categories: • •

Limitations in the production process, constraining the flow of products per time unit, Limitations in storage facilities, constraining the volume of available inventory.

In our theory developed in previous chapters, only the former type of restriction has been applied when solving related problems. Therefore, there appears to be a need for adding opportunities for additional constraints in the form of upper bounds for inventory. This may relatively easily be done by introducing supplementary inequalities of the type:

{ }

 ≤ C (t ) , £ −1 R R

(8.2)

where CR (t) captures the upper limitations for available inventory over time. Furthermore, it appears essential to develop the theory in the direction of including setup times. These times have been neglected earlier, and their existence has only had an indirect effect through the economic parameters by which a setup cost would be subtracted from the NPV at the time of a setup, i.e. by Kν (t )e − ρ t , where K is the row vector of setup costs and ν (t ) the setup vector at time t (a column vector). Hence, the relation between ν (t ) and available capacity C(t) need be investigated further. In the practical choices made available to the production planning department, little attention is given to the economic and monetary consequences of which operational decisions that are taken. Behind the 110

vast majority of decisions, attention is directed mainly towards volume consequences, rather than economic consequences. The quantity of damaged and useless paper is in the forefront of awareness. From our theoretical point of departure, one might wish to estimate the value of losses more accurately. Due to the multiplicity of products having different prices, the quantity measure alone would not reflect the loss accurately. Also, there are products that make a higher profit than others, such as medical paper. Should priorities be given to the high-profit grades when forming the product plan? A similar observation might be made concerning the competition of storage space among different products. In general, it might be suggested that more attention might be given to monetary consequences of operational decisions concerning capacity utilisation.

111

112

9

CONCLUSIONS AND SUGGESTIONS FOR FURTHER STUDIES

The aim of this dissertation has been to provide suggestions for stating and solving the capacitated multi-level multi-period production planning problem. In this final chapter, we summarise our results from Chapter 1 to Chapter 8. We also suggest some further research directions. All through our developments, we have relied upon the scientific base of MRP theory, involving the combination of Input-Output Analysis and Laplace transforms.

9.1 Summary and Conclusions Throughout the dissertation, we have employed the Laplace transform (or z-transform) and Input-Output Analysis as tools for applying MRP theory to the capacitated problems we have formulated. In essentially all cases, the Net Present Value has been stated as the objective to maximise. This choice has been based on the opinion argued in several articles that such an approach must be superior to traditional average cost considerations, the latter overwhelmingly appearing in earlier literature. In Chapter 3, we analysed the previously developed fundamental equations (available inventory, total inventory and backlogs) of MRP Theory, when the basic ordering policies Lot-For-Lot (L4L), Fixed Order Quantity (FOQ) and Fixed Period Requirements (FPR) were to be applied. Having presented a brief overview of the fundamental equations of MRP theory, this was followed by deriving the basic properties of the production plan for the three ordering policies in relation to this theory. For the L4L policy, we found an explicit closed-form Laplace transform expression for the time development of production, when given external demand, whereas for the other two policies, the results were more implicit. The optimal FOQ and optimal FPR were also determined for the case that external demand was stochastic. When leaving the L4L policy, it was shown that relevant expressions are possible to derive, but they become considerably more complicated. 113

All through Chapter 4 until Chapter 7, we have been treating capacitated multi-level, multi-stage production planning problems. In Chapter 4, a four-procedure heuristic method was suggested for the non-zero lead time problem in the discrete-time framework. Numerical examples illustrated how the NPV increases, when available capacity was allowed to increase. However, the increase took place with a small degressive element showing "diminishing returns to scale". This phenomenon repeated itself in the numerical examples treated in subsequent chapters. Instead of using a heuristic, in the three chapters following, a dynamic programming procedure was applied in order to find the optimal solution of the capacitated multi-level multi-stage production planning problem. This development followed the diagram depicted in Table 1.1. In Chapter 5, the model treated concerned external demand being deterministic in a discrete time setting. In order to apply dynamic programming, we formulated the state confronting decisions in each period to be a set of historical vectors of cumulative production, which were collected in matrices Q , collecting the necessary information for taking optimal future decisions. The array Q in period n, i.e. Q n , was then defined as a sequence of τˆ previous cumulative production vectors where τˆ was the maximum of all production lead times. In the continuous-time model of Chapter 6 instead, there was not necessarily the same number of earlier decisions to account for during the given maximum lead time for different transitions. Some decisions, on occasion, might be closer in time than at other times. However, a list of the cumulative production vectors representing decisions during the maximum interval τˆ would always suffice for providing the necessary amount of information. By choosing a sufficiently large but finite number nˆ of earlier cumulative production vectors as the state description, according to our findings, this would suffice for our purposes. In Chapter 7, we have made an attempt to extend our previous theory to the case of stochastic demand, when the processes take place within a continuous time framework and lead times are non-zero. There, we presented an outline for such a development. It was shown that the theory became increasingly complex. Our results from this investigation 114

cannot be considered other than far from complete. In particular, the concept of the state Q in this stochastic situation still will need a substantial amount of additional attention. When computing results from numerical examples in Chapters 5 and 6, the NPV was shown to behave as one might have expected intuitively, namely that there is a close to linear relation between available capacity and NPV. As mentioned above, this relation was perturbed by a small degressive element showing diminishing returns to scale. When introducing non-zero lead times into the capacitated lot-sizing problem, the complexity of the model has been shown to grow dramatically. The theoretical analysis was still manageable to cope with, when choosing an appropriate definition of the state space. We might therefore conclude that an embryo for the existence of a non-zero lead time extension of MRP theory in both discrete time and in continuous time has been established. Results from a study of capacity constraints in a paper mill were presented in Chapter 8. In the practical scenario, a great number of restrictions, many of which were possible to interpret as capacity constraints, proved to be present. The major capacity constraints could be classified into two categories: (i) limitations in the production process, constraining the flow of products per time unit, and (ii) limitations in storage facilities, constraining the volumes of available inventory, such as the limited area of the wood yard. We were also given attention to the importance of capacity losses due to setup frequency and trimming. These observations have also provided ideas for further theoretical extensions of MRP theory.

9.2 Suggestions for Further Studies Relaxing Assumptions During our theoretical developments, we have been forced to make assumptions of various kinds in order to keep complexity down for the sake of managing the problems treated. When addressing extensions of current theory, the first natural choice is to study consequences from

115

relaxing restrictions being based on assumptions. A few of these limitations are listed as follows: Non-Constant Lead Times Lead times have been considered constant throughout our developments. This is in line with Material Requirements Planning methodology from its start. However, in practical situations the true lead time is dependent on the current work load, i.e. on current capacity utilisation. Therefore, lead times also may be considered as consequences of the production plan, and not only the plan a consequence of the given lead times. The way in which this type of interaction takes place is yet to be analysed. Stochastic Elements in Lead Times Lead times are also subject to stochastic influences because of machine breakdowns etc. Extensions of the theory to possible variations in the lead time matrix τ , would be an interesting topic to develop. Variations in Bill-Of-Materials Also the given constant properties of the Bill-Of-Materials (the “technical coefficients”), captured in the various appearances of the matrix H, have been taken as a preset starting point, when stating the capacitated problem. Due to technical development in the longer run, or perturbations such as quality variation and scrap in the shorter run, the elements of H are not necessarily constant. Consequences of the uncertainty in H might be an item for further attention. Remanufacturing and Feedback An increasingly important feature in modern economies is the question of the reuse of resources, including remanufacturing and reprocessing, often called “reverse logistics”. When examining the physical flows involved in remanufacturing, there is a natural element of feedback. This corresponds to product structures with some ingredient disobeying the strict assembly type of product structure usually assumed in MRP. Consequences of non-triangular input matrices H constitute a further line of investigation. Here, we also might study pure disassembly structures, which come close to the arborescent type of product structure.

116

Setup Times The case study in Chapter 8 revealed that the finite setup times were of obvious significance, when taking operational decisions. Inclusion of setup times, and not only setup costs, is an item of additional interest. Storage Limitations Also this study showed, that capacities not only limited flows, but also stock. Developing consequences of upper limits for storage, etc., would comprise a natural extension to current MRP theory. Methodological Developments Although we have presented an outline for the case of stochastic external demand in Chapter 7, this treatment is evidently far from being conclusive. In particular, more attention is needed to investigate the properties of the state Q in this general case, as well as the description of how one state leads to a succeeding state and the stochastic properties of such transitions. Developing suitable numerical examples would be an important piece of work within this line of research.

117

118

REFERENCES Alain, G. (1999), A Primal-Dual Approach for Capacity-constrained Production Planning with Variable and Fixed Costs, Computer & Industrial Engineering, Vol. 37, 93-96. Albritton, M., Shapiro, A., and Spearman M. (2000), Solve the Problem with Two variants of Monte Carlo. Stochastic Programming E-Print Series. Andersson, L. E. and Grubbström, R. W. (1994), Asymptotic Behaviour of a Stochastic Multi-Period Inventory Process with Planned Production, Working Paper WP-210, Department of Production Economics, Linköping Institute of Technology. Aseltine, J. A. (1958), Transform Method in Linear System Analysis, McGraw-Hill, New York. Axsäter, S. and Rosling, K. (1994), Multi-Level Production-Inventory Control: Material Requirement Planning or Reorder Point Policies? European Journal of Operational Research, Vol. 75, 405-412. Axsäter, S., Schneeweiss Ch. and Silver E. (1986), Multi-Stage Production Planning and Inventory Control, Springer-Verlag, Berlin. Bagchi, U., Hayya, J.C. and Ord, J. K. (1983), The Hermite Distribution as a Model of Demand During Lead Time for Slow Moving Items, Decision Sciences, Vol. 14, 447-466. Barbarosoglu G. and Özdamar, L. (2000), Analysis of Solution SpaceDependent Performance of Simulated Annealing: the Case of the MultiLevel Capacitated Lot Sizing Problem, Computer & Operations Research Vol. 27, 895-903. Bogataj, M. (1999), Inventory Allocation and Customer Travelling Problem in Spatial Duopoly, International Journal of Production Economics, Vol. 59, 271-279.

119

Bogataj, M. and Bogataj, L. (2004), The Problems of Optimal Additional Investments in Reduction of Delays in Value Chain Analyzed in Frequency Domain, Informatizacija transportno logističnega grozda, (Mathematical economics, operational reseach and logistics), Serial no 4. University of Ljubljana: Faculty of Economics. Bonney, M. C. and Popplewell, K. (1988), Design of Production Control Systems: Choice of System Structure and Systems Implementation Sequence, Engineering Costs and Production Economics, Vol. 15, 169173. Brander, P., Levén, E. and Segerstedt, A. (2005), Lot Sizes In a Capacity Constrained Facility – A Simulation Study of Stationary Stochastic Demand, International Journal of Production Economics, Vol. 93-94, 375-386. Buck, J. R. and Hill, T. W. (1971), Laplace transforms for the Economic Analysis of Deterministic Problems in Engineering, The Engineering Economist, Vol. 16, 247-263. Carlson, R. C., Jucker, J. V. and Kropp D. H. (1979), Less Nervous MRP Systems: A Dynamic Economic Lot-Sizing Approach, Management Science, Vol. 25, No 8, pp.129-146. Chen, J. C., Chen, C., Lin, C. J. and Rau, H. (2005), Capacity Planning with Capability for Multiple Semiconductor Manufacturing Fabs, Computer & Industrial Engineering, Vol. 38, 709-732. Choi, S. and Enns, S. T. (2004), Multi-Product Capacity-Constrained Lot-Sizing with Economic Objectives, International Journal of Production Economics, Vol. 91, 47-62. Churchill, R. V. (1958), Operational Mathematics, McGraw-Hill, New York. Churchill, R. V. (1960), Complex Variables and Applications, McGrawHill, New York.

120

Clark, A.R. (2003), Optimization Approximations for Capacity Constrained Material Requirements Planning, International Journal of Production Economics, Vol. 84, 115-131. Erol, M. (1999), Analysis of Production Planning in Case of the Random Demand, Computer & Industrial Engineering, Vol. 37, 21-25. Feller, W. (1960), An Introduction to Probability Theory and Its Applications, Vol. I, Second Edition, John Wiley & Sons, New York. Feller, W. (1971), An Introduction to Probability Theory and Its Applications, Vol. II, Second Edition, John Wiley & Sons, New York, p. 439. Foster, T. S. (2002), Material Requirements Planning Course. http://www.freequality.org/. França, P. M., Armentano, V. A., Berretta, R. E., and Clark, A.R. (1997). A Heuristic Method for Lot-Sizing In Multi-Stage Systems, Computers & Operations Research, Vol. 24, 861-874. Grubbström, R. W. (1967), On the Application of the Laplace Transform to Certain Economic Problems, Management Science, Vol. 13, 558-567. Grubbström, R. W. (1980), A Principle for Determining the Correct Capital Costs of Work-In-Progress and Inventory, International Journal of Production Research, Vol. 18, No 2, 259-271. Grubbström, R. W. (1991), A Closed-Form Expression for the Net Present Value of a Time-Power Cash Flow Function, Managerial and Decision Economics, Vol. 12, No 5, 305-316. Grubbström, R. W. (1996), Stochastic Properties of a ProductionInventory Process with Planned Production Using Transform Methodology, International Journal of Production Economics, Vol. 45, 407-419.

121

Grubbström, R. W. (1998a), A Net Present Value Approach to Safety Stocks in a Planned Production, International Journal of Production Economics, Vol. 56-57, 213-229. Grubbström, R. W. (1998b), The Fundamental Equations of MRP Theory in Discrete Time, Working Paper WP-254, Department of Production Economics, Linköping Institute of Technology, December. Grubbström, R. W. (1999a), A Net Present Value Approach to Safety Stocks in a Multi-Level MRP System, International Journal of Production Economics, Vol. 59, 361-375. Grubbström, R. W. (1999b), An Optimal Forward Dynamic Lot-sizing Policy for the NPV and Average Cost Cases in Continuous Time, in Hillery, M. T. and Lewis, H. J., (Eds), The 15th International Conference on Production Research . ICPR-15 Manufacturing for a Global Market, Limerick, Ireland, Vol. 1, 381-384. Grubbström, R. W. and Huynh, Th. (2002), The Stochastic MultiLevel/Multi-Stage Capacity-Constrained Production-Inventory System Extended with Non-Zero Lead Times, Paper presented at the Twelfth International Symposium on Inventories, Budapest, August 19-24. Working Paper WP-306, Dept of Production Economics, Linköping Institute of Technology. Grubbström, R. W. and Huynh, Th. (2005a), Extension of Multi-Level, Multi-Stage Capacity-Constrained Production-Inventory Systems with Non-Zero Lead Times to Continuous Time, Proceedings, 18th International Conference on Production Research, Salerno, Italy, 31st July-4th August, 2005. Grubbström, R. W. and Huynh, Th. (2005b), Analysis of Standard Ordering Policies within the Framework of MRP Theory, Proceedings, 18th International Conference on Production Research, Salerno, Italy, 31st July-4th August, 2005. International Journal of Production Research, forthcoming. Grubbström, R. W. and Huynh, Th. (2006). Multi-Level, Multi-Stage Capacity-Constrained Production-Inventory Systems in Discrete Time 122

with Non-Zero Lead Times using MRP Theory, International Journal of Production Economics, Vol. 101, 53-62. Grubbström, R. W. and Jiang, Y. (1990), A Survey and Analysis of the Application of the Laplace Transform to Present Value Problems, Revista di matematica per le scienze economiche e sociale, Vol. 12, 47362. Grubbström, R. W. and Kingsman, B. G. (2004). Ordering and Inventory Policies for Step Changes in the Unit Item Cost: a Discounted Cash Flow Approach, Management Science, Vol. 50, pp. 253-267. Grubbström, R. W. and Lundquist, J. (1977), The Axsäter Integrated Production-Inventory Sytem Interpreted in Terms of the Theory of Relatively Closed Systems, Journal of Cybernetics, Vol. 7, 49-67. Grubbström, R. W., and Molinder, A. (1994), Further Theoretical Considerations on the Relationship Between MRP, Input-Output Analysis And Multi-Echelon Inventory Systems, International Journal of Production Economics, Vol. 35, 299-311. Grubbström, R. W., Ovrin, P. (1992), Intertemporal generalization of the relationship between material requirements planning and input-output analysis, International Journal of Production Economics, Vol. 26, 311-318. Grubbström, R. W., Tang, O. (1997), Early Writings Related to the Topics of MRP and Input-Output Analysis, in Bogataj, L., Grubbström, R. W. and Bogataj, M. (Eds), Input-Output Analysis and Laplace Transforms in Material Requirements Planning, Faculty of Maritime Studies and Transport, University of Ljubljana, Portoroz, Slovenia, 3344. Grubbström, R. W., Tang, O. (2000), An overview of input-output analysis applied to production-inventory systems, Economic Systems Research, Vol. 12, 3-25. Grubbström, R. W. and Wang, Z. (1999), Introducing Capacity Limitations into Multi-Level, Multi-Stage Production-Inventory Systems 123

Applying the Input-Output/Laplace Transform Approach, in Hillery, M. T., Lewis, H. J., (Eds), The 15th International Conference on Production Research . ICPR-15 Manufacturing for a Global Market, Limerick, Ireland, August 9-13, 435-438. Grubbström, R. W. and Wang, Z. (2000a), Modelling capacityconstrained production-inventory systems: A Review, Pre-Prints, Proceedings of the Eleventh International Working Seminar on Production Economics, Igls/Innsbruck, Austria, Vol. 1, 95-105. Grubbström, R. W. and Wang, Z. (2000b), Introducing Capacity Limitations into Multi-Level, Multi-Stage Production-Inventory Systems Applying the Input Output/Laplace Transform Approach, International Journal of Production Research, Vol. 38, No 17, 4227-4234. Grubbström, R. W. and Wang, Z. (2003), A Stochastic Model of MultiLevel/Multi-Stage Capacity-Constrained Production-Inventory Systems, International Journal of Production Economics, Vol. 81-82, 483-494. Hadley, G. and Whitin, T. M. (1963), Analysis of Inventory Systems, Prentice-Hall, Englewood Cliffs. Horvat, L. and Bogataj, L. (1996), Game Theory Aspects of MRP, InputOutput and Multi-Echelon Inventory Systems, Pre-Prints, Ninth International Working Seminar on Production Economics, Vol. 3, Igls/Innsbruck, 1-12. Huynh, Th. (2006), Multi-Level, Multi-Stage Capacity-Constrained Production-Inventory Systems with Non-Zero Lead Times In Continuous Time and with Stochastic Demand, Pre-Prints, Fourteenth International Working Seminar on Production Economics, Vol. 4, Innsbruck. Iida, T. (2002), A Non-stationary Periodic Review Production-Inventory Model with Uncertain Production Capacity and Uncertain Demand, European Journal of Operational Research, Vol. 140, 670-683. Ip, W. H., Li., Y., Man, K. F., and Tang, K. S. (2000), Multi-Product Planning and Scheduling Using Genetic Algorithm Approach, Computer & Industrial Engineering, Vol. 38, 283-296. 124

Jodlbauer, H. (2004). An Approach for Integrated Scheduling and Lotsizing, European Journal of Operational Research, in press. Jolayemi, J. K. and Olorunniwo, F. O. (2004), A Deterministic Model for Planning Production Quantities in a Multi-Plant, Multi-Warehouse Environment with Extensible Capacities, International Journal of Production Economics, Vol. 87, 99-113. Kern, G. M. and Wei, J. C. (1996), Master Production Rescheduling Policy in Capacity Constrained Just-In-time Make-To-Stock Environments, Decision Sciences, Vol. 27, No 2, 365-387. Lin, N. P. and Krajewski, L. J. (1992), A Model for Master Production Scheduling in Uncertain Environments, Decision Sciences, Vol. 23, 839861. Maes, J., McClain, J. O. and Van Wassenhove, L. N. (1991), MultiLevel Capacitated Lot Sizing Complexity and LP-Based Heuristics, European Journal of Operational Research, Vol. 53, 131-148. Miller, R. E. and Blair, P. D. (1985), Input-Output Analysis: Foundations and Extensions, Prentice-Hall, Englewood Cliffs. Molinder, A. (1995), Material Requirements Planning Employing, InputOutput Analysis and Laplace Transforms, PROFIL 14, ProductionEconomic Research in Linköping, Linköping. Mula, J., Poler, R. and Garcia, J.P. (2006), MRP with Flexible Constraints: A Fuzzy Mathematical Programming Approach, Fuzzy Sets and Systems, Vol. 157 (2006), 74-97. Oden, H. W., Langenwalter, G. A. and Lucier, R. A. (1993), Handbook of Material & Capacity Requirements Planning, McGraw-Hill, New York. Orlicky, J. (1975), Material requirement planning, McGraw-Hill, Inc., New York.

125

Peterson, R. and Silver, E. A. (1979), Decision Systems for Inventory Management and Production Planning, John Wiley & Sons, New York. Plossl, G. W. (1985), Production and Inventory Control: Principles and Techniques, Second Edition, Prentice-Hall, Englewood Cliffs. Pongcharoen, P., Hicks, C. and Braiden, P. M. (2004), The Development of Genetic Algorithms for the Finite Capacity Scheduling of Complex Products, with Multiple levels of Product Structure, European Journal of Operational Research, Vol. 152, 215-225. Ross, S. M. (1993), Introduction to Probability Models, Fifth Edition Academic Press, inc., London. Segerstedt, A. (1995). Multi-Level Production and Inventory Control Problems Related to MRP and Cover-Time Planning, PROFIL 13, Production-Economic Research in Linköping, Linköping. Silver, E. D., Pyke, D. And Peterson, R. (1998), Inventory Management and Production Planning and Scheduling, Third Edition, John Wiley & Sons, New York. Sox, C. R. and Muckstadt, J. A. (1996). Multi-item, multi-period production planning with uncertain demand, IIE Transactions, Vol. 28, 891-900. Spiegel, M. R. (1965), Laplace Transforms, McGraw-Hill, New York. Spitz, A. E. (1972), Production Planning, Aurebach, Princeton. Tang, O. (2000), Planning and Replanning within the Material Requirements Planning Environments – A Transform Approach, PROFIL 16, Production-Economic Research in Linköping, Linköping. Tempelmeier, H. and Helber, S. (1994), A Heuristic for Dynamic MultiItem Multi-Level Capacitated Lot-Sizing for General Product Structures, European Journal of Operational Research, Vol. 75, 296-311.

126

Teunter, R. (2005), A Note On “Khouja and Park, Optimal Lot Sizing Under Continuous Price Decrease, Omega 31 (2003)”, Omega, Vol. 33, 467-471. Van der Laan, E. (2003), An NPV and AC Analysis of a Stochastic Inventory System with Joint Manufacturing and Remanufacturing. International Journal of Production Economics, Vol. 81-82, 317-331. Özdamar, L. and Barbarosoglu, G. (2000), An Integrated Lagrangean Relaxation-Simulated Annealing Approach to the Multi-Level MultiItem Capacitated Lot Sizing Problem, International Journal of Production Economics, Vol. 68, 319-331. Wang, Z. (2001), Capacity-Constrained Production-Inventory Systems Using Laplace Transforms and Input-Output Analysis. Linköping Studies in Science and Technology, Licentiate Thesis No 864, Linköping 2001. Wang, Z. (2004), Capacity-Constrained Production-Inventory Systems: Modelling and Analysis in Both a Traditional and an E-Business Context. Linköping Studies in Science and Technology, Dissertations No 889. Winston, W. L. (1995), Introduction to Mathematical Programming, Second Edition, Duxbury, California. Whybark, D. C. and Williams, J. G. (1976), Material Requirements Planning under Uncertainty, Decision Sciences, Vol. 7, 595-606. Yin, K. K., Liu, H. and Yin, G. G. (2003), Stochastic Models and Numerical Solutions for Production Planning with Applications to the Paper Industry, Computer and Chemical Engineering, Vol. 27, 16931706. Yan, H. (2000), Hierarchical Stochastic Production Planning for Flexible Automation Workshops, Computer & Industrial Engineering, Vol. 38, 435-455.

127

Xie, J. and Dong, J. (2002), Heuristic Genetic Algorithms for General Capacitated Lot-Sizing Problems, Computers & Mathematics with Applications, Vol. 44, 263-276.

128