Search for: All records

Abstract Priority queues have long been used to increase revenue by exploiting the fact that time-sensitive customers are willing to pay for shorter waiting times. This fact begs the question: Can one make even more revenue by relaxing the strictness of the priority policy? This paper answers this question under the unobservable queue setting, where customers are heterogeneous in their time-sensitivity; specifically the time-sensitivity of customers is allowed to follow an arbitrary distribution. In this paper, we prove necessary and sufficient conditions under which partial priority can increase the revenue. Specifically, we find a surprising result: Although partial priority offers much more flexibility than strict priority, partial priority only increases revenue if there are two additional constraints on the service provider, one setting a maximum price and the other setting a maximum waiting time. In the absence of either of these constraints, we prove that strict priority maximizes revenue. Finally, in situations where partial priority increases the revenue, we analytically characterize the amount of improvement. 

Abstract In practice, the cost of delaying a job can grow as the job waits. Such behavior is modeled by the time-varying holding cost (TVHC) problem, where each job’s instantaneous holding cost increases with its current age (a job’s age is the time since it arrived). The goal of the TVHC problem is to find a scheduling policy that minimizes the time-average total holding cost across all jobs. However, no optimality results are known for the TVHC problem outside of the asymptotic regime. In this paper, we study a simple yet still challenging special case: A two-class M/M/1 queue in which class 1 jobs incur a non-decreasing, time-varying holding cost and class 2 jobs incur a constant holding cost. Our main contribution is deriving the first optimal (non-decreasing) index policy for this special case of the TVHC problem. Our optimal policy, called LookAhead, stems from the following idea: Rather than considering each job’scurrentholding cost when making scheduling decisions, we should look at their cost someXtime into the future, where thisXis intuitively called the “lookahead amount. This paper derives that optimal lookahead amount. 

Scheduling a stream of jobs whose holding cost changes over time is a classic and practical problem. Specifically, each job is associated with a holding cost (penalty), where a job's instantaneous holding cost is some increasing function of its current age (the time it has spent in the system since its arrival) and its class. The goal is to schedule the jobs to minimize the time-average total holding cost across all jobs. 

Priority queues are well understood in queueing theory. However, they are somewhat restrictive in that the low-priority customers suffer far greater waiting times than the highpriority customers. In this short paper, we introduce a novel generalization of a two-class priority queue, which we call Hybrid. We prove that Hybrid has a much broader achievability region than strict priority, allowing for a much greater range of waiting time pairs. We demonstrate settings where this new flexibility can increase the revenue obtained by a service system (like airport TSA) selling priority. 

Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. Essentially all of the theoretical work on multiserver-job systems focuses on maximizing utilization, with almost nothing known about mean response time. In simpler settings, such as various known-size single-server-job settings, minimizing mean response time is merely a matter of prioritizing small jobs. However, for the multiserver-job system, prioritizing small jobs is not enough, because we must also ensure servers are not unnecessarily left idle. Thus, minimizing mean response time requires prioritizing small jobs while simultaneously maximizing throughput. Our question is how to achieve these joint objectives. We devise the ServerFilling-SRPT scheduling policy, which is the first policy to minimize mean response time in the multiserver-job model in the heavy traffic limit. In addition to proving this heavy-traffic result, we present empirical evidence that ServerFilling-SRPT outperforms all existing scheduling policies for all loads, with improvements by orders of magnitude at higher loads. Because ServerFilling-SRPT requires knowing job sizes, we also define the ServerFilling-Gittins policy, which is optimal when sizes are unknown or partially known. 

New computing and communications paradigms will result in traffic loads in information server systems that fluctuate over much broader ranges of time scales than current systems. In addition, these fluctuation time scales may only be indirectly known or even be unknown. However, we should still be able to accurately design and manage such systems. This paper addresses this issue: we consider an M / M /1 queueing system operating in a random environment (denoted M / M /1( R )) that alternates between HIGH and LOW phases, where the load in the HIGH phase is higher than in the LOW phase. Previous work on the performance characteristics of M / M /1( R ) systems established fundamental properties of the shape of performance curves. In this paper, we extend monotonicity results to include convexity and concavity properties, provide a partial answer to an open problem on stochastic ordering, develop new computational techniques, and include boundary cases and various degenerate M / M /1( R ) systems. The basis of our results are novel representations for the mean number in system and the probability of the system being empty. We then apply these results to analyze practical aspects of system operation and design; in particular, we derive the optimal service rate to minimize mean system cost and provide a bias analysis of the use of customer-level sampling to estimate time-stationary quantities.