solve_schedule

Instructions

Implementation Reference

• mission-control/apps/api/src/services/oracle/algorithms/constraintOptimizer.ts:174-284 (handler)

  The main handler function `optimizeSchedule` that implements the schedule optimization logic. Takes tasks and time slots, formulates a binary integer programming problem maximizing priority-weighted completion with energy matching, solves it via HiGHS, and returns assignments with total score.

  export async function optimizeSchedule(
    tasks: Task[],
    slots: TimeSlot[],
  ): Promise<ScheduleResult> {
    const energyMatch: Record<string, Record<string, number>> = {
      high: { high: 1.0, medium: 0.5, low: 0.2 },
      medium: { high: 0.8, medium: 1.0, low: 0.6 },
      low: { high: 0.4, medium: 0.7, low: 1.0 },
    };
  
    const variables: OptimizationVariable[] = [];
    const objective: Record<string, number> = {};
    const constraints: Constraint[] = [];
  
    // Sanitize IDs for LP format (no hyphens, spaces, or special chars)
    const sanitize = (s: string) => s.replace(/[^a-zA-Z0-9]/g, "");
    const taskIdMap = new Map(tasks.map((t) => [t.id, sanitize(t.id)]));
    const slotIdMap = new Map(slots.map((s) => [s.id, sanitize(s.id)]));
  
    // Binary variable x_i_j = 1 if task i assigned to slot j
    for (const task of tasks) {
      for (const slot of slots) {
        if (slot.durationMinutes >= task.durationMinutes) {
          const varName = `x${taskIdMap.get(task.id)}${slotIdMap.get(slot.id)}`;
          variables.push({ name: varName, type: "binary" });
  
          // Objective: priority × energy match
          const match = energyMatch[task.energyRequired]?.[slot.energyLevel] ?? 0.5;
          objective[varName] = task.priority * match;
        }
      }
    }
  
    // Each task assigned at most once
    for (const task of tasks) {
      const coefficients: Record<string, number> = {};
      for (const slot of slots) {
        const varName = `x${taskIdMap.get(task.id)}${slotIdMap.get(slot.id)}`;
        if (variables.some((v) => v.name === varName)) {
          coefficients[varName] = 1;
        }
      }
      if (Object.keys(coefficients).length > 0) {
        constraints.push({ name: `task${taskIdMap.get(task.id)}`, coefficients, upper: 1 });
      }
    }
  
    // Each slot used at most once
    for (const slot of slots) {
      const coefficients: Record<string, number> = {};
      for (const task of tasks) {
        const varName = `x${taskIdMap.get(task.id)}${slotIdMap.get(slot.id)}`;
        if (variables.some((v) => v.name === varName)) {
          coefficients[varName] = 1;
        }
      }
      if (Object.keys(coefficients).length > 0) {
        constraints.push({ name: `slot${slotIdMap.get(slot.id)}`, coefficients, upper: 1 });
      }
    }
  
    if (variables.length === 0) {
      return { assignments: [], unscheduled: tasks.map((t) => t.id), totalScore: 0 };
    }
  
    const result = await solve({
      direction: "maximize",
      objective,
      variables,
      constraints,
    });
  
    // Build reverse maps: sanitized → original ID
    const reverseTaskMap = new Map(tasks.map((t) => [sanitize(t.id), t.id]));
    const reverseSlotMap = new Map(slots.map((s) => [sanitize(s.id), s.id]));
  
    const assignments: Array<{ taskId: string; slotId: string; score: number }> = [];
    const scheduledTasks = new Set<string>();
  
    if (result.status === "optimal") {
      for (const [varName, value] of Object.entries(result.solution)) {
        if (value > 0.5 && varName.startsWith("x")) {
          // Find which task+slot this variable represents
          const suffix = varName.slice(1); // remove leading "x"
          for (const [sanTask, origTask] of reverseTaskMap) {
            if (suffix.startsWith(sanTask)) {
              const sanSlot = suffix.slice(sanTask.length);
              const origSlot = reverseSlotMap.get(sanSlot);
              if (origSlot) {
                scheduledTasks.add(origTask);
                assignments.push({
                  taskId: origTask,
                  slotId: origSlot,
                  score: objective[varName] ?? 0,
                });
                break;
              }
            }
          }
        }
      }
    }
  
    const unscheduled = tasks.filter((t) => !scheduledTasks.has(t.id)).map((t) => t.id);
  
    return {
      assignments,
      unscheduled,
      totalScore: result.objectiveValue,
    };
  }

• mission-control/apps/api/src/services/oracle/algorithms/constraintOptimizer.ts:47-68 (schema)

  Type definitions: Task, TimeSlot, and ScheduleResult interfaces used by optimizeSchedule.

  export interface Task {
    id: string;
    name: string;
    durationMinutes: number;
    priority: number; // Higher = more important
    deadline?: number; // Unix timestamp
    energyRequired: "high" | "medium" | "low";
    category?: string;
  }
  
  export interface TimeSlot {
    id: string;
    startTime: number; // Unix timestamp
    durationMinutes: number;
    energyLevel: "high" | "medium" | "low";
  }
  
  export interface ScheduleResult {
    assignments: Array<{ taskId: string; slotId: string; score: number }>;
    unscheduled: string[];
    totalScore: number;
  }