-
Notifications
You must be signed in to change notification settings - Fork 4
Scheduling Algorithms
Currently there are four scheduling algorithms implemented. These range from simple greedy algorithms to evolutionary algorithms. All but the EFT-Greedy will create a schedule that meets the objective functions goal.
The EFT-Greedy (Earliest Finish Time) is the most basic scheduling algorithm. It selects the contact window with the earliest finish time and highest priority to be included in the schedule. In each step other possible contacts will be eliminated if they are of a lower priority or the finish time is at a later point. This scheduler does not schedule by the objective function that the others use.
The Greedy schedule works in a similar fashion as the EFT-Greedy. It selects at a given point the one contact window with the most fitness value gain. This selected contact window will then be added into the solution and the next contact is then selected. However this algorithm cannot see beyond its current solution point and might select a contact window that in the long run will lower the overall fitness value of the solution.
An iterative approach to the problem is the Hill-Climber algorithm. This scheduler will start either from an empty solution or a random generated one and then trys to optimize it step by step. This is done by going through the schedule and checking if there exists other contact windows that will produce a better solution then the current one. Step by step the solution is thus optimized depending on the selected objective function.
Finally there is the genetic algorithm. This scheduler will use the concept of evolution to create and optimize a solution. At the start multiple starting solutions are generated randomly. Each one will be evaluated and the one solution with the lowest fitness value will be discarded with a copy of the one with the highest. Two solutions are then selected and randomly combined to produce two children solutions which will replace their parents. A random mutation will then be run over each one of them that will include or exclude contact windows. This process is repeated until a sufficient good result is found.