STOCHASTIC SCHEDULING GAMES WITH MARKOV DECISION ARRIVAL PROCESSES

In Hordijk and Koole 1,2!, a new type of arrival process, the Markov Decision Arrival Process (MDAP), was introduced, which can be used to model certain dependencies between arrival streams and the system at w hich the arrivals occur. This arrival process was used to solve contro l problems with several controllers having a common objective, where t he output from one controlled node is fed into a second one, as in tan dems of multi-server queues. In the case that objectives of the contro llers are different, one may choose a min-max (worst case) approach wh ere typically a controller tries to obtain the best performance under the worst possible (unknown) strategies of the other controllers. We u se the MDAP to model such situations, or situations of control in an u nknown environment. We apply this approach to several scheduling probl ems, including scheduling of customers and scheduling of servers. We c onsider different information patterns including delayed information. For all these models, we obtain several structural results of the opti mal policies.