Search

Resource flexibility, arguably among the most celebrated operational concepts, is known to provide firms facing demand uncertainty with such benefits as risk pooling, revenue-maximization optionality, and operational hedging. In this paper, we uncover a heretofore unknown benefit: we establish that resource flexibility facilitates learning the demand when the latter is censored, which could, in turn, enable firms to make better-informed future operational decisions, thereby increasing profitability. Further, we quantify these learning benefits of flexibility and find that they could be of the same order of magnitude as the extensively studied risk-pooling benefits of flexibility. This suggests that flexibility’s learning benefits could be a first-order consideration and that extant theories, which view flexibility only as the ability to act ex post, could be underestimating its true value when learning the demand is desirable, for example, when it enables managers to make better ex ante capacity, assortment, or pricing decisions in future periods. This paper was accepted by Vishal Gaur, operations management.

We consider a single-hop switched queueing network with a mix of heavy-tailed (i.e., arrival processes with infinite variance) and light-tailed traffic, and study the delay performance of the Max-Weight policy, known for its throughput optimality and asymptotic delay optimality properties. Classical results in queueing theory imply that heavy-tailed queues are delay unstable, i.e., they experience infinite expected delays in steady state. Thus, we focus on the impact of heavy-tailed traffic on the light-tailed queues, using delay stability as performance metric. Recent work has shown that this impact may come in the form of subtle rate-dependent phenomena, the stochastic analysis of which is quite cumbersome. Our goal is to show how fluid approximations can facilitate the delay analysis of the Max-Weight policy under heavy-tailed traffic. More specifically, we show how fluid approximations can be combined with renewal theory in order to prove delay instability results. Furthermore, we show how fluid approximations can be combined with stochastic Lyapunov theory in order to prove delay stability results. We illustrate the benefits of the proposed approach in two ways: (i) analytically, by providing a sharp characterization of the delay stability regions of networks with disjoint schedules, significantly generalizing previous results; (ii) computationally, through a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions.

We study the problem of scheduling over time varying links in a network that serves both heavy-tailed and light tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic (the heavy queue), and the other receives light-tailed traffic (the light queue). The queues are connected to the server through time-varying ON/OFF links, which model fading wireless channels. We first show that the policy that gives complete priority to the light-tailed traffic guarantees the best possible tail behavior of both queue backlog distributions, whenever the queues are stable. However, the priority policy is not throughput maximizing, and can cause undesirable instability effects in the heavy queue. Next, we study the class of throughput optimal max-weight-α scheduling policies. We discover a threshold phenomenon, and show that the steady state light queue backlog distribution is heavy-tailed for arrival rates above a threshold value, and light-tailed otherwise. We also obtain the exact tail coefficient of the light queue backlog distribution under max-weight-α scheduling. Finally, we study a log-max-weight scheduling policy, which is throughput optimal, and ensures that the light queue backlog distribution is light-tailed., National Science Foundation (U.S.) (Grant CNS-1217048), National Science Foundation (U.S.) (Grant CNS-0915988), National Science Foundation (U.S.) (CMMI-1234062), United States. Army Research Office. Multidisciplinary University Research Initiative (Grant W911NF-08-1-0238)

We study scheduling and routing problems that arise in multi-hop wireline networks with a mix of heavy-tailed and light-tailed traffic. We analyze the delay performance of the widely studied class of Back-Pressure policies, known for their throughput optimality property, using as a performance criterion the notion of delay stability, i.e., whether the expected end-to-end delay in steady state is finite. First, by means of simple examples, we provide insights into how the network topology, the routing constraints, and the link capacities (relative to the arrival rates) may affect the delay stability of the Back-Pressure policy in the presence of heavy-tailed traffic. Next, we illustrate how fluid approximations facilitate the delay-stability analysis of multi-hop networks with heavy-tailed traffic. This approach allows us to derive analytical results that would have been hard to obtain otherwise, and also to build a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions. Finally, we show how one can achieve optimal performance, with respect to the delay stability criterion, by using a parameterized version of the Back-Pressure policy., National Science Foundation (U.S.) (Grant CNS-1217048), National Science Foundation (U.S.) (Grant CCF-0728554), National Science Foundation (U.S.) (CMMI-1234062), United States. Office of Naval Research (Grant N00014-12-1-0064), United States. Army Research Office. Multidisciplinary University Research Initiative (Grant W911NF-08-1-0238)

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (p. 203-209)., We study scheduling problems arising in switched queueing networks, a class of stochastic systems that are often used to model data communication networks, such as uplinks and downlinks of cellular networks, networks of data switches, and ad hoc wireless networks. Motivated by empirical evidence of self-similarity and long-range dependence, the networks that we consider receive a mix of heavy-tailed and light-tailed trac. In this setting we evaluate the delay performance of the widely-studied class of Max-Weight scheduling policies. As performance metric we use the notion of delay stability, i.e., whether the steady-state expected delay in a queue is finite or not. Max-Weight policies are known to have excellent stability properties, and also to achieve good delay performance under light-tailed trac. Classical results from queueing theory imply that heavy-tailed queues are delay unstable under any policy, so we focus on the potential impact of heavy tails on light-tailed queues. The main insight derived from this thesis is that the Max-Weight policy performs poorly in the presence of heavy tails, whereas a suitably modified version of Max-Weight achieves much better overall performance. More specifically: (i) under the Max-Weight scheduling policy, any light-tailed queue that conflicts (i.e., cannot be served simultaneously) with a heavy-tailed queue is delay unstable; (ii) delay instability may propagate to light-tailed queues that do not conflict with heavy-tailed queues. The latter can happen through a "domino effect," if a light-tailed queue conflicts with a queue that has become delay unstable because it conflicts with a heavy-tailed queue. The extent of this phenomenon depends on the arrival rates; (iii) under the parameterized Max-Weight- scheduling policy, all light-tailed queues are delay stable provided the -parameters are chosen suitably. On the methodological side, we show how fluid approximations can be combined with renewal theory in order to prove del, by Mihalis G. Markakis., Ph.D.