scheduling strats

scheduling.md

Strategy 1: Least Common Multiple (LCM) Cycle

Explanation: Calculate LCM of all intervals to create a cycle. Within the cycle, schedule each announcement at multiples of its interval. Prevent overlaps by assigning the earliest available slot.

Code:

const moment = require('moment');

const SCHEDULED_ANNOUNCEMENTS = [/* as defined */];

function lcm(a, b) {
  const gcd = (x, y) => y === 0 ? x : gcd(y, x % y);
  return (a * b) / gcd(a, b);
}

function getCycleInterval(announcements) {
  return announcements.reduce((acc, ann) => lcm(acc, ann.interval), 1);
}

function generateSchedule(announcements) {
  const cycle = getCycleInterval(announcements);
  const schedule = [];
  
  announcements.forEach(ann => {
    for (let t = 0; t < cycle; t += ann.interval) {
      if (ann.isActive && !ann.isActive()) continue;
      schedule.push({ time: t, name: ann.name });
    }
  });

  schedule.sort((a, b) => a.time - b.time);
  // Resolve overlaps
  const finalSchedule = [];
  schedule.forEach(item => {
    if (finalSchedule.length && item.time === finalSchedule[finalSchedule.length - 1].time) {
      item.time += 1; // Shift by 1 second
    }
    finalSchedule.push(item);
  });
  return finalSchedule;
}

const schedule = generateSchedule(SCHEDULED_ANNOUNCEMENTS);
console.log(schedule);

Strategy 2: Priority Queue with Frequency Priority

Explanation: Use a priority queue where higher frequency announcements have higher priority. Schedule based on priority, ensuring no overlaps and spacing.

Code:

class PriorityQueue {
  constructor() { this.queue = []; }
  enqueue(item) {
    this.queue.push(item);
    this.queue.sort((a, b) => a.priority - b.priority);
  }
  dequeue() { return this.queue.shift(); }
  isEmpty() { return this.queue.length === 0; }
}

function generatePrioritySchedule(announcements) {
  const pq = new PriorityQueue();
  announcements.forEach(ann => pq.enqueue({ ...ann, next: 0, priority: ann.interval }));
  const schedule = [];
  const cycle = getCycleInterval(announcements);
  
  for (let t = 0; t < cycle; t++) {
    while (!pq.isEmpty() && pq.queue[0].next === t) {
      const ann = pq.dequeue();
      if (ann.isActive && !ann.isActive()) break;
      schedule.push({ time: t, name: ann.name });
      ann.next += ann.interval;
      pq.enqueue(ann);
    }
  }
  return schedule;
}

const prioritySchedule = generatePrioritySchedule(SCHEDULED_ANNOUNCEMENTS);
console.log(prioritySchedule);

Strategy 3: Timer-Based Scheduling with Single Timer

Explanation: Use a single interval timer that ticks every second. At each tick, check which announcements are due, enqueue them ensuring no overlaps and spacing.

Code:

class Scheduler {
  constructor(announcements) {
    this.announcements = announcements.filter(a => !a.isActive || a.isActive());
    this.lastPlayed = null;
    this.queue = [];
    this.startTime = moment();
    this.cycle = getCycleInterval(this.announcements);
  }

  tick(currentTime) {
    this.announcements.forEach(ann => {
      if (currentTime % ann.interval === 0) this.queue.push(ann);
    });
    if (!this.lastPlayed && this.queue.length) {
      this.play(this.queue.shift(), currentTime);
    }
  }

  play(ann, time) {
    if (this.lastPlayed && time - this.lastPlayed < 5) return;
    console.log(`Playing ${ann.name} at ${time}`);
    this.lastPlayed = time;
  }

  run() {
    setInterval(() => {
      const currentTime = moment().diff(this.startTime, 'seconds') % this.cycle;
      this.tick(currentTime);
    }, 1000);
  }
}

const scheduler = new Scheduler(SCHEDULED_ANNOUNCEMENTS);
scheduler.run();

Strategy 4: Multiple Independent Timers

Explanation: Assign individual timers to each announcement based on their interval. Manage concurrency to prevent overlaps by checking the current playing status.

Code:

const EventEmitter = require('events');

class MultiTimerScheduler extends EventEmitter {
  constructor(announcements) {
    super();
    this.announcements = announcements.filter(a => !a.isActive || a.isActive());
    this.isPlaying = false;
    this.scheduleTimers();
    this.on('play', this.handlePlay.bind(this));
  }

  scheduleTimers() {
    this.announcements.forEach(ann => {
      setInterval(() => {
        this.emit('play', ann);
      }, ann.interval * 1000);
    });
  }

  handlePlay(ann) {
    if (this.isPlaying) return;
    this.isPlaying = true;
    console.log(`Playing ${ann.name} at ${moment().format()}`);
    // Simulate audio duration
    setTimeout(() => { this.isPlaying = false; }, 3000);
  }
}

const multiTimerScheduler = new MultiTimerScheduler(SCHEDULED_ANNOUNCEMENTS);

Strategy 5: Round-Robin with Interval Alignment

Explanation: Cycle through announcements in a round-robin fashion, aligning each to its interval. Adjust next play time based on last played to maintain frequency.

Code:

function roundRobinSchedule(announcements, cycle) {
  const schedule = [];
  const lastPlayed = {};
  
  announcements.forEach(ann => { lastPlayed[ann.name] = -ann.interval; });
  
  for (let t = 0; t < cycle; t++) {
    for (let ann of announcements) {
      if (t - lastPlayed[ann.name] >= ann.interval) {
        if (schedule[schedule.length - 1]?.name !== ann.name) {
          schedule.push({ time: t, name: ann.name });
          lastPlayed[ann.name] = t;
        }
      }
    }
  }
  return schedule;
}

const rrSchedule = roundRobinSchedule(SCHEDULED_ANNOUNCEMENTS, getCycleInterval(SCHEDULED_ANNOUNCEMENTS));
console.log(rrSchedule);