Iterative Repair for Scheduling
Data Pipelines, Monitoring & Reliability DS practice problem on Onlearn.
Difficulty: medium.
Topics: Iterative Repair for Scheduling, Min-Conflicts Heuristic, Constraint Violation Penalty, Hill Climbing Perturbation, Backtracking Search, Repair Operator Selection, Combinatorial Optimization, Constraint Satisfaction, Automated Planning, Distributed Systems, Heuristic Search, Local Search Algorithms, Resource Allocation Modeling, Conflict Resolution Strategies, State Space Traversal, Dynamic Scheduling Policies.
Implement an iterative repair algorithm for a single machine job scheduling problem. You are given a set of jobs, each with a processing time and a deadline, along with an initial ordering of jobs on the machine. The goal is to minimize total tardiness (the sum of how late each job finishes past its deadline). The tardiness of a job is defined as max(0, completion time deadline). Jobs are processed sequentially in the given order on a single machine with no idle time. Your algorithm should start from the initial schedule and iteratively improve it. In each iteration, evaluate all possible adjacent swaps (swapping the job at position i with the job at position i+1). Among all swaps that reduce the total tardiness, apply the one that achieves the greatest reduction. If no adjacent swap improves the total tardiness, or if the maximum number of iterations is reached, stop and return the current schedule along with its total tardiness. Return a tuple of (final order, total tardiness) where final order is a list of job indices and total tardiness is an integer.