The impact of sequencing policies on the mean flow time of single server queues

Abstract

In systems with nite resources, scheduling may take signi cant time and this may a ect the performance of the system. In this study, we are interested in the time value of optimizing a schedule. To this end, we consider a single server queue with an external scheduling mechanism and one by one Poisson arrivals. Processing times of the jobs are independent random variables following an exponential distribution. Jobs are sequenced by the scheduler for another independent exponential time following Shortest Processing Time (SPT) rule which is used here as a proxy for a general optimal scheduling rule. Two trigger mechanisms, arrivals and departures, to start a sequencing are o ered. In addition to the trigger mechanisms, three rules are considered. The rst one is freezing the server during sequencing. The second one is continuing processing previously sequenced jobs and the last one is continuing processing until the system is empty. In order to investigate the performance of the system with respect to mean ow time of jobs, the systems are modeled as Markov processes under each policy. To imitate an SPT queue, state dependent service rates approach is used. In numerical results part, the optimal sequencing policies under di erent system parameters are determined.