Hierarchical decision making in production and repair/replacement planning with imperfect repairs under uncertainties

In this paper, we analyse an optimal production, repair and replacement problem for a manufacturing system subject to random machine breakdowns. The system produces parts, and upon machine breakdown, either an imperfect repair is undertaken or the machine is replaced with a new identical one. The decision variables of the system are the production rate and the repair/replacement policy. The objective of the control problem is to find decision variables that minimize total incurred costs over an infinite planning horizon. Firstly, a hierarchical decision making approach, based on a semi-Markov decision model (SMDM), is used to determine the optimal repair and replacement policy. Secondly, the production rate is determined, given the obtained repair and replacement policy. Optimality conditions are given and numerical methods are used to solve them and to determine the control policy. We show that the number of parts to hold in inventory in order to hedge against breakdowns must be readjusted to a higher level as the number of breakdowns increases or as the machine ages. We go from the traditional policy with only one high threshold level to a policy with several threshold levels, which depend on the number of breakdowns. Numerical examples and sensitivity analyses are presented to illustrate the usefulness of the proposed approach.     

A rolling horizon approach for disruption management of railway rolling stock

This paper deals with real-time disruption management of rolling stock in passenger railway transportation. We describe a generic framework for dealing with disruptions of railway rolling stock schedules. The framework is presented as an online combinatorial decision problem, where the uncertainty of a disruption is modeled by a sequence of information updates. To decompose the problem and to reduce the computation time, we propose a rolling horizon approach: rolling stock decisions are only considered if they are within a certain time horizon from the time of rescheduling. The schedules are then revised as time progresses and new information becomes available. We extend an existing model for rolling stock scheduling to the specific requirements of the real-time situation, and we apply it in the rolling horizon framework. We perform computational tests on instances constructed from real-life cases of Netherlands Railways (NS), the main operator of passenger trains in the Netherlands. We explore the consequences of different settings of the approach for the trade-off between solution quality and computation time.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities

We consider a production model with two facilities sharing a resource during a time horizon consisting of a number of time periods. Cumulative production levels at the ends of consecutive periods are linked with constraints of a general form. This allows us to give different interpretations related to scheduling and input–output analysis. The model may arise either separately or in the structure of more general production models. In both cases it is reasonable to find an optimal or near-optimal distribution of resources between these two facilities. This helps either to develop a new production plan or to improve an existing one. The problem in question is NP-hard. We show that our approach leads to fully polynomial time approximation schemes (FPTASs).     

Timetabling of sorting slots in a logistic warehouse

We study a problem that occurs at the end of a logistic stream in a warehouse and which concerns the timetabling of the sorting slots that are used to accommodate the prepared orders before they are dispatched. We consider a set of orders to be prepared in a certain number of preparation shops over a given time horizon. Each order is associated with the truck that will transport it to the customer. A sorting slot is an accumulation area where processed orders wait to be loaded onto a truck. For a given truck a known number of sorting slots is needed from the time the first order for this truck begins to be prepared, right up until the truck’s scheduled departure time. Since several orders destined for different trucks are processed simultaneously, and since the number of sorting slots is limited, the timetabling of these resources is necessary to ensure that all orders can be processed over the considered time horizon. In this paper we describe the general industrial context of the problem and we formalize it. We state that some particular cases of the problem are polynomially solvable while the general problem is NP-complete. We then propose optimization methods for solving the problem.     

A Multi-Period Renewal equipment problem

This paper looks at a Multi-Period Renewal equipment problem (MPR). It is inspired by a specific real-life situation where a set of hardware items is to be managed and their replacement dates determined, given a budget over a time horizon comprising a set of periods. The particular characteristic of this problem is the possibility of carrying forward any unused budget from one period to the next, which corresponds to the multi-periodicity aspect in the model. We begin with the industrial context and deduce the corresponding knapsack model that is the subject of this paper. Links to certain variants of the knapsack problem are next examined. We provide a study of complexity of the problem, for some of its special cases, and for its continuous relaxation. In particular, it is established that its continuous relaxation and a special case can be solved in (strongly) polynomial time, that three other special cases can be solved in pseudo-polynomial time, while the problem itself is strongly NP-hard when the number of periods is unbounded. Next, two heuristics are proposed for solving the MPR problem. Experimental results and comparisons with the Martello&Toth and Dantzig heuristics, adapted to our problem, are provided.     

Solving the Unit Commitment Problem by a Unit Decommitment Method

In this paper, we present a unified decommitment method to solve the unit commitment problem. This method starts with a solution having all available units online at all hours in the planning horizon and determines an optimal strategy for decommitting units one at a time. We show that the proposed method may be viewed as an approximate implementation of the Lagrangian relaxation approach and that the number of iterations is bounded by the number of units. Numerical tests suggest that the proposed method is a reliable, efficient, and robust approach for solving the unit commitment problem.     

A dynamic policy for grouping maintenance activities

A maintenance activity carried out on a technical system often involves a system-dependent set-up cost that is the same for all maintenance activities carried out on that system. Grouping activities thus saves costs since execution of a group of activities requires only one set-up. Many maintenance models consider the grouping of maintenance activities on a long-term basis with an infinite horizon. This makes it very difficult to incorporate short-term circumstances such as opportunities or a varying use of components because these are either not known beforehand or make the problem intractable. In this paper we propose a rolling-horizon approach that takes a long-term tentative plan as a basis for a subsequent adaptation according to information that becomes available on the short term. This yields a dynamic grouping policy that assists the maintenance manager in his planning job. We present a fast approach that allows interactive planning by showing how shifts from the tentative planning work out. We illustrate our approach with examples.     

Optimal Replacement Planning by Geometric Programming

Geometric programming (GP) is suggested as an analytical toolfor solving replacement problems with infinite time horizon.The GP solution method is described and explained through theformulation and solution of a typical replacement problem. Asimple example is worked out to demonstrate the pint that GPhas potential as an appropriate mathematical tool for the analysisof certain types of replacement problems.     

Optimal replacement policies for a multicomponent reliability system

This paper studies a discrete time, infinite horizon, dynamic programming model for the replacement of components in a binary coherent system. Under quite general conditions, we show that it is optimal to follow a critical component policy (CCP), i.e., a policy specified by a critical component set and the rule: Replace a component if and only if it is failed and in the critical component set. We also discuss the problem of computing such policies.     

The Trended Inventory Lot Sizing Problem with Shortages Under a New Replenishment Policy

In the past few years, considerable attention has been given to the inventory lot sizing problem with trended demand over a fixed horizon. The traditional replenishment policy is to avoid shortages in the last cycle. Each of the remaining cycles starts with a replenishment and inventory is held for a certain period which is followed by a period of shortages. A new replenishment policy is to start each cycle with shortages and after a period of shortages a replenishment should be made. In this paper, we show that this new type of replenishment policy is superior to the traditional one. We further propose four heuristic procedures that follow the new replenishment policy. These are the constant demand approximation method, the equal cycle length heuristic, the extended Silver approach, and the extended least cost solution procedure. We also examine the cost and computation time performances of these heuristic procedures through an empirical study. The number of test problems solved to optimality, average and maximum cost deviation from optimum were used as measures of cost performance. The results of the 10 000 test problems reveal that the extended least cost approach is most cost effective.     

The average optimality of a repair-limit replacement policy

We consider a minimal-repair and replacement problem of a reliability system whose state at a failure is described by a pair of two attributes, i.e., the total number of its past failures and the current failure level. It is assumed that the system is bothered by more frequent and more costly failures as time passes. Our problem is to find and/or characterize a minimal-repair and replacement policy of minimizing the long-run average expected maintenance cost per unit time over the infinite time horizon. Formulating the problem as a semi-Markov decision process, we show that a repairlimit replacement policy is average optimal. That is, for each total number of past system failures, there exists a threshold, called a repair limit, such that it is optimal to repair minimally if the current failure level is lower than the repair limit, and to replace otherwise. Furthermore, the repair limit is decreasing in the total number of past system failures.     

A multi-objective approach for solving a replacement policy problem for equipment subject to imperfect repairs

This paper proposes a multi-objective approach to model a replacement policy problem applicable to equipment with a predetermined period of use (a planning horizon), which may undergo critical and non-critical failures. Corrective replacements and imperfect repairs are taken to restore the system to operation respectively when critical and non-critical failures occur. Generalized Renewal Process (GRP) is used to model imperfect repairs. The proposed model supports decisions on preventive replacement intervals and the number of spare parts purchased at the beginning of the planning horizon. A Multi-Objective Genetic Algorithm (MOGA) coupled with discrete event simulation (DES) is proposed to provide a set of solutions (Pareto-optimum set) committed to the different objectives of a maintenance manager in the face of a replacement policy problem, that is, maintenance cost, rate of occurrence of failures, unavailability, and investment on spare parts. The proposed MOGA is validated by an application example against the results obtained via the exhaustive approach. Moreover, examples are presented to evaluate the behavior of objective functions on Pareto set (trade-off analysis) and the impact of the repair effectiveness on the decision making.     

Capacity planning for phased implementation of flexible manufacturing systems under budget restrictions

We consider a problem of gradually replacing conventional dedicated machines with flexible manufacturing modules (FMMs) under budget restrictions over a finite planning horizon assuming that dedicated machines cannot be purchased during the planning horizon and acquired FMMs are kept until the end of the horizon. In the problem, a replacement schedule is to be determined and operations are to be assigned to the FMMs or the dedicated machines with the objective of minimizing the sum of discounted costs of acquisition and operation of FMMs and operation costs of conventional dedicated machines. In this research, the problem is formulated as a mixed integer linear program and solved by a Lagrangean relaxation approach. A subgradient optimization method is employed to obtain lower bounds of solutions and a multiplier adjustment method is devised to improve the lower bounds. We develop a linear programming-based Lagrangean heuristic algorithm to find a good feasible solution of the original problem in a reasonable amount of computation time. The algorithm is tested on randomly generated test problems and the results are reported.     

Optimal investment strategies with a reallocation constraint

We study a Merton type optimization problem under a reallocation constraint. Under this restriction, the stock holdings can not be liquidated faster than a certain rate. This is a common restriction in certain type of investment firms. Our main objective is to study the large time optimal growth rate of the expected value of the utility from wealth. We also consider a discounted infinite horizon problem as a step towards understanding the first problem. A numerical study is done by solving the dynamic programming equations. Under the assumption of a power utility function, an appropriate dimension reduction argument is used to reduce the original problem to a two dimensional one in a bounded domain with convenient boundary conditions. Computation of the optimal growth rate introduces additional numerical difficulties as the straightforward approach is unstable. In this direction, new analytical results characterizing the growth rate as the limit of a sequence of finite horizon problems with continuously derived utility are proved.     

A multi-period double coverage approach for locating the emergency medical service stations in Istanbul

We consider the multi-period location planning problem of emergency medical service (EMS) stations. Our objective is to maximize the total population serviced by two distinct stations within two different response time limits over a multi-period planning horizon. Our aim is to provide a backup station in case no ambulance is available in the closer station and to develop a strategic plan that spans multiple periods. In order to solve this problem, we propose a Tabu Search approach. We demonstrate the effectiveness of the proposed approach on randomly generated data. We also implement our approach to the case of Istanbul to determine the locations of EMS stations in the metropolitan area.     

The Single Period Coverage Facility Location Problem: Lagrangean heuristic and column generation approaches

In this paper we introduce the Single Period Coverage Facility Location Problem. It is a multi-period discrete location problem in which each customer is serviced in exactly one period of the planning horizon. The locational decisions are made independently for each period, so that the facilities that are open need not be the same in different time periods. It is also assumed that at each period there is a minimum number of customers that can be assigned to the facilities that are open. The decisions to be made include not only the facilities to open at each time period and the time period in which each customer will be served, but also the allocation of customers to open facilities in their service period.     

Capital renewal as a real option

We consider the timing of replacement of obsolete subsystems within an extensive, complex infrastructure. Such replacement action, known as capital renewal, must balance uncertainty about future profitability against uncertainty about future renewal costs. Treating renewal investments as real options, we derive an optimal solution to the infinite horizon version of this problem and determine the total present value of an institution’s capital renewal options. We investigate the sensitivity of the infinite horizon solution to variations in key problem parameters and highlight the system scenarios in which timely renewal activity is most profitable. For finite horizon renewal planning, we show that our solution performs better than a policy of constant periodic renewals if more than two renewal cycles are completed.     

The Repair Limit Replacement Method

In the repair limit replacement method when an item requires repair it is first inspected and the repair cost is estimated. Repair is only then undertaken if the estimated cost is less than the "repair limit". Dynamic programming methods are used in this paper as a general approach to the problem of determining optimum repair limits. Two problems are formulated and the cases of finite and infinite planning horizons and discounted and undiscounted costs are discussed. Methods are given for allowing for equipment availability and for the introduction of new types of equipment. An improved general formulation for finite time horizon, stochastic, dynamic programming problems is developed.     

Optimal birth control of population dynamics

The authors studied optimal birth control policies for an age-structured population of McKendrick type which is a distributed parameter system involving 1st order partial differential equations with nonlocal bilinear boundary control. The functional analytic approach of Dubovitskii and Milyutin is adopted in the investigation. Maximum principles for problems with a free end condition and fixed final horizon are developed, and the time optimal control problems, the problem with target sets, and infinite planning horizon case are investigated.