11 research outputs found
Managing supply chain risks with dual sourcing: Bayesian learning of censored supply capacity
No full textDual sourcing is a common strategy for mitigating supply chain risks, with supply capacity uncertainty being one of the most significant risks. However, firms often have limited knowledge about uncertain supply capacity, and can only observe it when the delivered quantity is less than the ordered amount. This leads to censored supply capacity observations. To investigate how supply capacity learning affects dual-sourcing decisions, we propose a model of a firm sourcing non-storable substitute products from an expensive reliable supplier and an inexpensive unreliable supplier to meet a deterministic time-varying demand over a finite horizon. The unreliable supplier has a random capacity with an unknown parameter. The firm updates its belief about this parameter using Bayesian learning and adapts its sourcing decisions to balance the tradeoff between maximizing current profits based on its current belief (exploitation) and increasing the precision of its belief for future periods (exploration). We use Bayesian dynamic programming to determine the firm's myopic sourcing policy and partially characterize its optimal sourcing policy. We apply a state space reduction technique to Weibull distributed capacity, resulting in an inductively solvable optimization problem. The optimal sourcing policy can be obtained under a condition that ensures splitting the demand between the suppliers is optimal. For exponentially distributed capacity, the optimization problem has a recursive closed-form solution, and the optimal sourcing policy is such that the optimal order quantity from the reliable (unreliable) supplier is smaller (greater) than the myopic quantity. We complement our analytical results with numerical examples and discuss extensions to random demand and inventory carryover
On the optimality of the Gittins index rule for multi-armed bandits with multiple plays
No full textWe investigate the general multi-armed bandit problem with multiple servers. We determine a condition on the reward processes sufficient to guarantee the optimality of the strategy that operates at each instant of time the projects with the highest Gittins indices. We call this strategy the Gittins index rule for multi-armed bandits with multiple plays, or briefly the Gittins index rule. We show by examples that: (i) the aforementioned sufficient condition is not necessary for the optimality of the Gittins index rule; and (ii) when the sufficient condition is relaxed the Gittins index rule is not necessarily optimal. Finally, we present an application of the general results to the multiserver scheduling of parallel queues without arrivals.Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/41854/1/186-50-3-449_90500449.pd
Optimal Control of Noncollaborative Servers in Two-Stage Tandem Queueing Systems
No full textWe consider two-stage tandem queueing systems with dedicated servers in each station and a flexible server that is trained to serve both stations. We assume no arrivals, exponential service times, and linear holding costs for jobs present in the system. We study the optimal dynamic assignment of servers to jobs assuming a noncollaborative work discipline with idling and preemptions allowed. For larger holding costs in the first station, we show that (i) nonidling policies are optimal and (ii) if the flexible server is not faster than the dedicated servers, the optimal server allocation strategy has a threshold-type structure. For all other cases, we provide numerical results that support the optimality of threshold-type policies. Our numerical experiments also indicate that when the flexible server is faster than the dedicated server of the second station, the optimal policy may have counterintuitive properties, which is not the case when a collaborative service discipline is assumed. (C) 2014 Wiley Periodicals, Inc
Optimal control of flexible servers in two tandem queues with operating costs
No full textWe consider two-stage tandem queuing systems with dedicated servers in each station and flexible servers that can serve in both stations. We assume exponential service times, linear holding costs, and operating costs incurred by the servers at rates proportional to their speeds. Under conditions that ensure the optimality of nonidling policies, we show that the optimal allocation of flexible servers is determined by a transition-monotone policy. Moreover, we present conditions under which the optimal policy can be explicitly determined
Markov decision processes with multidimensional action spaces
No full textWe study controlled Markov processes where multiple decisions need to be made for each state. We present conditions on the cost structure and the state transition mechanism of the process under which optimal decisions are restricted to a subset of the decision space. As a result, the numerical computation of the optimal policy may be significantly expedited.Markov processes Dynamic programming Multiple servers
Optimal stochastic scheduling and routing in queueing networks.
No full textQueueing networks are extensively used in the study of systems such as communication, computer, and manufacturing networks. Presently there exists some conceptual understanding of many underlying issues of network performance; yet, there remain fundamental issues that are not well understood and need to be investigated. Such issues are related to efficient network resource utilization and routing under imperfect information. In this dissertation we investigate stochastic scheduling, resource allocation and dynamic routing problems arising in queueing networks. We determine optimal policies or derive qualitative properties of optimal policies for the problems described below. We study the problem of optimally scheduling time-critical tasks in multi-class queueing systems. Two different versions of the problem are considered: (i) If the service of a task does not begin by a certain deadline, the task is lost and a fixed cost is incurred; and (ii) if the service of a task is completed at a time other than a certain due date, a penalty proportional to the earliness or tardiness is incurred. We determine properties of dynamic nonidling strategies that minimize infinite horizon expected costs. Next we consider the problem of optimally scheduling tasks in a multi-server system consisting of two interconnected queues. Tasks incur an instantaneous holding cost during the time they remain in the system. We establish sufficient conditions on the service times, the holding costs, and the interconnection process under which it is possible to explicitly determine the strategy that minimizes the total expected discounted cost. Finally we investigate the following decentralized routing problem. We consider a queueing system consisting of two service stations and two controllers, one in front of each station. Customers arriving at a controller's site are to be routed to one of the two stations. Each controller has perfect knowledge of the queue length in its own station and receives information about the other station's queue length with delay of one time unit. We explicitly determine the controllers' routing strategies that minimize the customers' total flowtime.PhDElectrical Engineering: SystemsUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/104185/1/9501012.pdfDescription of 9501012.pdf : Restricted to UM users only
A simple load balancing problem with decentralized information
No full textThe following load balancing problem is investigated in discrete time: A service system consists of two service stations and two controllers, one in front of each station. The service stations provide the same service with identical service time distributions and identical waiting costs. Customers requiring service arrive at a controller's site and are routed to one of the two stations by the controller. The processes describing the two arrival streams are identical. Each controller has perfect knowledge of the workload in its own station and receives information about the other station's workload with one unit of delay. The controllers' routing strategies that minimize the customers' total flowtime are determined for a certain range of the parameters that describe the arrival process and the service distribution. Specifically, we prove that optimal routing strategies are characterized by thresholds that are either precisely specified or take one of two possible values.Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/45840/1/186_2005_Article_BF01246331.pd
Optimality of Index Policies for Stochastic Scheduling with Switching Penalties
No full textWe investigate the impact of switching penalties on the nature of optimal scheduling policies for systems of parallel queues without arrivals. We study two types of switching penalties incurred when switching between queues: lump sum costs and time delays. Under the assumption that the service periods of jobs in a given queue possess the same distribution, we derive an index rule that defines an optimal policy. For switching penalties that depend on the particular nodes involved in a switch, we show that although an index rule is not optimal in general, there is an exhaustive service policy that is optimal
