Grid scheduling with NBU service times

In the highly unpredictable environment of grid computing, it often makes sense to replicate the same job on several of the available servers. We prove that never replicating is optimal for a heterogeneous multi-server system in a random environment when service times are New Better than Used.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

Asymptotics of stochastic networks with subexponential service times

We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i ₀ ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i ₀ asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i ₀. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered. This revised version was published online in June 2006 with corrections to the Cover Date.     

The orienteering problem with stochastic travel and service times

In this paper, we introduce a variant of the orienteering problem in which travel and service times are stochastic. If a delivery commitment is made to a customer and is completed by the end of the day, a reward is received, but if a commitment is made and not completed, a penalty is incurred. This problem reflects the challenges of a company who, on a given day, may have more customers than it can serve. In this paper, we discuss special cases of the problem that we can solve exactly and heuristics for general problem instances. We present computational results for a variety of parameter settings and discuss characteristics of the solution structure.     

Dynamic pricing and scheduling in a multi-class single-server queueing system

This paper investigates an optimal sequencing and dynamic pricing problem for a two-class queueing system. Using a Markov Decision Process based model, we obtain structural characterizations of optimal policies. In particular, it is shown that the optimal pricing policy depends on the entire queue length vector but some monotonicity results prevail as the composition of this vector changes. A numerical study finds that static pricing policies may have significant suboptimality but simple dynamic pricing policies perform well in most situations.     

具有服务等级的两台同型机实时在线排序

考虑具有服务等级的两台同型机在线排序问题, 其中工件带有到达时间, 目标为最小化最大完工时间, 设计了竞争比为\frac{7}{4}的在线算法.     

Optimal stochastic scheduling of two interconnected queues with varying service rates

We consider two-stage tandem queueing systems attended by two specialized and one flexible server, where all servers have time varying rates. Assuming exponential processing times and linear holding costs, we derive properties of server allocation policies that minimize expected costs over an infinite time horizon.     

Johnson’s problem with stochastic processing times and optimal service level

Theoretical results about Johnson’s problem with stochastic processing times are few. In general, just finding the expected makespan of a given sequence is already difficult, even for discrete processing time distributions. Furthermore, to obtain optimal service level we need to compute the entire distribution of the makespan. Therefore the use of heuristics and simulation is justified. We show that pursuing the minimal expected makespan by two heuristics is empirically effective for obtaining excellent overall distributions. The first is to use Johnson’s rule on the means. The second is based on pair-switching and converges to some known stochastically optimal solutions when they apply. We show that the first heuristic is asymptotically optimal under mild conditions. We also investigate the effect of sequencing on the makespan variance.     

Dynamic scheduling for switched processing systems with substantial service-mode switching times

Switched Processing Systems (SPS) represent canonical models for many communication and computer systems. Over the years, much research has been devoted to developing the best scheduling policies to optimize the various performance metrics of interest. These policies have mostly originated from the well-known MaxWeight discipline, which at any point in time switches the system into the service mode possessing “maximal matching” with the system state (e.g., queue-length, workload, etc.). However, for simplicity it is often assumed that the switching times between service modes are “negligible”—but this proves to be impractical in some applications. In this study, we propose a new scheduling strategy (called the Dynamic Cone Policy) for SPS, which includes substantial service-mode switching times. The goal is to maximize throughput and maintain system stability under fairly mild stochastic assumptions. For practical purposes, an extended scheduling strategy (called the Practical Dynamic Cone Policy) is developed to reduce the computational complexity of the Dynamic Cone Policy and at the same time mitigate job delay. A simulation study shows that the proposed practical policy clearly outperforms another throughput-maximizing policy called BatchAdapt, both in terms of the average and the 95th percentile of job delay for various types of input traffic.     

Ensuring service levels in routing problems with time windows and stochastic travel times

In the stochastic variant of the vehicle routing problem with time windows, known as the SVRPTW, travel times are assumed to be stochastic. In our chance-constrained approach to the problem, restrictions are placed on the probability that individual time window constraints are violated, while the objective remains based on traditional routing costs. In this paper, we propose a way to offer this probability, or service level, for all customers. Our approach carefully considers how to compute the start-service time and arrival time distributions for each customer. These distributions are used to create a feasibility check that can be “plugged” into any algorithm for the VRPTW and thus be used to solve large problems fairly quickly. Our computational experiments show how the solutions change for some well-known data sets across different levels of customer service, two travel time distributions, and several parameter settings.     

Dynamic multi-appointment patient scheduling for radiation therapy

Seeking to reduce the potential impact of delays on radiation therapy cancer patients such as psychological distress, deterioration in quality of life and decreased cancer control and survival, and motivated by inefficiencies in the use of expensive resources, we undertook a study of scheduling practices at the British Columbia Cancer Agency (BCCA). As a result, we formulated and solved a discounted infinite-horizon Markov decision process for scheduling cancer treatments in radiation therapy units. The main purpose of this model is to identify good policies for allocating available treatment capacity to incoming demand, while reducing wait times in a cost-effective manner. We use an affine architecture to approximate the value function in our formulation and solve an equivalent linear programming model through column generation to obtain an approximate optimal policy for this problem. The benefits from the proposed method are evaluated by simulating its performance for a practical example based on data provided by the BCCA.     

A robust optimization approach to dispatching technicians under stochastic service times

We consider the problem of dispatching technicians to service/repair geographically distributed equipment. This problem can be cast as a vehicle routing problem with time windows, where customers expect fast response and small delays. Estimates of the service time, however, can be subject to a significant amount of uncertainty due to misdiagnosis of the reason for failure or surprises during repair. It is therefore crucial to develop routes for the technicians that would be less sensitive to substantial deviations from estimated service times. In this paper we propose a robust optimization model for the vehicle routing problem with soft time windows and service time uncertainty and solve real-world instances with a branch and price method. We evaluate the efficiency of the approach through computational experiments on real industry routing data.     

Single-machine scheduling with time-and-resource-dependent processing times

We consider single-machine scheduling problems in which the processing time of a job is a function of its starting time and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We show that the problems remain polynomially solvable under the proposed model.     

Dynamic overbooking scheduling system to improve patient access

Patient no-show has long been a recognized problem in modern outpatient health-care delivery systems. The common impacts are reduced clinic efficiency and provider productivity, wasted medical resources, increased health-care cost and limited patient access to care. The main goal of this research is to develop an effective dynamic overbooking policy into any scheduling system that accounts for the predictive probability of no-shows for any given patient. This policy increases the quality of patient care in terms of wait time and access to care while minimizing the clinic's costs. This proposed model is also illustrated to be more cost-effective than overbooking patients evenly throughout a clinic session. This paper also suggests that overbooking should be performed at better patient flow and higher no-show rate so that the costs are minimized. Consequently, this research improves the outpatient experience for both patients and medical providers.     

Optimal patient and personnel scheduling policies for care-at-home service facilities

In this paper we study the problem of personnel planning in care-at-home facilities. We model the system as a Markov decision process, which leads to a high-dimensional control problem. We study monotonicity properties of the system and derive structural results for the optimal policy. Based on these insights, we propose a trunk reservation heuristic to control the system. We provide numerical evidence that the heuristic yields close to optimal performance, and scales well for large problem instances.     

Single machine scheduling with forbidden start times

This paper addresses a single machine scheduling problem in which the following simple constraint is added: a set of time slots is forbidden for starting a task, that is no task can start at any forbidden time point. We show that the single machine problem with makespan minimization is strongly -complete and we give polynomial algorithms to solve the problems with a small number of forbidden start times.      

Single-machine scheduling problems with past-sequence-dependent setup times

This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlog n) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a “learning” environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects.     

A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times

This paper describes a generalized variable neighborhood search heuristic for the Capacitated Vehicle Routing Problem with Stochastic Service Times, in which the service times at vertices are stochastic. The heuristic is tested on randomly generated instances and compared with two other heuristics and with an alternative solution strategy. Computational results show the superiority and effectiveness of the proposed heuristic.     

Single-machine scheduling with time window-dependent processing times

In the one-machine scheduling problems analysed in this paper, the processing time of a job depends on the time at which the job is started. More precisely, the horizon is divided into time windows and with each one a coefficient is associated that is used to determine the actual processing time of a job starting in it. Two models are introduced, and one of them has direct connections with models considered in previous papers on scheduling problems with time-dependent processing times. Various computational complexity results are presented for the makespan criterion, which show that the problem is NP-hard, even with two time windows. Solving procedures are also proposed for some special cases.