Optimal non-preemptive scheduling with time-varying non-observable channels

We investigate how to allocate resources when the capacity of the channel fluctuates over time, and when the scheduler does not have full information regarding the actual state of the system. The main motivation comes from communication networks in which the available capacity might evolve over time. A nice introduction to the role of information in scheduling, mostly in the context of stability, is provided in [1]. This paper shows how the problem can be cast as a Partially Observable MDP (POMDP), and observes that in full generality there is very little that can be said. We thus set out to study a simple, yet interesting, instance of the problem in which the channel capacity can only take good values, ON, or bad values OFF. When the channel is ON, data can be transmitted through the channel, but not when it is OFF. Even though the scheduler does not have access to the state of every channel, it does observe successful transmissions.