How I Optimized the Auto-Scheduling Feature

7 million combinations. 2GB of RAM. That’s what my auto-scheduling feature was eating when I tried the brute-force approach for 10 subjects. The scheduling tool I’d built back in 2019 for university students needed an upgrade, and the new feature — automatically finding schedules with minimal overlaps — turned into an optimization challenge that consumed most of my development time.

1. Optimizing Session Memory

Previously, I stored class schedules like this:

{
    "classCode": string, // Class code
    "schedules": [ // Class schedules
        {
            "startDate": number, // Start date
            "endDate": number, // End date
            "dayOfWeek": number, // Day of the week
            "startSession": number, // Start session
            "endSession": number, // End session
        }
    ]
}

The schedules in schedules are sorted ascending by startDate.

To calculate the number of overlapping sessions between 2 classes (different subjects):

totalOverlap = 0 // Total overlapping sessions

Loop through schedules of class 1:
 Loop through schedules of class 2:
  If startDate and endDate of the 2 schedules overlap:
   If dayOfWeek of both schedules match:
    If startSession and endSession overlap:
     totalOverlap += Overlapping weeks * Overlapping sessions

Overlapping sessions are calculated as:

min(endSession1, endSession2) - max(startSession1, startSession2) + 1;

A JavaScript number defaults to 64 bits. So storing sessions takes 64 * 4 = 256 bits. And computing the result requires 4 operations.

So I came up with the idea of storing startSession and endSession as bitmasks:

"schedules": [ // Class schedules
    {
        ...
        "sessionBitmask": number, // Session bitmask for the day
    }
]

Example for sessions 1 through 3:

1110000000000000

Example for sessions 7 through 9:

0000001110000000

With bitmasks, overlapping sessions are calculated as:

let overlapBitmask = bitmask1 & bitmask2;
// bitmask1       = 1110000000000000 = 57344
// bitmask2       = 1111110000000000 = 64512
// overlapBitmask = 0001110000000000 = 7168
while (overlapBitmask) {
  // Count the number of 1-bits
  totalOverlap++;
  overlapBitmask >>= 1; // Right shift by 1 bit
}

Bitmask storage reduced memory from 256 bits (4 integers) to 128 bits (2 integers). Although the bit-counting step adds operations, we can improve it with caching:

if (cache.hasOwnProperty(overlapBitmask)) return cache[overlapBitmask];

localTotalOverlapSession = 0;

while (overlapBitmask) {
  // Count the number of 1-bits
  totalOverlap++;
  localTotalOverlapSession++;

  overlapBitmask = overlapBitmask >> 1; // Right shift by 1 bit
}

cache[overlapBitmask] = localTotalOverlapSession;

Result: overlap calculation time dropped noticeably — didn’t bother measuring exactly but it’s within acceptable range (around +-15s for 7 million combinations).

2. Optimizing the Sample Space

To find the optimal combination based on overlapping sessions (optimal = 0 overlaps), you’d need to generate all combinations then check each one. Sounds bad already.

Instead of generating all combinations first, I calculate overlaps during combination generation. If a combination exceeds the threshold (max 12 overlapping sessions), it gets pruned immediately. The algorithm uses backtracking with recursion:

// Combination generator
function generateCombination(
  current: number[],
  index: number,
  overlap: number
) {
  // If all subjects selected, add this combination to the list
  if (index === selectedSubjects.length) {
    combinations.push([overlap, ...current]);
    return;
  }
  // Get available classes for the current subject
  const classesData = classes[index];
  for (let i = 0; i < classesData.length; i++) {
    let newOverlap = overlap;

    // Get the current class schedule
    const currentClassTimeGrid = timeGrid[index][i];

    // Calculate overlap if this class is added to the combination
    for (let j = 0; j < index; j++) {
      newOverlap += calculateOverlapBetween2Classes(
        timeGrid[j][current[j]],
        currentClassTimeGrid
      );

      // If overlap exceeds threshold, skip this combination
      if (newOverlap > threshold) break;
    }

    // If overlap exceeds threshold, skip this combination
    if (newOverlap > threshold) continue;

    current[index] = i; // Save selected class

    // Generate combination for next subject
    generateCombination(current, index + 1, newOverlap);
  }
}

That’s the approach for now. If you have better ideas, feel free to comment!

3. User Experience

Since auto-scheduling is computation-heavy, I moved the scheduling function to a Web Worker to avoid blocking the UI thread:

const response = await new Promise((resolve, reject) => {
  try {
    this.calendarWorker.onmessage = data => resolve(data);
    this.calendarWorker.postMessage({ ...data });
  } catch (e: unknown) {
    reject(e);
  }
});

4. Multi-threading

Since a single worker is single-threaded, I tried using multiple workers for parallel computation — but hit a bottleneck when sending data back.

Specifically, I split combinations into chunks processed by child workers. But when they finish, results must be sent back to the parent worker for combining.

Workers run in separate execution contexts, so passing messages requires serialize and deserialize (like sending a POST request with JSON body). This costs significant time and memory, so I shelved multi-threading until engines support passing object references between workers (currently only ArrayBuffer, MessagePort, and ImageBitmap are transferable).

5. GPU

I also considered using GPU compute via tensorflow.js (WebGL). But tensor operations are parallel, which means all combinations must be generated first before computing overlaps. This creates massive computation and memory overhead since we can’t prune predictable overlaps like we can sequentially on a single thread. Example using tensorflow.js for parallel computation:

const overlaps = [];
for (const chunk of chunkedCombinations) {
  // Gather class indices for each combination
  const classIndices1 = tf.gather(chunk, i, 1);
  const classIndices2 = tf.gather(chunk, j, 1);

  // Get schedules for selected classes
  const selectedSchedules1 = subjectMatrices.gather(classIndices1);
  const selectedSchedules2 = subjectMatrices.gather(classIndices2);

  // Split schedule components
  const [start1, end1, day1, mask1] = tf.split(selectedSchedules1, 4, -1);
  const [start2, end2, day2, mask2] = tf.split(selectedSchedules2, 4, -1);

  // Filter out schedules with start1 or start2 equal to 0
  const validSchedules = tf.logicalAnd(
    tf.notEqual(start1, tf.scalar(0, "int32")),
    tf.notEqual(start2, tf.scalar(0, "int32"))
  );

  const hasOverlap = tf.logicalAnd(
    tf.lessEqual(start1, end2),
    tf.greaterEqual(end1, start2)
  );
  const dayMatch = tf.equal(day1, day2);
  const bitmaskOverlap = tf.bitwiseAnd(mask1.toInt(), mask2.toInt());

  const totalWeeks = tf.ceil(
    tf.div(
      tf.sub(tf.minimum(end1, end2), tf.maximum(start1, start2)),
      tf.scalar(aWeekInMs)
    )
  );

  let bitmaskOverlapShifted = bitmaskOverlap;
  const bitCounts = [];

  for (let i = MIN_SESSION; i <= MAX_SESSION; i++) {
    bitCounts.push(
      tf.bitwiseAnd(
        bitmaskOverlapShifted,
        tf.fill(bitmaskOverlap.shape, 1, "int32")
      )
    );
    bitmaskOverlapShifted = tf.floorDiv(bitmaskOverlapShifted, 2);
  }

  const totalBitCounts = tf.addN(bitCounts);

  // Calculate total overlap
  const pairOverlaps = tf.mul(
    tf.mul(
      tf.mul(tf.cast(hasOverlap, "int32"), tf.cast(dayMatch, "int32")),
      tf.mul(totalWeeks, tf.cast(validSchedules, "int32"))
    ),
    totalBitCounts
  );

  const summedPairOverlaps = tf.sum(pairOverlaps, [1, 2, 3, 4]);
  overlaps.push(summedPairOverlaps);
}

Also, GPU computation froze the UI entirely (GPU resources maxed out). I tried limiting resources but nothing worked.

So GPU computation is still on hold here.