I'm reviewing different algorithms to solve a scheduling problem and was hoping someone with a better breath in the area might help me focus on the right class of algorithms.
Basically the problem is as follows. I have a large number of "events" during a day that are pre-scheduled at particular times. These times are not static and could be delayed and thus shift backward in time either by a small stochastic amount or by a larger amount based on the cumulative delay of the events preceding it. The schedule is continuously updated throughout the day to reflect these delays.
I need to schedule
N "observers" to monitor these events. They need to start watching an event a little bit before the current estimate of the start time (say
z minutes). They can stop watching once the event occurs. They can watch up to a maximum of
M>=1) events simultaneously. Each observer might have a variable assigned
The events have a particular value and I want to schedule the observers to minimize the potential total value of missed or unobserved events.
The problem struck me as being similar to job shop scheduling, but not quite the same. Any suggestions for algorithms, problem descriptions with their variants, etc that would help in figuring out how best to solve this would be appreciated.