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

In systems with finite resources, scheduling may take significant time and this may affect 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 offered. In addition to the trigger mechanisms, three rules are considered. The first 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 different system parameters are determined.