Requirements for an optimal service ordering policy

Lemma 4: An optimal policy is Markov

(independent of both past and future arrivals)

Follows because service times and interarrival times are exponential.