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 (M>=1) events simultaneously. Each observer might have a variable assigned M.

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.


My thoughts are these:

One can describe the problem as: Let $ I $ be the set of intervals of the events (from their start to their end).

You can then put, $ I = J_1 \cup J_2 \cup \ldots J_n $, subject to $ |J_k| \leq m $. The $ k $th observer will then get the set of events, $ J_k $. Maximize $ |A \cap B \cap \ldots| $ for $ A, B, \ldots \in J $.

I think this can be solved through a simple greedy algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.