Statistical decision analysis of stochastic linear programming problems

This paper presents a statistical decision analysis of a one-stage linear programming problem with deterministic constraints and stochastic criterion function. Procedures for obtaining numerical results are given which are applicable to any problem having this general form. We begin by stating the statistical decision problems to be considered, and then discuss the expected value of perfect information and the expected value of sample information. In obtaining these quantities, use is made of the distribution of the optimal value of the linear programming problem with stochastic criterion function, and so we discuss Monte Carlo and numerical integration procedures for estimating the mean of this distribution. The case in which the random criterion vector has a multivariate Normal distribution is discussed separately, and more detailed methods are offered. We discuss dual problems, including some relationships of this work with other work in probabilistic linear programming. An example is given in Appendix A showing application of the methods to a sample problem. In Appendix B we consider the accuracy of a procedure for approximating the expected value of information.     

Inventory control in divergent supply chains with time‐based dispatching and shipment consolidation

This article analyses a divergent supply chain consisting of a central warehouse and N nonidentical retailers. The focus is on joint evaluation of inventory replenishment and shipment consolidation effects. A time‐based dispatching and shipment consolidation policy is used at the warehouse in conjunction with real‐time point‐of‐sale data and centralized inventory information. This represents a common situation, for example, in various types of vendor managed inventory systems. The main contribution is the derivation of an exact recursive procedure for determining the expected inventory holding and backorder costs for the system, under the assumption of Poisson demand. Two heuristics for determining near optimal shipment intervals are also presented. The results are applicable both for single‐item and multiitem systems. © 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 59–71, 2011     

基于逆向分层的工作流时间-费用优化方法

针对效用网格下基于优先级因子的工作流时间-费用优化问题,基于工作流的同步完成特征对任务进行分层并提出三种实时调度算法:基于逆向分层的sufferage(BLSuff)、基于逆向分层的min-min(BLMin)及基于逆向分层的min-max(BLMax)。算法设计基于优先级因子的衡量标准对时间与费用同时进行优化,并为任务设置期望完成时间以达到充分利用费用优化空间进行费用优化的目标。实验结果表明这三种算法在各种优先级因子下都能对工作流的执行时间与执行费用进行较好的优化。     

利用几何结构求解欧氏平面TSP的改进遗传算法

TSP是经典的组合优化问题。根据欧氏平面TSP最优环路的性质提出了子路径及相关的概念,利用点集凸壳设计了环路构造算法,并以点集Delaunay三角剖分图为启发信息设计了改进的遗传算法,通过中国144城市TSP等验证了算法的有效性。     

State information lag markov decision process with control limit rule

In the framework of a discrete Markov decision process with state information lag, this article suggests a way for selecting an optimal policy using the control limit rule. The properties sufficient for an optimal decision rule to be contained in the class of control limit rules are also studied. The degradation in expected reward from that of the perfect information process provides a measure of the potential value of improving the information system.     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A sequential partial information bomber-defender shooting problem

A bomber carrying homogenous weapons sequentially engages ground targets capable of retaliation. Upon reaching a target, the bomber may fire a weapon at it. If the target survives the direct fire, it can either return fire or choose to hold fire (play dead). If the former occurs, the bomber is immediately made aware that the target is alive. If no return fire is seen, the true status of the target is unknown to the bomber. After the current engagement, the bomber, if still alive, can either re-engage the same target or move on to the next target in the sequence. The bomber seeks to maximize the expected cumulative damage it can inflict on the targets. We solve the perfect and partial information problems, where a target always fires back and sometimes fires back respectively using stochastic dynamic programming. The perfect information scenario yields an appealing threshold based bombing policy. Indeed, the marginal future reward is the threshold at which the control policy switches and furthermore, the threshold is monotonic decreasing with the number of weapons left with the bomber and monotonic nondecreasing with the number of targets left in the mission. For the partial information scenario, we show via a counterexample that the marginal future reward is not the threshold at which the control switches. In light of the negative result, we provide an appealing threshold based heuristic instead. Finally, we address the partial information game, where the target can choose to fire back and establish the Nash equilibrium strategies for a representative two target scenario.     

An integer programming model for the weekly tour scheduling problem

We study a workforce planning and scheduling problem in which weekly tours of agents must be designed. Our motivation for this study comes from a call center application where agents serve customers in response to incoming phone calls. Similar to many other applications in the services industry, the demand for service in call centers varies significantly within a day and among days of the week. In our model, a weekly tour of an agent consists of five daily shifts and two days off, where daily shifts within a tour may be different from each other. The starting times of any two consecutive shifts, however, may not differ by more than a specified bound. Furthermore, a tour must also satisfy constraints regarding the days off, for example, it may be required that one of the days off is on a weekend day. The objective is to determine a collection of weekly tours that satisfy the demand for agents' services, while minimizing the total labor cost of the workforce. We describe an integer programming model where a weekly tour is obtained by combining seven daily shift scheduling models and days‐off constraints in a network flow framework. The model is flexible and can accommodate different daily models with varying levels of detail. It readily handles different days‐off rules and constraints regarding start time differentials in consecutive days. Computational results are also presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 607–624, 2001.     

Spares stocking policies for repairable items with dependent repair times

This paper analyzes the problem of determining desirable spares inventory levels for repairable items with dependent repair times. The problem is important for repairable products such as aircraft engines which can have very large investment in spares inventory levels. While existing models can be used to determine optimal inventory spares levels when repair times are independent, the practical considerations of limited repair shop capacity and prioritized shop dispatching rules combine to make repair times not independent of one another. In this research a simulation model of a limited capacity repair facility with prioritized scheduling is used to explore a variety of heuristic approaches to the spares stocking decision. The heuristics are also compared with use of a model requiring independent repair times (even though that assumption is not valid here). The results show that even when repair time dependencies are present, the performance of a model which assumes independent repair times is quite good.     

Production‐inventory systems with imperfect advance demand information and updating

We consider a supplier with finite production capacity and stochastic production times. Customers provide advance demand information (ADI) to the supplier by announcing orders ahead of their due dates. However, this information is not perfect, and customers may request an order be fulfilled prior to or later than the expected due date. Customers update the status of their orders, but the time between consecutive updates is random. We formulate the production‐control problem as a continuous‐time Markov decision process and prove there is an optimal state‐dependent base‐stock policy, where the base‐stock levels depend upon the numbers of orders at various stages of update. In addition, we derive results on the sensitivity of the state‐dependent base‐stock levels to the number of orders in each stage of update. In a numerical study, we examine the benefit of ADI, and find that it is most valuable to the supplier when the time between updates is moderate. We also consider the impact of holding and backorder costs, numbers of updates, and the fraction of customers that provide ADI. In addition, we find that while ADI is always beneficial to the supplier, this may not be the case for the customers who provide the ADI. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Machine maintenance with workload considerations

Machine maintenance is modeled in the setting of a single‐server queue. Machine deterioration corresponds to slower service rates and failure. This leads to higher congestion and an increase in customer holding costs. The decision‐maker decides when to perform maintenance, which may be done pre‐emptively; before catastrophic failures. Similar to classic maintenance control models, the information available to the decision‐maker includes the state of the server. Unlike classic models, the information also includes the number of customers in queue. Considered are both a repair model and a replacement model. In the repair model, with random replacement times, fixed costs are assumed to be constant in the server state. In the replacement model, both constant and variable fixed costs are considered. It is shown in general that the optimal maintenance policies have switching curve structure that is monotone in the server state. However, the switching curve policies for the repair model are not always monotone in the number of customers in the queue. Numerical examples and two heuristics are also presented. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Analysis of supply contracts with commitments and flexibility

In this article we address an important class of supply contracts called the Rolling Horizon Flexibility (RHF) contracts. Under such a contract, at the beginning of the horizon a buyer has to commit requirements for components for each period into the future. Usually, a supplier provides limited flexibility to the buyer to adjust the current order and future commitments in a rolling horizon manner. We present a general model for a buyer's procurement decision under RHF contracts. We propose two heuristics and derive a lower bound. Numerically, we demonstrate the effectiveness of the heuristics for both stationary and non‐stationary demands. We show that the heuristics are easy to compute, and hence, amenable to practical implementation. We also propose two measures for the order process that allow us to (a) evaluate the effectiveness of RHF contracts in restricting the variability in the orders, and (b) measure the accuracy of advance information vis‐a‐vis the actual orders. Numerically we demonstrate that the order process variability decreases significantly as flexibility decreases without a dramatic increase in expected costs. Our numerical studies provide several other managerial insights for the buyer; for example, we provide insights into how much flexibility is sufficient, the value of additional flexibility, the effect of flexibility on customer satisfaction (as measured by fill rate), etc. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Exponential size neighborhoods for makespan minimization scheduling

We investigate the quality of local search heuristics for the scheduling problem of minimizing the makespan on identical parallel machines. We study exponential size neighborhoods (whose size grows exponentially with the input length) that can be searched in polynomial time, and we derive worst‐case approximation guarantees for the local optima of such neighborhoods. The so‐called split neighborhood splits a feasible schedule into two layers, and then recombines the two layers by finding a perfect matching. We show that the makespan of every local optimum for split is at most a factor of 2 away from the globally optimal makespan. We then combine the split neighborhood with two neighborhoods from the literature. The combination of split with the jump neighborhood only marginally improves the approximation guarantee, whereas the combination with the lexicographic‐jump neighborhood decreases the approximation guarantee from 2 to 3/2. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Scheduling jobs with piecewise linear decreasing processing times

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP‐hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP‐hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 2003     

Asymptotic analysis of periodic policies for the inventory routing problem

In this article, a distribution system is studied where the sum of transportation and inventory costs is to be minimized. The inventory holding cost is assumed to be the same for all retailers. A fixed partition (FP) periodic policy is proposed with tight asymptotic worst‐case performance of 3/2 with respect to the best possible policy. This bound cannot be improved in the class of FP periodic policies. In partition‐based PB policies, the retailers are first partitioned into sets and then the sets are grouped in such a way that sets of retailers within a group are served together at selected times. A PB periodic, policy is presented with tight worst‐case asymptotic performance of with respect to the best possible policy. This latter performance improves the worst‐case asymptotic performance of of the previously best known policy for this problem. We also show that the proposed PB periodic policy has the best worst‐case asymptotic performance within the class of PB policies. Finally, practical heuristics inspired by the analyzed policies are designed and tested. The asymptotic worst–case performances of the heuristics are shown to be the same of those of the analyzed policies. Computational results show that the heuristics suggested are less than 6.4% on average from a lower bound on the optimal cost when 50 or more retailers are involved. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 00: 000–000, 2013     

Optimal design of a multi-item,multi-location,multi-repair type repair and supply system

The design of a system with many locations, each with many items which may fail while in use, is considered. When items fail, they require repair; the particular type of repair being governed by a probability distribution. As repairs may be lengthy, spares are kept on hand to replace failed items. System ineffectiveness is measured by expected weighted shortages over all items and locations, in steady state. This can be reduced by either having more spares or shorter expected repair times. Design consists of a provisioning of the number of spares for each item, by location; and specifying the expected repair times for each type of repair, by item and location. The optimal design minimizes expected shortages within a budget constraint, which covers both (i) procurement of spares and (ii) procurement of equipment and manning levels for the repair facilities. All costs are assumed to be separable so that a Lagrangian approach is fruitful, yielding an implementable algorithm with outputs useful for sensitivity analysis. A numerical example is presented.     

On the first come–first served rule in multi‐echelon inventory control

A two‐echelon distribution inventory system with a central warehouse and a number of retailers is considered. The retailers face stochastic demand and replenish from the warehouse, which, in turn, replenishes from an outside supplier. The system is reviewed continuously and demands that cannot be met directly are backordered. Standard holding and backorder costs are considered. In the literature on multi‐echelon inventory control it is standard to assume that backorders at the warehouse are served according to a first come–first served policy (FCFS). This allocation rule simplifies the analysis but is normally not optimal. It is shown that the FCFS rule can, in the worst case, lead to an asymptotically unbounded relative cost increase as the number of retailers approaches infinity. We also provide a new heuristic that will always give a reduction of the expected costs. A numerical study indicates that the average cost reduction when using the heuristic is about two percent. The suggested heuristic is also compared with two existing heuristics. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Scheduling recurrent construction

A problem we call recurrent construction involves manufacturing large, complex, expensive products such as airplanes, houses, and ships. Customers order configurations of these products well in advance of due dates for delivery. Early delivery may not be permitted. How should the manufacturer determine when to purchase and release materials before fabrication, assembly, and delivery? Major material expenses, significant penalties for deliveries beyond due dates, and long product makespans in recurrent construction motivate choosing a release timetable that maximizes the net present value of cash flows. Our heuristic first projects an initial schedule that dispatches worker teams to tasks for the backlogged products, and then solves a series of maximal closure problems to find material release times that maximize NPV. This method compares favorably with other well‐known work release heuristics in solution quality for large problems over a wide range of operating conditions, including order strength, cost structure, utilization level, batch policy, and uncertainty level. Computation times exhibit near linear growth in problem size. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

On the asymptotic optimality of algorithms for the flow shop problem with release dates

We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP‐hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.