Scheduling jobs on heterogeneous processors

We consider the problem of schedulingn jobs nonpreemptively onm processors to minimize various weighted cost functions of job completion times. The time it takes processorj to process a job is distributed exponentially with rate parameter _j , independent of the other processors. Associated with jobi is a weightw _i . There are no precedence constraints and any job may be processed on any processor. Assume that _{1 2}...µ _m andw ₁w ₂...w _n . Then for certain weighted cost functions, the optimal policy is such that the processors can be partitioned into setsS ₁, ...,S _n+1 such that if the fastest available processor is in setS _i ,i=1, ...,n, then jobi should be assigned to it, and if it isS _n+1, it will never be used. After each assignment the jobs are renumbered (so that jobi+1 becomes jobi if jobi is assigned to a processor). The partitioning is independent of the job weights and the states (busy or idle) of the processors. The optimal policy can be determined in at most max {m, n} steps. If all the weights are identical, the optimal policy reduces to a simple threshold rule such that a job should be assigned to the fastest available processor, sayj, if there are more thanK _j jobs waiting.K _j will depend on ₁, ..., _j but not on _j+1, ...,µ _m . The optimal policy is also individually optimal in the sense that it minimizes the cost for each jobi subject to the constraint that processors will first be offered to the jobs in the order 1, 2, ...,n.We explicitly characterize the optimal policy for several specific examples of cost functions, such as weighted flow time, weighted discounted flowtime, and weighted number of tardy jobs.     

Staffing decisions for heterogeneous workers with turnover

In this paper we consider a firm that employs heterogeneous workers to meet demand for its product or service. Workers differ in their skills, speed, and/or quality, and they randomly leave, or turn over. Each period the firm must decide how many workers of each type to hire or fire in order to meet randomly changing demand forecasts at minimal expense. When the number of workers of each type can by continuously varied, the operational cost is jointly convex in the number of workers of each type, hiring and firing costs are linear, and a random fraction of workers of each type leave in each period, the optimal policy has a simple hire- up-to/fire-down-to structure. However, under the more realistic assumption that the number of workers of each type is discrete, the optimal policy is much more difficult to characterize, and depends on the particular notion of discrete convexity used for the cost function. We explore several different notions of discrete convexity and their impact on structural results for the optimal policy.     

Understanding the marginal impact of customer flexibility

We study the marginal impact of customer flexibility in service systems. We consider a queueing system with multiple parallel servers, in which a proportion of customers are flexible and can go to any server, while the remainder require service at a particular server. We show that the stationary expected waiting time is decreasing and convex in the proportion of flexible customers. We also show, for a related Inventory Model, in which servers are never idle and can build up inventory, that convexity holds in a strong sample-path sense. Our results reinforce the idea that a little flexibility goes a long way.     

Optimal control of tandem reentrant queues

We consider optimal policies for reentrant queues in which customers may be served several times at the same station. We show that for tandem reentrant queues the last-buffer first-served (LBFS) policy stochastically maximizes the departure process. This revised version was published online in June 2006 with corrections to the Cover Date.     

Expulsion and scheduling control for multiclass queues with heterogeneous servers

We consider an M/M/2 system with nonidentical servers and multiple classes of customers. Each customer class has its own reward rate and holding cost. We may assign priorities so that high priority customers may preempt lower priority customers on the servers. We give two models for which the optimal admission and scheduling policy for maximizing expected discounted profit is determined by a threshold structure on the number of customers of each type in the system. Surprisingly, the optimal thresholds do not depend on the specific numerical values of the reward rates and holding costs, making them relatively easy to determine in practice. Our results also hold when there is a finite buffer and when customers have independent random deadlines for service completion.     

Confirmation of gentamicin and neomycin in milk by weak cation-exchange extraction and electrospray ionization/ion trap tandem mass spectrometry

A new procedure for the confirmation of two aminoglycoside antibiotics in milk was developed and validated. This work is among the early applications of ion trap mass spectrometry for regulatory methodology, and it incorporates a novel weak cation-exchange extraction. The procedure was validated for the confirmation of both gentamicin and neomycin at 30 ng ml(-1) and above. Milk is first treated with acid and centrifuged. The supernate, excluding the fat layer, is buffered with sodium citrate to neutral pH. The extract is applied to a weak cation-exchange solid-phase extraction column. Aminoglycosides are eluted with acidified methanol. Following separation by ion-pair liquid chromatography, analytes are ionized with an electrospray interface. Protonated molecular ions are selectively stored in an ion trap mass spectrometer, then collisionally dissociated to yield unique product ion spectra. Confirmation is based on matching spectral responses between samples and comparison standards consisting of a bona fide standard spiked into control extracts. Method performance was demonstrated with replicate samples of control milk, fortified milk, and milk containing incurred residues of each compound.     

On the Gittins index in the M/G/1 queue

For an M/G/1 queue with the objective of minimizing the mean number of jobs in the system, the Gittins index rule is known to be optimal among the set of non-anticipating policies. We develop properties of the Gittins index. For a single-class queue it is known that when the service time distribution is of type Decreasing Hazard Rate (New Better than Used in Expectation), the Foreground–Background (First-Come-First-Served) discipline is optimal. By utilizing the Gittins index approach, we show that in fact, Foreground–Background and First-Come-First-Served are optimal if and only if the service time distribution is of type Decreasing Hazard Rate and New Better than Used in Expectation, respectively. For the multi-class case, where jobs of different classes have different service distributions, we obtain new results that characterize the optimal policy under various assumptions on the service time distributions. We also investigate distributions whose hazard rate and mean residual lifetime are not monotonic.     

Scheduling in Multiclass Networks with Deterministic Service Times

We consider general feed-forward networks of queues with deterministic service times and arbitrary arrival processes. There are holding costs at each queue, idling may or may not be permitted, and servers may fail. We partially characterize the optimal policy and give conditions under which lower priority should be given to jobs that would be delayed later in the network if they were processed now.