'Scheduling repeating events in a timeframe
I have a set of events that I am trying to schedule in a timeframe. The events are synchronous (once started, cannot be paused and must run to completion). Furthermore, each event has some parameters that must be respected by the schedule:
- a duration
- a target run frequency (an event cannot happen before its target run frequency, the frequency must be > the duration, and the scheduler gives priority to events further past their target frequency)
- a minimum time period which must separate events of any kind
I am trying to write a python program that can find a feasible schedule (not necessarily an optimal schedule, I'm fine with a greedy algorithm). As an example, let's say I have a timeframe from t=0 to t=100.
event1has a duration of 20 seconds, target frequency of 40 seconds, and minimum separation period of 10s.event2has a duration of 10 seconds, has a target frequency of 30 seconds, and a minimum separation period of 10s.
A feasible schedule output could be:
event1 0->20 // either event1 or event2 could have been scheduled here. event1 is runnable again at t=40
event2 30->40 // event2 is the only runnable task at this time, the minimum separation period has expired. event2 is runnable again at t=60
event1 50->70 // event1 becomes runnable, the minimum separation period has expired
event2 80->90 // event2 is runnable after the minimum separation period
I've been trying to implement this by using a greedy algorithm, starting at t=0 and finding a runnable task at each stage, then moving t forward by some amount. The trouble I'm having is calculating how far ahead to move t. Is there any libraries I could use for something like this instead? If not, how can I implement an algorithm for this?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
