A Markov-Decision-Chain Approach to a Stochastic Assignment Problem

This paper discusses a problem where jobs of random quality, or importance, arrive at random times and must be done by one of a fixed set of men on hand. The men can all complete any job in an exponential amount of time, with mean l / u , but the men are of different known qualities. Once a man finishes a job he again becomes available to do future jobs. If a man of quality p is assigned to do a job whose value is observed to be x , a reward r ( p , x ) is received. Also a cost of c ( p ) is incurred per unit time that a man of quality p is kept idle. The decision maker must observe the values of the incoming jobs and assign them to available men so as to maximize expected reward per unit time. The problem is set into the framework of a G / M / n queue with a possibly limited waiting room, and the optimization is done by techniques of Markov decision analysis.