Scheduling of Multi-Class Single-Server Queues Under Nontraditional Performance Measures

Abstract

We consider a multi-class production system without setups where many job classes share a single server. The traditional performance measure used for scheduling these systems is that of mean throughput time (i.e., the time spent in the system). However, mean throughput time may not be the only measure of importance in real systems. In particular, throughput time variance and the outer percentiles of throughput time may be equally important. We present two heuristics for scheduling multi-class single-server queues that are based on heavy-traffic analysis and perform well with respect to these nontraditional measures in a wide variety of cases. An approximation is given for the throughput time distribution under both scheduling methods.

Keywords

This publication has 10 references indexed in Scilit:

Job flow control in assembly operations
IEEE Transactions on Automatic Control, 1999
A Practical Scheduling Method for Multiclass Production Systems with Setups
Management Science, 1999
Dynamic Scheduling with Convex Delay Costs: The Generalized $c|mu$ Rule
The Annals of Applied Probability, 1995
Scheduling Manufacturing Systems of Re-Entrant Lines
Published by Springer Nature ,1994
Scheduling Networks of Queues: Heavy Traffic Analysis of a Bi-Criteria Problem
Published by Springer Nature ,1994
Due-Date Setting and Priority Sequencing in a Multiclass M/G/1 Queue
Management Science, 1991
M/G/c Queueing Systems with Multiple Customer Classes: Characterization and Control of Achievable Performance Under Nonpreemptive Priority Rules
Management Science, 1988
Dynamic, Non-Preemptive Priority Queues with General, Linearly Increasing Priority Function
Operations Research, 1985
Refining diffusion approximations for queues
Operations Research Letters, 1982
Minimising Waiting Time Variance in the Single Machine Problem
Management Science, 1977