Flow-times in an M/G/1 Queue under a Combined Preemptive/Non-preemptive Priority Discipline.: Scheduled Waiting Time on Single Track Railway Lines

Abstract

A priority based rule for use during the process of scheduling trains oper- ating on a single track railway line was proposed by the Norwegian railway operator and owner, Jernbaneverket. The purpose of this study is to inves- tigate the effect of the suggested scheduling rule on the scheduled waiting times suffered by trains operating on a segment of the railway line. It is shown that the scheduling rule, under certain limiting assumptions, can be studied in the setting of queuing theory and that it has properties in common with a theoretical priority discipline combining two well docu- mented priority rules. The main part of this study is the development and analysis of a threshold based, combined preemptive/non-preemptive priority discipline. Under the combined discipline, preemptions are allowed during the early stage of processing only. Theoretical expressions for flow-times of jobs passing through the queuing system are reached through detailed studies of the non-preemptive and the preemptive priority discipline. The relationship between the suggested priority based scheduling rule and the theoretical, combined priority discipline is finally illustrated by sim- ulations. When adjusted for actual time spent by trains on traversing the line segment, the steady state solution for flow-times obtained from queuing theory yields an accurate expression for the trains average scheduled wait- ing times. The scheduling problem can in fact be modeled accurately by an M/G/1 queue under the combined priority discipline.