How the autoscheduler works

Introduction

This article describes RehabAlpha's logic for autoscheduling treatments.

Optimize facility schedule

The inputs are:

1. A facility
2. An inclusive date range [d1, d2] where d1 is greater than or equal to today.

NOTE: "today" will always be relative to the timezone of the facility.

Definitions

Define the planner period as [d1, d2] where d1 and d2 are given as inputs to the optimizeFacilitySchedule function.

Define the lookahead period as the 90 calendar dates from today through today + 89 days.

Define the modification period as the intersection of the planner period and the lookahead period, after applying the facility's schedule lock.

If lockScheduleWithinNDays is null, there is no lock-window restriction. If lockScheduleWithinNDays is non-null, dates through today + lockScheduleWithinNDays are locked, and the first modifiable date is today + lockScheduleWithinNDays + 1.

If the modification period is empty, the autoscheduler exits without fetching cases, searching for a better schedule, or making changes.

Define a therapy case's resolved treatment-plan schedule using the treatment scheduling and compliance rules described in the treatment scheduling article. This schedule contains:

1. Treatable windows: the effective slices of treatment-plan authority where treatments may be created.
2. Native compliance windows: the full compliance windows that define each treatment period's rules.
3. Anti-stacking windows: max-only compliance windows derived from overlapping treatable windows that use the same units and same basis.

Strategy

At a high level, the strategy is this:

1. Initialize the current schedule as the champion schedule
2. Randomly perturb the champion schedule to produce a challenger schedule
3. If the challenger schedule is better than the champion, crown it the new champion

Repeat steps 2 and 3 until convergence (described below).

Note that ties go to the champion. For a challenger schedule to win, it must be strictly better than the champion.

Algorithm

At a high level, we're going to

1. Exit without changes if the modification period is empty
2. Pick the first therapy case from a pre-determined pool of cases
3. Build a set of challenger schedules by perturbing this therapy case
4. Make the challengers and current champion compete, then crown a champion
5. Repeat this process using the next therapy case

Pool of cases

1. Fetch all the active therapy cases linked to the facility
2. Resolve each case's treatment-plan schedule.
3. Discard cases that have no relevant windows and no relevant treatments. A case is relevant if it has a treatable window that overlaps the planner period, a compliance window that overlaps the planner period, or an existing treatment in the planner period that the autoscheduler might move or delete.
4. Randomly shuffle the set of relevant therapy cases.
5. Pick the first case in the list.

Pool of dates

The dates in the sampling pool should be determined after selecting a therapy case.

The dates in the sampling pool should be the dates that are in all of these:

1. the dates in the planner period
2. the dates in the modification period
3. the dates in one of the therapy case's resolved treatable windows

We'll call these dates the "sample dates".

The sample dates are not necessarily a single continuous range. A newer treatment plan with 0 treatment periods can supersede older treatment-plan authority, and older indefinite plans do not resume after newer finite plans end. Because of this, the autoscheduler should use the union of the resolved treatable windows instead of treating the case as one continuous range from the first treatment period to the last treatment period.

For updates and deletes, the candidate treatment's current date must be in the planner period, and any new date must be in the sample dates.

Procedure

After a sample case is selected and sample dates are determined, our goal is to build a big set of valid challenger schedules.

1. First, generate challenger schedules that introduce a newly created treatment to the champion schedule. (Skip this step if the facility has allowCreateAndDelete = false.)

   1. Iterate over the sample dates.
   2. Skip any date that already has a treatment for the same therapy case.
   3. For each date, determine the sample therapists. These are therapists with a non-expired license in the relevant state for the relevant discipline, who also have >0 planned hours at the facility on this date. Include null in this set.
   4. For each sample therapist, create a challenger schedule with the sample therapist assigned to the new treatment on this date.

2. Next generate challenger schedules that delete a single treatment from the champion schedule. (Skip this step if the facility has allowCreateAndDelete = false.)

   1. Starting with the champion schedule, identify all the deletable treatments in the planner period.
   2. A treatment is deletable only if it is unsigned, has no active pending signature request, has no resolutionId, is not inside the schedule lock window, and can be safely removed from the treatment document, treatment list, clinical version, and signature-details records.
   3. Make one challenger schedule per deletable treatment that omits the treatment from the schedule.

3. Next generate challenger schedules by simulating various modifications to each treatment.

   1. Starting with the champion schedule, identify all the treatments in the planner period that don't have a resolutionId.

   2. Iterate over the sample treatments

   3. For the current treatment, build a challenger schedule for each allowed perturbation of the treatment.

      A treatment can be perturbed by:

      1. changing its date to another date in the set of sample dates
      2. changing its therapist to another therapist in the set of sample therapists. (The sample therapists are determined just as described above.)
      3. changing its date and therapist

      A perturbation is allowed if it doesn't violate the treatment's lockTherapist or lockDate properties, and it doesn't violate the facility's lockTherapists and lockDates properties. A date perturbation is also invalid if it would create more than one treatment on the same date for the same therapy case.

Make the champion schedule and all of the case-based challenger schedules compete. Then crown a winner (the, potentially new, champion). Then pick the next case in the list of sample cases and repeat this process until the case-based search reaches local convergence.

4. Generate challenger schedules by simulating therapist swaps.

   1. Starting with the champion schedule, iterate over the dates in the modification period.
   2. For each discipline, identify active treatments on that date with a modifiable therapist.
   3. Randomly pick two treatments from that set.
   4. If the therapists are different, build a challenger schedule by swapping the assigned therapists between those two treatments.
   5. The swap is valid only if both therapist assignments are allowed for the target treatment date and discipline. Null therapist assignments are allowed.
   6. Make the challenger and champion compete. If the challenger wins, crown it the new champion and continue from that champion.
   7. Repeat until 100 attempts pass without crowning a new champion, then move to the next discipline.

5. Generate challenger schedules by simulating date swaps.

   1. Starting with the champion schedule, iterate over assigned therapists.
   2. For each discipline, identify active treatments assigned to that therapist and discipline with a modifiable date.
   3. Randomly pick two treatments from that set.
   4. If the dates are different, build a challenger schedule by swapping the dates between those two treatments.
   5. The swap is valid only if each treatment moves to a date allowed by its own therapy case's sample dates.
   6. Atomic date swaps may swap two treatments from the same case with each other, but the resulting schedule may not contain more than one treatment on the same date for the same therapy case.
   7. Make the challenger and champion compete. If the challenger wins, crown it the new champion and continue from that champion.
   8. Repeat until 100 attempts pass without crowning a new champion, then move to the next discipline.

6. Generate challenger schedules by simulating treatment swaps.

   1. Starting with the champion schedule, iterate over disciplines.
   2. Identify active treatments for that discipline with both a modifiable date and a modifiable therapist.
   3. Randomly pick two treatments from that set.
   4. If the dates or therapists are different, build a challenger schedule by swapping both the dates and assigned therapists between those two treatments.
   5. The swap is valid only if each treatment moves to a date allowed by its own therapy case's sample dates and both therapist assignments are allowed for the target treatment date and discipline. Null therapist assignments are allowed.
   6. Atomic treatment swaps may swap two treatments from the same case with each other, but the resulting schedule may not contain more than one treatment on the same date for the same therapy case.
   7. Make the challenger and champion compete. If the challenger wins, crown it the new champion and continue from that champion.
   8. Repeat until 100 attempts pass without crowning a new champion, then move to the next discipline.

Convergence

Stop the process once either of these is true:

1. The autoscheduler completes a full optimization round without crowning a new champion.

   A full optimization round means both of these are true:

   1. The case-based search completes a full pass through all sample cases without crowning a new champion.
   2. The therapist-swap, date-swap, and treatment-swap phases all run from that case-converged champion without crowning a new champion.

   If any case-based challenger wins, the autoscheduler keeps running case-based passes until a full case pass has no winner. If any swap challenger wins, the autoscheduler runs another case-based search from that new champion before trying the swap phases again.

2. A total of 10,000 challenger schedules have competed

How to crown a winner

Each facility has a user-specified schedule priority order. A challenger schedule wins only if it is strictly better than the champion schedule using that priority order. Ties go to the champion.

Each priority produces a score where lower values are better. To crown a winner, compare the challenger and champion lexicographically:

1. Compare the scores for the first user-specified priority.
2. If one schedule has a lower score, that schedule wins.
3. If the scores are equal, compare the next priority.
4. Continue until a winner is found or all priorities are tied.
5. If all priorities are tied, the champion remains the champion.

The current priority items are:

1. Avoid noncompliant treatment plans

   This priority uses a Compliance Score.

2. Avoid unassigned treatments

   Count the number of treatments that do not have an assigned therapist. (higher values are worse)

3. Equal therapist utilization

   For each discipline, calculate a target utilization as total estimated treatment minutes in the planner range divided by total eligible planned therapist minutes in the planner range. Eligible therapist-days are therapist-days with more than 0 planned minutes and a matching license for the discipline. Each eligible therapist-day is scored as the absolute difference between its target treatment minutes (target utilization * planned minutes) and its currently assigned treatment minutes. Each therapist-day score is rounded to the nearest 5 minutes. Unassigned treatment minutes and assigned treatment minutes outside an eligible therapist-day are scored against a target of 0, also rounded to the nearest 5 minutes. The final score is the sum across all disciplines. Higher values are worse.

Compliance Score

Compliance Score is calculated from the resolved treatment-plan schedule.

Score every treatable window and anti-stacking window that intersects the scoring scope. The scoring scope should include any window that could be affected by the current challenger. In the simplest implementation, the scoring scope can be all resolved windows that intersect the planner period.

For each scored window:

actual = scheduled value in the window
deficit = max(0, minValue - actual)
surplus = if maxValue is null: 0, else: max(0, actual - maxValue)
rawDistance = deficit + surplus

The scheduled value uses the window's units:

1. For treatments, count treatments.
2. For treatment-days, count distinct treatment dates.
3. For minutes, sum treatment minutes.

Partial treatable windows use their effective bounds. In particular, a partial treatable window has minValue = 0 and keeps its original max cap. This means a partial window is noncompliant only if it exceeds its max.

Anti-stacking windows are max-only windows. They have minValue = 0 and maxValue equal to the highest comparable finite max from the overlapping treatable windows. Anti-stacking windows are only created when the overlapping treatable windows use the same units and same basis. For example, weekly treatment-count rules can be compared with other weekly treatment-count rules, but weekly treatment-count rules are not converted into 30-day rules or minute rules.

Represent Compliance Score as:

violatingWindows = count of scored windows where rawDistance > 0
normalizedDistance = sum of rawDistance / denominator for each scored window
rawDistance = sum of rawDistance for each scored window

The denominator should make unlike units less explosive when compared together. A reasonable denominator is:

1. maxValue when the window has a finite max greater than 0
2. minValue when the window has no finite max and minValue is greater than 0
3. 1 otherwise

When comparing two Compliance Scores, use lexicographic order:

1. fewer violating windows wins
2. if tied, lower normalized distance wins
3. if tied, lower raw distance wins

This means the autoscheduler first prefers schedules that satisfy more treatment-plan windows, then prefers schedules that are closer to compliance, while still preserving exact raw distance as a final deterministic tiebreaker.

Compliance Score should not reward filling a compliant partial window up to its max. For example, if a partial window allows up to 3 treatments and requires 0, then 0, 1, 2, and 3 treatments are all equally compliant for this priority. If RehabAlpha later wants to prefer "as full as possible" partial windows, that should be modeled as a separate lower-priority utilization score rather than as part of Compliance Score.