|
11. Algorithms in the FreeTime core
FreeTime is capable of automatically reacting to all new data entered by the participants of the meeting under its coordination. The schedule can thus be adopted with minimal manual operation and with less extra coordination between participants. This fundamental advantage of the product is based on the scheduling technology developed by LEDAS, in particular on the powerful LEDAS Scheduling Engine (LSE) incorporated into the FreeTime server.
After the user has made some changes in a schedule, he or she must synchronize them with the server, which calls the LSE computational kernel in order to check and resolve conflicts in a new schedule.
LSE is an independent scheduling engine, which is designed to be integrated into scheduling systems and tools of different complexity. Its interface functions allow to create a scheduling problem, which contains such entities as jobs (single or group), resources and resource pools, constraints (release/due dates, precedence relations) and assignments of resources on jobs. The engine works with these problems, trying to solve them with a variety of universal and specialized methods: a critical path algorithm, serial and stochastic serial methods, a conflict eliminator algorithm, branch and bound method, and so on.
The main purpose of LSE is to provide scalable and time-efficiency algorithms for resource-constrained project scheduling problems, which are NP-hard in the general case. Thus, LSE contains fast, optimal (i.e. providing true minimal completion time for the project), specialized algorithms for some particular cases and a special universal heuristic scheme for general case.
One of the fastest and most powerful methods is the serial scheme, which performs one-by-one scheduling of jobs using a greedy method with carefully developed efficient heuristics. Its modification - a stochastic serial method - allows one to get even more optimal solutions using a randomized heuristic-based way of output solution computation. All these methods are extremely fast - a problem with about 1000 jobs is solved in less than one second.
The main method used in FreeTime is an original conflict elimination method. It takes into account initial starting times on jobs, finds conflicts in this initial schedule (such as resource overloading or finishing a job after its due date) and locally shifts starting times to resolve these conflicts. It is very important that an output schedule is the closest to the initial schedule. That means that the solver will make as few changes as possible to resolve all conflicts and that the new schedule would not crucially change someone's plans. So, it provides excellent support for obtaining more "natural" solution. Another great advantage of this method is that it is very fast - its run-time and consumption of memory is quadratic with respect to the size of the initial problem.
| 
