Algorithm Definitions

There are several schedule deconfliction algorithms that can be used to find a schedule solution. In all cases, the deconfliction algorithms will attempt to assign start times, durations, and resource assignments to each task.

To change the deconfliction algorithm, select Schedule -> Select Algorithm from the Menu Bar.

For a detailed discussion of the algorithms, see The Optwise Corporation Deconfliction Scheduler Algorithms (as used in STK Scheduler).

The above link requires a free version of Adobe Acrobat Reader. Click on the link below to download.

http://www.adobe.com/products/acrobat/main.html

The available deconfliction algorithms are:

One-Pass Algorithm

The One-Pass algorithm makes a single pass through the task list assigning task start times to the earliest possible time within a task timeslot. The order in which tasks and task timeslots are considered is dependent primarily on the task priority, and secondarily on the timeslot desirability. Tasks with the same priority are taken in list order. Timeslots with the same desirability are taken in list order. One-Pass is the fastest of the algorithms, but implicitly assumes that task priority, timeslot desirability, and scheduling tasks as early as possible are important. Decisions made early in the task list cannot be undone to improve later performance.

Sequential Algorithm

The sequential algorithm is based on the One-Pass algorithm but uses the timeslot start time as its secondary task consideration sorting order (instead of timeslot desirability). This seemingly minor change makes a major improvement in solution quality for scheduling problems that include repetitive consumable resource depletion and replenishment. An example of this type of problem is satellite imagery collection planning where images are stored on-board a recorder and later downlinked to ground stations to free recorder space for additional collections.

Multi-Pass Algorithm

The Multi-Pass algorithm uses the core deconfliction processing routines in the One-Pass algorithm, but in each of its multiple passes modifies the task order and the timeslot order prior to each assignment pass. A set of expert system rules is used to generate the possible task and time order lists. Each pass is graded based on a Figure Of Merit (FOM) and the best solution is returned. This algorithm will require more time than the One-Pass algorithm since it has to run through the One-Pass algorithm multiple times. The actual number of times it is run is based on the complexity of the problem. The multi-pass algorithm will usually produce better result than the one-pass algorithm.

Neural Network Algorithm

The Neural algorithm uses a competition model in which all of the possible assignment possibilities compete to be assigned subject to the constraints just as many potential bidders compete for products at an auction. In this unique algorithm, the order of the task and timeslots are unimportant, but task priority and timeslot desirability affect the probability that a particular assignment will be chosen through the use of the Figure Of Merit. Since the algorithm does not bias the solution toward earliest time, a repair algorithm is run at the end to move tasks to the earliest possible time and then tests to see if any additional unassigned tasks can be added. Multiple runs can generate a family of solutions.

Random Algorithm

The Random Algorithm searches for solutions in an unbiased manner to seed a random solution (and available options) and uses a repair algorithm to repair it. While the initial random solution will probably be invalid (in violation of constraints and having tasks with duration far less than desired) the repaired schedule will be valid. This algorithm's strength is that it is unbiased and can find solutions that cannot be predicted by rules. It is useful when a very unusual Figure Of Merit is used to grade the performance. While constraints are obeyed, they are not used to help fine the best solution.

Squeaky-Wheel Algorithm

The concept behind a Squeaky-Wheel algorithm is straight forward. Multiple runs of a solver are done. After each run, tasks that are not assigned are noted and a credit is calculated that is used to bias the order in which candidate tasks (and task slots) are searched of subsequent runs. Tasks that are easy to assign will tend to fall later than tasks that are never assigned (Squeaky-Wheel tasks) as more and more runs are done. The Squeaky-Wheel algorithm uses the same basic search method as Random Algorithm. The difference is that after each run, instead of randomly choosing the slot order, the new slot order is biased by how many times the task has been missed.

Load-Leveling Algorithm

The Load-Leveling algorithm is a special algorithm based on the One-Pass Algorithm with a desired goal of equally distributing assignment time amongst all the tasks in a schedule. Unlike most other algorithms, the Load-Leveling algorithm does not have a FOM-driven quality checker. Instead, tasks that have received little assignment time during either the initial pass or expansion phase are given a higher weighting. This has the effect of reducing the bias that other algorithms may have when deciding between pairs of tasks where one task may have a longer or earlier timeslot.

Greedy Algorithm

The Greedy algorithm orders timeslots by the FOM value as opposed to their individual timeslot score. As the schedule changes, the FOM score is recomputed and the timeslots are resorted accordingly. Similar to the One-Pass algorithm, individual tasks are scheduled according to their task priority . The FOM can be configured in the Schedule Properties. Information on how to edit the FOM calculation, as well as variable definitions can be found here.

Algorithm Builder

The Algorithm Builder allows you to create a custom algorithm based on a variety of customizable criteria. The Algorithm Builder can generate and save an XML file containing the user-specified options. Click Go to obtain a schedule solution using your custom algorithm.