Understanding the Scheduling Priority Algorithm

New (OST version 1.09+ (03Jun11))

Scheduling Priorities

Every SchedulingBlock can have component priority ratings in seven categories. The first three are mandatory and a value of 100 is assigned for each one that is missing. (This is a severe penalty for not having the required values.)
  1. Primary (required)
  2. Urgency (required)
  3. Science (required)
  4. Override (optional)
  5. Nice (optional)
  6. Stringency (calculated: logBase2(apiLimit) + logBase2(windLimit))
  7. Length (calculated: logBase2(hoursPerExecution))

Each component priority value is weighted based on the weight assignments found in this file: /home/mchost/evla/config/scheduler/schedulingPriorityWeights.properties

For example, the current (and default if the if cannot be found) are:
  • PrimaryWeight=3
  • UrgencyWeight=1
  • ScienceWeight=0.03
  • OverrideWeight=1
  • NiceWeight=1
  • StringencyWeight=0.33
  • LengthWeight=-0.25

Changes to this file are detected in real-time and updated in the OST immediately.

The final priority of a SchedulingBlock is the sum of each component value times its weight. Only Dynamic blocks priorities are considered as Fixed Date SBs are scheduled first, regardless of priority.

Scheduling Algorithm

  1. Add all Fixed Date SBs to the schedule if they have a start time within the LST Range of the schedule. End times are not considered for Fixed Date SBs but are considered below for the Dynamic SBs.
  2. Sort the remaining blocks (all Dynamic) by priority.
  3. For each one: * A. Try to fit the SB in between already scheduled blocks * B. Try to wiggle the SB in between already scheduled blocks by nudging the scheduled blocks left and right to make room.

Details on 3A: Loop from the schedule's Start LST to the schedule's End LST trying to fit the current SB in. If it does not fit at the current LST, increment intelligently. If it didn't fit because it was blocked by an already schedule SB, move to the end time of the blocking SB and continue the loop. If it didn't fit because the current LST was outside the blockToBeScheduled's valid LST range, then advance to the start of the blockToBeScheduled's LST range and continue the loop. If the block is scheduled, check to see if it has more EBs to schedule. If it does, continue the loop; otherwise end the loop.

Details on 3B: First, check to see if the block still has EBs to schedule; if not return. Find the first already scheduled SB that is blocking this SB. Try to fit this SB before that blocking SB by moving the previous SB left and the blocking SB right. If that doesn't work try to fit it after the blocking SB by moving the blocking SB left and the next SB right. If it didn't fit in before or after the blocking SB, find the next blocking SB and repeat the process. Continue until there are no more blocking SBs found or we have scheduled all the EBs for this SB. When the wiggle results in more than enough space, push the blocks (beforeSB, newSB and afterSB) to the left so that they are scheduled sooner rather than later.

Old (OST version < 1.09)

The Formula

Daniel and Brian outlined the heuristics for the OST.

Currently it behaves as follows:

  • SB_Priority = CR (committee ranking) + RM (referee median grade/10.) + PCODE + SB_Over-ride Priority, where
    • CR = ranges from 0-9
    • RM = ranges from 0.-0.4
    • PCODE = -1 * (lb(SB length in decimal hours))/2.
      • This weights longer projects more highly, e.g.,
        • 0.5 hour project would have a PCODE of +0.5
        • 2.0 hour project would have a PCODE of -0.5
        • 8.0 hour project would have a PCODE of -1.5
    • SB_Over-ride_Priority = previously used to raise the priority on some projects (-2 used to raise its priority to an interrupt level; 0 is neutral) - NOTE: It looks like this could be used to implement the discussed 'start-this-project-now' feature in the scheduler (as discussed at the meeting), if it were an editable field within the OST.

The Sequence

  • The first filter is on the wind and API constraints; SBs that pass are then sorted by the SB_Priority; it then executes several passes on each unscheduled SB within the list. So for unscheduled blocks A, B, C and D, the algorithm does:
  • 1) Schedule SBs at the center of their start LST range.
  • 2) If 1) fails/conflicts, shift the SB to the beginning of its start LST range; increment by 15 minutes until it fits (or you've reached the end of the start LST range).
  • 3) If 1) and 2) failed to schedule the SB, identify any interfering SBs and see if they can be shifted to fit the SB into the schedule.

Observation Priority Schemes

Name Origin Values DescriptionSorted descending
Override Staff any To allow schedulers to make the OST priority do what they want it to in special cases
Nice OPT 0 to 1 To allow observers to lower priority of priority their own SBs
Urgency/Obs Type Staff 0 Short timescale transient
    2 Science, moderate probability to observe
    3 Science, might be observed
    1 Science, high probability of being observed
Science PSC 0-9 Science priority, without regard to band priority or LST
    4 Science filler
    1 Partially completed projects, completion badly needed
    2 Normal science and tests
Stringency OST   log_2(wind.limit)+log_2(API.limit)
Length OST .. log_2(length in hrs) seems to work
Observing priority PSC/Staff 0 Especially urgent ToO and urgent commissioning tests

New Name Weight Old Name Weight
Observing 3 priority_sch 1
Urgency/Obs Type 1 -- 0
Stringency 0.33 -- 0
Length -0.25 priority_comp 0.5
Science 0.03 priority_ref 0.1
Nice 1 -- 0
Override 1 override 1

Mapping the Old (0-9) priorities to New Letter Grades

  • 0,1 -> A; A = will almost certainly be observed
  • 2,3 -> B; B = will likely be observed
  • 4,5 -> C; C = might be observed
  • 6-9 -> D; D = filler, or unlikely to be observe

-- JosephMcMullin - 29 Mar 2010
Topic revision: r3 - 2011-06-22, JosephMcMullin
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding NRAO Public Wiki? Send feedback