Preventive Maintenance Scheduling
Scheduling with Time Windows — Greedy / ILP
A manufacturing plant must schedule 8–12 PM tasks across 3 machines with 2 maintenance crews over a 5-day horizon. Each task has a maintenance window — scheduling outside this window risks unplanned breakdown costing €5,000–€50,000 per incident.
Where This Decision Fits
Manufacturing operations lifecycle — the highlighted step is what this page optimizes
The Problem
From maintenance windows to weighted completion time optimization
A manufacturing facility operates 3 production machines (CNC lathe, hydraulic press, packaging line) that require periodic preventive maintenance. 8 PM tasks must be completed by 2 maintenance crews over a 5-day horizon (40 working hours). Each task has a preferred maintenance window [aj, bj] and a processing time pj. Scheduling a task outside its window increases breakdown risk — each unplanned failure costs €5,000–€50,000 in lost production, emergency repairs, and downstream delays.
The objective is to minimize weighted completion time — prioritizing tasks by urgency and breakdown cost while respecting crew capacity and time-window constraints.
| Maintenance Domain | Scheduling Model | |
|---|---|---|
| Maintenance crew | Machine (processor) | |
| PM task | Job j with processing time pj | |
| Maintenance window [aj, bj] | Time-window constraint | |
| Breakdown cost / urgency | Weight wj | |
| Minimize delay & risk | Min Σ wj Cj |
subject to
Cj = Sj + pj ∀ j // completion = start + processing
aj ≤ Sj ≤ bj − pj ∀ j // start within maintenance window
Σi xij = 1 ∀ j // each task assigned to exactly one crew
no overlap on crew i ∀ i // crew handles one task at a time
xij ∈ {0, 1} // binary assignment
Try It Yourself
Schedule maintenance tasks across crews and see the Gantt chart update
Maintenance Scheduler
8 Tasks · 2 Crews| # | Task | Machine | Duration (h) | Window Start | Window End | Weight |
|---|
Ready. Select a scenario and click “Solve & Visualize”.
| Algorithm | On Time | Total Delay | Crew Util. | Time |
|---|---|---|---|---|
| Click Solve & Visualize | ||||
The Algorithms
Three approaches to maintenance scheduling with time windows
Earliest Deadline First (EDF)
O(n log n) | Optimal for single machine, no windowsSort all PM tasks by their window end time bj in ascending order. Assign each task to the crew with the earliest available slot, starting as early as possible within its window. Tasks whose deadlines come first get priority, minimizing the chance of window violations. This mirrors how maintenance planners naturally prioritize — the most urgent tasks first.
Shortest Task First (STF)
O(n log n) | Minimizes average completion timeSort tasks by processing time pj in ascending order. By completing short tasks first, the schedule maximizes the number of tasks finished early, freeing crew capacity for longer, more complex maintenance. This is the SPT (Shortest Processing Time) rule, which is optimal for minimizing ΣCj on a single machine without window constraints.
Integer Linear Program (ILP)
Exponential worst-case | Provably optimal solutionFormulate the full problem as a mixed-integer program with binary assignment variables xij, continuous start times Sj, and big-M disjunctive constraints to prevent crew overlap. The ILP solver explores the feasible region via branch-and-bound, producing a provably optimal schedule with minimum weighted completion time. For the problem sizes here (8–12 tasks), the solver terminates in milliseconds.
Real-World Complexity
Why preventive maintenance scheduling goes beyond the basic model
Beyond the Basic Model
- Condition-based triggers — IoT sensor data (vibration, temperature, oil analysis) can shift maintenance windows dynamically, requiring re-optimization in real time
- Spare parts availability — Some tasks require specific parts with lead times, adding release-date constraints that may conflict with maintenance windows
- Production schedule coupling — Machines cannot be taken offline during critical production runs; maintenance must fit into planned downtime slots
- Crew specialization — Not every technician is qualified for every machine; electrical, mechanical, and hydraulic skills create eligibility constraints
- Cascading failures — Delaying one task increases failure probability for dependent systems, creating stochastic penalty functions
- Multi-site coordination — Shared maintenance crews across multiple plant locations add travel time and inter-site scheduling constraints
- Regulatory inspections — Safety-critical equipment has mandatory inspection intervals imposed by regulators, adding hard deadline constraints
Key References
Foundational works in maintenance scheduling optimization
- (2016). “Scheduling: Theory, Algorithms, and Systems.” 5th Edition, Springer.
- (1996). “Applications of maintenance optimization models: a review and analysis.” Reliability Engineering & System Safety, 51(3), 229–240.
- (2016). “Maintenance scheduling in the electricity industry: A literature review.” European Journal of Operational Research, 251(3), 695–706.
Need to optimize your maintenance operations?
From preventive maintenance scheduling to predictive analytics, mathematical modeling can reduce downtime and extend asset life. Let’s discuss how Operations Research can work for your plant.