A Diffusion Approximation for a Markovian Queue with Reneging

Consider a single-server queue with a Poisson arrival process and exponential processing times in which each customer independently reneges after an exponentially distributed amount of time. We establish that this system can be approximated by either a reflected Ornstein–Uhlenbeck process or a reflected affine diffusion when the arrival rate exceeds or is close to the processing rate and the reneging rate is close to 0. We further compare the quality of the steady-state distribution approximations suggested by each diffusion.     

Local search procedures for improving feasible solutions to the sequential ordering problem

Given a digraphG=(V, A), a weight for each node inV and a weight for each arc inA, the Sequential Ordering Problem (SOP) consists of finding a Hamiltonian path, such that a release date and a deadline for each node and precedence relationships among nodes are satisfied and a linear function is minimized. In our case, the objective function is the maximum cumulated potential of the nodes (also, the so-called makespan). The SOP has a broad range of applications, mainly in production planning and manufacturing systems. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, the nodes' weights are the processing time for the jobs, the arcs' weights are the setup times for two consecutive jobs, and the cumulated potential of a node is the completion time of a job. The goal is to produce a feasible scheduling of the jobs so that the makespan is minimized. We present an approximate algorithm for improving feasible solutions to the SOP. The algorithm is based on two local search-opt procedures to reduce the makespan while satisfying the time window (i.e. release date and deadline) and precedence constraints, for=3 and 4. The complexity of the algorithm isO(bn ⁴), wheren denotes the number of nodes andb is the average number of precedences per node. Extensive computational experience and implementation aspects are reported for very large-scale instances up to 3000 nodes and 9000 precedences. Experience with real-life cases is also reported.     

A Diffusion Approximation for a GI/GI/1 Queue with Balking or Reneging

Consider a single-server queue with a renewal arrival process and generally distributed processing times in which each customer independently reneges if service has not begun within a generally distributed amount of time. We establish that both the workload and queue-length processes in this system can be approximated by a regulated Ornstein-Uhlenbeck (ROU) process when the arrival rate is close to the processing rate and reneging times are large. We further show that a ROU process also approximates the queue-length process, under the same parameter assumptions, in a balking model. Our balking model assumes the queue-length is observable to arriving customers, and that each customer balks if his or her conditional expected waiting time is too large.     

Scheduling Multiclass Packet Streams to Minimize Weighted Loss

We consider the problem of scheduling an arriving sequence of packets at a single server. Associated with each packet is a deadline by which the packet must be scheduled. Each packet belongs to one of a predetermined set of classes, and each class has an associated weight value. The goal is to minimize the total weighted value of the packets that miss their deadlines. We first prove that there is no policy that minimizes this weighted loss for all finite arrival sequences of packets. We then present a class of greedy scheduling policies, called the current-minloss throughput-optimal (CMTO) policies. We characterize all CMTO policies, and provide examples of easily implementable CMTO policies. We compare CMTO policies with a multiclass extension of the earliest-deadline-first (EDF) policy, called EDF+, establishing that a subclass of CMTO policies achieves no more weighted loss than EDF+ for any traffic sequence, and at the same time achieves a substantial weighted-loss advantage over EDF+ for some traffic sequences – this advantage is shown to be arbitrarily close to the maximum possible achievable advantage. We also provide empirical results to quantify the weighted-loss advantage of CMTO policies over EDF+ and the static-priority (SP) policy, showing an advantage exceeding an order of magnitude when serving heavy-tailed aggregations of MPEG traces.     

Single-machine scheduling with positional due indices and positional deadlines

In this paper, we study single-machine scheduling problems with due dates, positional due indices, deadlines and positional deadlines. The scheduling criteria studied in this paper include the number of position-violated tasks, the weighted number of position-violated tasks, and the maximum positional lateness of tasks, by also combining with other traditional scheduling criteria. For each problem, we either provide a polynomial-time algorithm or present an NP-hardness proof.