Doubly Stochastic Sequential Assignment Problem

This article introduces the Doubly Stochastic Sequential Assignment Problem (DSSAP), an extension of the Sequential Stochastic Assignment Problem (SSAP), where sequentially arriving tasks are assigned to workers with random success rates. A given number of tasks arrive sequentially, each with a random value coming from a known distribution. On a task arrival, it must be assigned to one of the available workers, each with a random success rate coming from a known distribution. Optimal assignment policies are proposed for DSSAP under various assumptions on the random success rates. The optimal assignment algorithm for the general case of DSSAP, where workers have distinct success rate distribution, has an exponential running time. An approximation algorithm that achieves a fraction of the maximum total expected reward in a polynomial time is proposed. The results are illustrated by several numerical experiments. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 124–137, 2016     

Minimizing makespan in a multimode multiprocessor shop scheduling problem

We study the problem of multimode scheduling tasks on dedicated processors, with the objective of minimizing the maximum completion time. Each task can be undertaken in one among a set of predefined alternative modes, where each mode specifies a required set of dedicated processors and a processing time. At any time each processor can be used by a single task at most. General precedence constraints exist among tasks, and task preemption is not allowed. The problem consists of assigning a mode and a starting time to each task, respecting processor and precedence constraints, to minimize the time required to complete all tasks. The problem is NP-hard in several particular cases. In previous works, we studied algorithms in which a solution was obtained by means of an iterative procedure that combines mode assignment and sequencing phases separately. In this paper, we present some new heuristics where the decision on the mode assignment is taken on the basis of a partial schedule. Then, for each task, the mode selection and the starting time are chosen simultaneously considering the current processor usage. Different lower bounds are derived from a mathematical formulation of the problem and from a graph representation of a particular relaxed version of the problem. Heuristic solutions and lower bounds are evaluated on randomly generated test problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 893–911, 1999     

Deterministic and stochastic scheduling with teamwork tasks

We study a class of new scheduling problems which involve types of teamwork tasks. Each teamwork task consists of several components, and requires a team of processors to complete, with each team member to process a particular component of the task. Once the processor completes its work on the task, it will be available immediately to work on the next task regardless of whether the other components of the last task have been completed or not. Thus, the processors in a team neither have to start, nor have to finish, at the same time as they process a task. A task is completed only when all of its components have been processed. The problem is to find an optimal schedule to process all tasks, under a given objective measure. We consider both deterministic and stochastic models. For the deterministic model, we find that the optimal schedule exhibits the pattern that all processors must adopt the same sequence to process the tasks, even under a general objective function GC = F(f₁(C₁), f₂(C₂), … , f_n(C_n)), where f_i(C_i) is a general, nondecreasing function of the completion time C_i of task i. We show that the optimal sequence to minimize the maximum cost MC = max f_i(C_i) can be derived by a simple rule if there exists an order f₁(t) ≤ … ≤ f_n(t) for all t between the functions {f_i(t)}. We further show that the optimal sequence to minimize the total cost TC = ∑ f_i(C_i) can be constructed by a dynamic programming algorithm. For the stochastic model, we study three optimization criteria: (A) almost sure minimization; (B) stochastic ordering; and (C) expected cost minimization. For criterion (A), we show that the results for the corresponding deterministic model can be easily generalized. However, stochastic problems with criteria (B) and (C) become quite difficult. Conditions under which the optimal solutions can be found for these two criteria are derived. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A heuristic procedure for allocating tasks in fault-tolerant distributed computer systems

One way of achieving the increased levels of system reliability and availability demanded by critical computer-based control systems is through the use of fault-tolerant distributed computer systems. This article addresses the problem of allocating a set of m tasks among a set of n processors in a manner that will satisfy various task assignment, system capacity, and task scheduling constraints while balancing the workload across processors. We discuss problem background, problem formulation, and a known heuristic procedure for the problem. A new solution-improving heuristic procedure is introduced, and computational experience with the heuristics is presented. With only a modest increase in the amount of computational effort, the new procedure is demonstrated to improve dramatically solution quality as well as obtain near-optimal solutions to the test problems.     

Nonstationary stochastic gold-mining: A time-sequential tactical-allocation problem

This paper presents an extension of gold-mining problems formulated in earlier work by R. Bellman and J. Kadane. Bellman assumes there are two gold mines labeled A and B, respectively, each with a known initial amount of gold. There is one delicate gold-mining machine which can be used to excavate one mine per day. Associated with mine A is a known constant return rate and a known constant probability of breakdown. There is also a return rate and probability of breakdown for mine B. Bellman solves the problem of finding a sequential decision procedure to maximize the expected amount of gold obtained before breakdown of the machine. Kadane extends the problem by assuming that there are several mines and that there are sequences of constants such that the jth constant for each mine represents the return rate for the jth excavation of that mine. He also assumes that the probability of breakdown during the jth excavation of a mine depends on j. We extend these results by assuming that the return rates are random variables with known joint distribution and by allowing the probability of breakdown to be a function of previous observations on the return rates. We show that under certain regularity conditions on the joint distributions of the random variables, the optimal policy is: at each stage always select a mine which has maximal conditional expected return per unit risk. This gold-mining problem is also a formulation of the problem of time-sequential tactical allocation of bombers to targets. Several examples illustrating these results are presented.     

Exact algorithms and bounds for the dynamic assignment interdiction problem

We study a multi‐stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP‐hard, even when the attacker can interdict only one arc. We propose an exact exponential‐state dynamic‐programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 373–387, 2017     

A generalized assignment model for dynamic supply chain capacity planning

We consider a generalization of the well‐known generalized assignment problem (GAP) over discrete time periods encompassed within a finite planning horizon. The resulting model, MultiGAP, addresses the assignment of tasks to agents within each time period, with the attendant single‐period assignment costs and agent‐capacity constraint requirements, in conjunction with transition costs arising between any two consecutive periods in which a task is reassigned to a different agent. As is the case for its single‐period antecedent, MultiGAP offers a robust tool for modeling a wide range of capacity planning problems occurring within supply chain management. We provide two formulations for MultiGAP and establish that the second (alternative) formulation provides a tighter bound. We define a Lagrangian relaxation‐based heuristic as well as a branch‐and‐bound algorithm for MultiGAP. Computational experience with the heuristic and branch‐and‐bound algorithm on over 2500 test problems is reported. The Lagrangian heuristic consistently generates high‐quality and in many cases near‐optimal solutions. The branch‐and‐bound algorithm is also seen to constitute an effective means for solving to optimality MultiGAP problems of reasonable size. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria

We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive‐repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date‐related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A sequential dynamic pricing model and its applications

Consider a sequential dynamic pricing model where a seller sells a given stock to a random number of customers. Arriving one at a time, each customer will purchase one item if the product price is lower than her personal reservation price. The seller's objective is to post a potentially different price for each customer in order to maximize the expected total revenue. We formulate the seller's problem as a stochastic dynamic programming model, and develop an algorithm to compute the optimal policy. We then apply the results from this sequential dynamic pricing model to the case where customers arrive according to a continuous‐time point process. In particular, we derive tight bounds for the optimal expected revenue, and develop an asymptotically optimal heuristic policy. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Monotone optimal preventive maintenance policies for stochastically failing equipment

This paper examines various models for maintenance of a machine operating subject to stochastic deterioration. Three alternative models are presented for the deterioration process. For each model, in addition to the replacement decision, the option exists of performing preventive maintenance. The effect of this maintenance is to “slow” the deterioration process. With an appropriate reward structure imposed on the processes, the models are formulated as continuous time Markov decision processes. the optimality criterion being the maximization of expected discounted reward earned over an infinite time horizon. For each model conditions are presented under which the optimal maintenance policy exhibits the following monotonic structure. First, there exists a control limit rule for replacement. That is, there exists a number i* such that if the state of machine deterioration exceeds i* the optimal policy replaces the machine by a new machine. Secondly, prior to replacement the optimal level of preventive maintenance is a nonincreasing function of the state of machine deterioration. The conditions which guarantee this result have a cost/benefit interpretation.     

Optimal sensor placement for underwater threat detection

The optimization framework for optimal sensor placement for underwater threat detection has been developed. It considers single‐period and multiperiod detection models, each of which includes two components: detection algorithm and optimization problem for sensor placement. The detection algorithms for single‐period and multiperiod models are based on likelihood ratio and sequential testing, respectively. For the both models, the optimization problems use the principle of superadditive coverage, which is closely related to energy‐based and information‐based approaches. An algorithm for quasi‐regular sensor placement approximating solutions to the optimization problems has been developed based on corresponding continuous relaxations and a criterion for its applicability has been obtained. Numerical experiments have demonstrated that the algorithm consistently outperforms existing optimization techniques for optimal sensor placement.© 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

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.     

The search for an intelligent evader: Strategies for searcher and evader in the two-region problem

This paper considers the search for an evader concealed in one of two regions, each of which is characterized by its detection probability. The single-sided problem, in which the searcher is told the probability of the evader being located in a particular region, has been examined previously. We shall be concerned with the double-sided problem in which the evader chooses this probability secretly, although he may not subsequently move: his optimal strategy consists of that probability distribution which maximizes the expected time to detection, while the searcher's optimal strategy is the sequence of searches which limits the evader to this expected time. It transpires for this problem that optimal strategies for both searcher and evader may generally be obtained to a surprisingly good degree of approximation by using the optimal strategies for the closely related (but far more easily solved) problem in which the evader is completely free to move between searches.     

舰艇编队作战任务优化分配

从舰艇编队的实际作战需求出发,将作战使命分解为多个作战任务,然后分配给相关平台。首先在每个平台只能承担一项任务的前提下,构建了编队作战任务分配的基本模型。在此基础上研究了两平台协同执行任务时效能互补、单平台在同时执行多项任务时武器装备相互干扰等情况,进一步构建了考虑平台间协同效益和平台执行多任务的作战任务分配模型。应用改进的遗传算法给出了编队作战任务分配方案优化选择的具体方法步骤,最后针对一个典型案例进行了仿真计算与分析,验证了三种模型的合理性。     

Optimal ordering policies for a product that perishes in two periods subject to stochastic demand

This paper considers the problem of computing optimal ordering policies for a product that has a life of exactly two periods when demand is random. Initially costs are charged against runouts (stockouts) and outdating (perishing). By charging outdating costs according to the expected amount of outdating one period into the future, a feasible one period model is constructed. The central theorem deals with the n-stage dynamic problem and demonstrates the appropriate cost functions are convex in the decision variable and also provides bounds on certain derivatives. The model is then generalized to include ordering and holding costs. The paper is concluded with a discussion of the infinite horizon problem.     

A characterization of optimal base‐stock levels for a multistage serial supply chain

In this article, we present a multistage model to optimize inventory control decisions under stochastic demand and continuous review. We first formulate the general problem for continuous stages and use a decomposition solution approach: since it is never optimal to let orders cross, the general problem can be broken into a set of single‐unit subproblems that can be solved in a sequential fashion. These subproblems are optimal control problems for which a differential equation must be solved. This can be done easily by recursively identifying coefficients and performing a line search. The methodology is then extended to a discrete number of stages and allows us to compute the optimal solution in an efficient manner, with a competitive complexity. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 32–46, 2016     

Periodic inspection policy with preventive maintenance

This article considers a modified inspection policy with periodic check intervals, where the unit after check has the same age as before with probability p and is as good as new with probability q. The mean time to failure and the expected number of checks before failure are derived, forming renewal-type equations. The total expected cost and the expected cost per unit of time until detection of failure are obtained. Optimum inspection policies which minimize the expected costs are given as a numerical example.     

Scheduling of stochastic tasks on two parallel processors

We consider the problem of scheduling n tasks on two identical parallel processors. We show both in the case when the processing times for the n tasks are independent exponential random variables, and when they are independent hyperexponentials which are mixtures of two fixed exponentials, that the policy of performing tasks with longest expected processing time (LEPT) first minimizes the expected makespan, and that in the hyperexponential case the policy of performing tasks with shortest expected processing time (SEPT) first minimizes the expected flow time. The approach is simpler than the dynamic programming approach recently employed by Bruno and Downey.     

Bayesian selling problem with partial information

We introduce an optimal stopping problem for selling an asset when the fixed but unknown distribution of successive offers is from one of n possible distributions. The initial probabilities as to which is the true distribution are given and updated in a Bayesian manner as the successive offers are observed. After receiving an offer, the seller has to decide whether to accept the offer or continue to observe the next offer. Each time an offer is observed a fixed cost is incurred. We consider both the cases where recalling a past offer is allowed and where it is not allowed. For each case, a dynamic programming model and some heuristic policies are presented. Using simulation, the performances of the heuristic methods are evaluated and upper bounds on the optimal expected return are obtained. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Optimal power control in a wireless network using a model with stochastic link coefficients

This paper addresses optimal power allocation in a wireless communication network under uncertainty. The paper introduces a framework for optimal transmit power allocation in a wireless network where both the useful and interference coefficients are random. The new approach to power control is based on a stochastic programming formulation with probabilistic SIR constraints. This allows to state the power allocation problem as a convex optimization problem assuming normally or log‐normally distributed communication link coefficients. Numerical examples illustrate the performance of the optimal stochastic power allocation. A distributed algorithm for the decentralized solution of the stochastic power allocation problem is discussed. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005