Algorithm Builder

Algorithm Builder

The Algorithm Builder allows you to create a custom algorithm based on a variety of customizable criteria. It provides up to three sort steps. For each sort step, you can specify Prior Groups, Expand All Tasks At End, Expand After Each Try, a search step (ordered, neural, or DS1MPS), a number of tries, a time limit, and end-of-trial output (text best, XML best, text last, XML last). The Algorithm Builder can generate and save an XML file containing your specified options. Click Go to obtain a schedule solution using your custom algorithm.

The available algorithm options are as follows:

  • Number of Sort Levels
  • Sort Types (per level)
  • Algorithm Modifiers
  • Search Method
  • Search Options

Initial Parameters

The algorithm Builder allows you to use existing algorithms as starting point for new custom algorithms. To load an existing algorithm's parameters and options, select the algorithm by name in the "Initialize Parameters to Primary Algorithm (Optional)" area of the Algorithm Builder UI.

Sort Parameters

The Sort Parameters allows you to specify how many levels of sorts are to be performed (1, 2, or 3) or not at all (none). Additionally, each Sort level can be set to use different attributes to sort on. A or D indicates an ascending or descending sort. in all cases the sort is done on the timeslots in a particular priority group (timeslots with the same priority value).

Non-Random Sort Types:

  • List A/D: Sorts timeslots based on the order that they were created. This applies to manually created tasks and tasks contained in a command ingest file. Task timeslots, or profiles, remain in list order as the default.
  • Priority A/D: Sorts timeslots by priority. In most cases it is better to use priority groups instead of Priority A.
  • EarlyStart A/D: Sorts timeslots by the start time of the timeslot. Timeslots with the earliest starts are sorted to the top of the list.
  • LatestStart A/D: Sorts timeslots by the stop time of the timeslot. Timeslots with the latest stop are sorted to the top of the list.
  • Desire A/D: Timeslots are sorted by desirability. For example, if Sort1(desireA) is used, timeslots are sorted by desirability (ascending), but if two timeslots have the same desirability then the original timeslot list order is used.
  • Slack A/D: Timeslots are sorted based on the total slack. Slack is the timeslot duration minus the task minimum duration.
  • Slack Ds1: This sort provides backwards compatibility with the first generation (pre-2008) algorithm. It is assumed that there is only one priority group and computes a total slack for all timeslots associated with a task. It is used as part of the original MPS algorithm.
  • TaskSlotTime A/D: Sorts based on the sum total of timeslot durations in a particular task. Ascending prioritizes lower total duration, descending prioritizes higher total duration.
  • SlotDur A/D: Sorts timeslots based on the duration of the slot. Ascending prioritizes lower duration, descending prioritizes higher duration.
  • FOM A/D: Sorts timeslots based on their Figure of Merit. Ascending prioritizes higher FOM score, descending prioritizes lower FOM score.

Random Options

The following random sort options should always be the last sort parameter. Instead of sorting, these options will randomize the timeslots that are equal based on the prior sort option.

Random Sort Options:

  • Random: Randomizes timeslot selection order within a priority group.
  • RanTask: Sorts timeslots based on an initial randomize task order.
  • RotateProfile: Sorts timeslots by rotating the chosen possibility order for each task.
  • RanProfile: Randomizes timeslots on an initial randomized possibility order.
  • RanProfilePerTask: Sorts timeslots using a randomize possibility order based on the possibilities for each particular task.
  • RanSlot: Same as random.
  • RanDS1: RanDs1 mimics a method from the pre-2008, which was used as part of the MPS algorithm. It randomizes the first slot chosen for a task, but leaves the remaining timeslots in list order.

If multiple sorts are used, they are nested within each level. For example, an algorithm with Sort1 being DesireD and Sort2 being earlyStartD, a schedule with 4 tasks (3 with desirability of 80, and 1 with a desirability of 70), the 3 "80"s will be considered first. Within that group of 3, the task with the earliest start time will be considered first, then the next start time, and then finally the latest of the start times. Only after these 3 tasks have been considered will the 4th task with a desirability of 10 be considered for scheduling.

Algorithm Modifiers

Modifier Types:

  • Expand After Each Task: After each task assignment, an attempt is made to expand the single task to full desired duration.
  • Expand After Each Try: After each try in a trial the routine that attempts to expand all tasks as described above. This is done before FOM calculation that is used to choose the best try.
  • Expand All Tasks At End: The expansion is attempted after all tasks have been assigned the minimum duration if possible. The task duration is expanded from minimum to maximum possible or desired in as many as 20 iterations. Initially, a task can have as much as an additional 1/10 of (Max duration min duration) per iteration. An adaptive algorithm adjusts the amount of extra duration per iteration dependent on the characteristics of the problem. Tasks are iterated in the original list order. Tasks are allowed to move other tasks later in time in order to complete the expansion. This is the most common expand modifier.
  • Expand Multi-Segment Tasks Up Front: When used Handover tasks will be expanded fully and at the beginning of the priority group. This allows for backwards compatibility to performance that occurred just after handover tasks were introduced in 2004. It may be used in combination with the useExpandAllTasksAtEnd modifier.
  • Expand After Each Priority Group: If Priority Groups are enabled, after each Priority Group is assigned all tasks will be expanded as described above.
  • Expand Earlier Than Preferred Start: This option will cause the algorithms to expand task assignments earlier than their original start time.
  • Use Multi Try in Priority Groups: Multiple tries are done for each priority group. Improves yields if a later successful task assignment in the priority group add resources that allows additional tasks to be assigned.
  • Use Priority Groups: Turns on the use of priority groups. Before any other sort is done, all timeslots are gathered into groups with identical properties. Using priority groups instead of a simple sort allows the priority of a task to be given elevated status in the algorithms
  • Use Next Available Slot: If the current task is part of a sequence (task sequences are defined in the input specification file) and the current task can be assigned, then the next slot checked will be for another task in the same sequence. This increases the probability that sequences are completed. This operation is done within the current priority group. (Individual tasks in a sequence have the same priority and thus are always in the same priority group.)

Search

Search Types:

  • Ordered: An ordered search is as described. For each priority group, the timeslots (and corresponding task) are tried in the sorted order. If a task is successfully assigned to the task, then later timeslots associated with the task are skipped.
  • Neural: The neural search option implements a search that competes all possible slot solutions against each other. This search option is used without sort parameters since their order is ignored. The only modifier that is fully operational with neural is the expandAllTasksAtEnd.
  • DS1MPS: This search is included to allow for backward compatibility with a standard algorithm available prior to 2008, the MPS algorithm. Providing sort options, in addition to DS1MPS, can slightly alter the results in some cases, but is not recommended. In addition, this search is incompatible with the Expand After Each Priority Group modifier.

Search Options:

  • # of tries for the neural search or random sort: Number of times the algorithms run with different seeds. The algorithms will then select the highest scoring solution.
  • Time Limit: Unlimited or limited amount of time prior to the algorithms ceasing scheduling activities.

Re-sort Timeslots After Each Assignment: This is used for the Greedy algorithm, which resorts timeslots by Figure of Merit score to take into account impacts form previous assignments. This will impact performance, so use it sparingly.

Custom Algorithm Use

After All options are configured for the custom algorithm, select the "Add Trial" button and then "Save Solution". This will open a Window Save pop up where you can name and place the new custom algorithm. To set STK Scheduler to use the custom algorithm file, Navigate to Schedule -> Schedule Properties Algorithm Tab. Select the Custom radio button, enter/navigate to the Custom Algorithm File, and Select OK. STK Scheduler will now use the custom algorithm when the "GO" button is selected to run the Algorithms.