Scenario: HouseSpark Cleaning Co.

You manage 3 cleaning crews in Warsaw:

• Crew A (Alpha), Crew B (Bravo), Crew C (Charlie)
• Availability: Mon–Fri 08:00–17:00 (1-hour lunch flex), Sat 09:00–14:00, Sun off
• Capacity guideline: ~8.0 hours of billable work/day/crew (travel counts separately; model ~0.25–0.75h per job depending on zone crossings)

City is partitioned into Zones A, B, C (approximate neighborhoods). Assume:

• Same-zone travel between jobs: 0.25 h
• Cross-zone travel: 0.6 h
• First job of the day: assume 0.3 h travel from depot (center of Zone B)
• End-of-day return: 0.3 h

Each property has:

• ID, Client, Zone, Type (steady or variable), Duration (fixed or range), Window (earliest-latest start), Preferred day(s), Frequency, Priority (1 high, 2 normal, 3 low), Notes.

Your objective: produce a feasible week schedule (Mon 2025-10-27 → Sun 2025-11-02) that:

• Meets time windows and crew availability
• Respects durations (choose a value within range for variable jobs)
• Minimizes overtime and travel
• Maximizes fulfillment of priority-1 jobs
• Handles mid-week change events without excessive disruption (minimize reschedules)

 

Property Catalog (50)

Legend

• dur_fixed: hours (steady jobs)
• dur_range: [min, max] hours (variable jobs)
• window: HH:MM–HH:MM start window
• pref: preferred days (Mon..Sun)
• freq: W (weekly), 2W (biweekly), O (one-off this week)
• type: steady or variable
• prio: 1 (high), 2 (normal), 3 (low)

1. P01, Kowalski, Zone A, type=steady, dur_fixed=2.5, window 08:30–11:00, pref Mon, freq W, prio 1
2. P02, Nowak, Zone B, variable [2.0,3.5], 09:00–12:00, Tue, W, prio 2
3. P03, Wiśniewska (rental), Zone C, variable [3.0,5.0], 10:00–15:00, checkout Wed, O, prio 1
4. P04, Zieliński, Zone A, steady 3.0, 12:00–15:00, Thu, 2W, prio 2
5. P05, Wójcik, Zone B, steady 2.0, 13:00–16:00, Mon, W, prio 2
6. P06, Kamińska, Zone C, variable [1.5,2.5], 08:00–10:30, Fri, W, prio 3
7. P07, Lewandowski, Zone B, steady 4.0, 09:00–13:00, Wed, 2W, prio 1
8. P08, Dąbrowska, Zone A, variable [2.0,3.0], 11:00–14:00, Tue, W, prio 2
9. P09, Szymański, Zone C, steady 2.5, 14:00–16:30, Thu, W, prio 2
10. P10, Woźniak, Zone B, variable [3.0,4.0], 08:00–11:00, Fri, W, prio 1
11. P11, Kozłowska, Zone A, steady 1.5, 10:00–12:00, Mon, W, prio 3
12. P12, Jankowski, Zone B, variable [2.5,3.5], 12:30–15:30, Tue, 2W, prio 2
13. P13, Mazur, Zone C, steady 2.0, 09:30–11:30, Wed, W, prio 2
14. P14, Krawczyk, Zone A, variable [1.0,2.0], 08:00–10:00, Thu, W, prio 3
15. P15, Kaczmarek, Zone B, steady 3.0, 11:00–14:00, Fri, 2W, prio 2
16. P16, Piotrowski (Airbnb), Zone C, variable [3.0,4.5], 10:00–14:00, checkout Sat, O, prio 1
17. P17, Grabowska, Zone A, steady 2.0, 13:00–15:00, Tue, W, prio 2
18. P18, Zając, Zone B, variable [2.0,3.0], 09:00–12:00, Mon, W, prio 2
19. P19, Pawłowski, Zone C, steady 1.5, 12:00–14:00, Wed, W, prio 3
20. P20, Michalska, Zone A, variable [3.5,5.0], 10:00–15:00, Thu, O, prio 1
21. P21, Król, Zone B, steady 2.0, 08:30–10:30, Tue, W, prio 2
22. P22, Wieczorek, Zone C, variable [2.0,3.0], 13:00–16:00, Fri, 2W, prio 2
23. P23, Jabłońska (rental), Zone A, variable [3.0,5.5], 11:00–16:00, checkout Wed, O, prio 1
24. P24, Wróbel, Zone B, steady 2.5, 12:00–14:30, Thu, W, prio 3
25. P25, Dudek, Zone C, variable [1.5,2.5], 08:00–10:30, Mon, W, prio 2
26. P26, Adamczyk, Zone A, steady 3.0, 09:00–12:00, Wed, 2W, prio 2
27. P27, Górska, Zone B, variable [2.5,4.0], 10:00–14:00, Tue, W, prio 2
28. P28, Nowicka, Zone C, steady 2.0, 14:00–16:00, Thu, W, prio 3
29. P29, Pawlak, Zone A, variable [2.0,3.5], 08:00–11:00, Fri, W, prio 2
30. P30, Sikora, Zone B, steady 1.5, 09:00–10:30, Mon, W, prio 3
31. P31, Walczak, Zone C, variable [3.0,4.0], 11:00–15:00, Wed, 2W, prio 2
32. P32, Baran, Zone A, steady 2.0, 12:00–14:00, Tue, W, prio 2
33. P33, Rutkowski, Zone B, variable [1.5,2.5], 13:30–16:00, Fri, W, prio 3
34. P34, Szulc, Zone C, steady 2.0, 08:30–10:30, Thu, W, prio 2
35. P35, Ostrowska, Zone A, variable [2.0,3.0], 10:00–13:00, Mon, 2W, prio 2
36. P36, Tomaszewski, Zone B, steady 3.0, 11:00–14:00, Tue, W, prio 2
37. P37, Chmielewski, Zone C, variable [1.0,2.0], 09:00–11:00, Wed, W, prio 3
38. P38, Borkowska, Zone A, steady 2.5, 12:00–14:30, Thu, W, prio 2
39. P39, Sokołowski, Zone B, variable [2.0,3.0], 08:30–11:30, Sat, O, prio 2
40. P40, Urbańska, Zone C, steady 3.5, 11:00–14:30, Fri, 2W, prio 1
41. P41, Kubiak, Zone A, variable [2.5,4.0], 09:30–13:30, Mon, W, prio 2
42. P42, Maciejewska, Zone B, steady 2.0, 14:00–16:00, Tue, W, prio 3
43. P43, Szczepański, Zone C, variable [2.0,3.0], 10:00–13:00, Thu, W, prio 2
44. P44, Kowalczyk, Zone A, steady 1.0, 08:00–09:00, Fri, W, prio 3
45. P45, Krupa, Zone B, variable [3.0,4.5], 09:00–13:00, Wed, W, prio 1
46. P46, Jabłoński, Zone C, steady 2.0, 13:00–15:00, Mon, 2W, prio 2
47. P47, Piątek, Zone A, variable [1.5,2.5], 11:00–13:30, Tue, W, prio 2
48. P48, Majewska, Zone B, steady 2.5, 12:00–14:30, Thu, W, prio 2
49. P49, Olszewski (office), Zone C, variable [2.0,3.0], 17:00–19:30, Fri, O, prio 1 (after-hours exception allowed)
50. P50, Malinowska, Zone A, steady 2.0, 09:00–11:00, Sat, O, prio 2

Note: Weekly vs biweekly — for 2W, assume this is their “on” week unless you choose to push some to next week as a trade-off; justify if you do.

 

Change / Disruption Events (announce mid-week)

1. E1 (Tue 17:00): P23 (rental) guests extend stay +1 day → move checkout clean Wed→Thu; duration may increase by +0.5h within range.
2. E2 (Tue 08:00): P07 requests deep-clean add +1.5h if you keep Wed; else reschedule Fri within 08:00–12:00.
3. E3 (Wed 09:00): Crew C short-staffed: capacity −1.5h for Wed only.
4. E4 (Thu 12:00): P10 adds oven/fridge: +1.0h (Fri).
5. E5 (Thu 18:00): P40 (prio 1) asks to pull in earlier on Fri (pref 09:30–13:00).
6. E6 (Fri 07:30): P16 checkout time slips → start window 11:30–15:30 (Sat), duration stays.
7. E7 (Fri 15:30): Roadworks between Zones A↔C → cross-zone travel Fri p.m. and Sat a.m. +0.2h.
8. E8 (Sat 08:00): P39 needs to finish by 12:00 hard due to key-holder constraint.

Students must resequence affected crews with minimal disruption (e.g., keep unaffected jobs stable if possible).

---

Constraints & Assumptions

• Job start must be within window; job duration (chosen within range for variable jobs) must fit entirely inside crew’s day (plus travel).
• One job at a time per crew. Lunch can “float” when convenient.
• You may shift biweekly jobs a day earlier/later if it reduces overtime or avoids violating a window; justify.
• Overtime allowed up to +1.0h/day/crew but penalized (see KPIs).
• You control the exact duration selection for variable jobs at dispatch time; choosing smaller/ larger values has trade-offs—justify.

 

Tasks

1. Define “time window,” “job duration uncertainty,” “travel time model,” and “overtime” in the context of crew scheduling.
2. Explain how variable job durations complicate feasibility compared to steady durations. Provide two mitigation tactics (buffering, robust sequencing, etc.).
3. Construct an initial baseline schedule (Mon–Sun) that covers all prio-1 and prio-2 weekly/one-off jobs with no overtime using the travel model above. State any biweekly deferrals you choose.
4. Justify your selection of durations inside each variable range for the baseline.
5. Apply events E1–E3 and update the schedule. Keep changes minimal (stability objective).
6. Analyze the impact of E4–E5 on Fri; propose two alternative re-plans and compare their KPIs.
7. Apply E6–E8 for Sat; evaluate whether it’s better to:
   • (A) move some Fri jobs to Sat (accept roadworks penalty), or
   • (B) compress Fri with limited overtime.
     Support with quantitative metrics.
8. Calculate weekly KPIs for your final schedule:
   • Total travel hours, total billable hours, overtime hours, number of window violations (target 0), percentage of prio-1 fulfilled on preferred day, reschedule count vs baseline.
9. Discuss trade-offs between a greedy earliest-due-date heuristic vs ILP with binary assignment and sequencing (time-indexed or disjunctive constraints).
10. Evaluate robustness: rerun with all variable jobs at max durations; quantify how many violations occur and propose a buffer policy that caps violations to zero.

Stretch (HL): Formulate a compact MILP or CP-SAT:

• Decision variables: assignment (crew, day, sequence), start times, duration choices for variable jobs.
• Constraints: windows, capacity, sequence & travel, lunch break, events.
• Objective: weighted sum (prio-1 fulfillment, travel, overtime, reschedules).
  Provide model outline and test on a subset (e.g., Mon–Wed).

 

Python Starter Code (data + baseline scaffolding)

# HouseSpark Scheduling Starter (Mon 2025-10-27 → Sun 2025-11-02)
# NOTE: Times are local; compute durations in hours.
from dataclasses import dataclass
from typing import List, Optional, Tuple, Dict
from datetime import datetime, timedelta

DAYS = ["Mon","Tue","Wed","Thu","Fri","Sat","Sun"]
WEEK_START = datetime(2025,10,27)  # Monday

@dataclass
class PropertyJob:
    pid: str
    client: str
    zone: str          # 'A' | 'B' | 'C'
    type: str          # 'steady' | 'variable'
    dur_fixed: Optional[float] = None
    dur_range: Optional[Tuple[float,float]] = None
    window: Tuple[str,str] = ("08:00","16:00")  # earliest, latest START
    pref_days: List[str] = None                 # e.g., ["Mon","Wed"]
    freq: str = "W"                             # 'W'|'2W'|'O'
    prio: int = 2
    notes: str = ""

@dataclass
class Assignment:
    day: str
    crew: str          # 'A'|'B'|'C'
    pid: str
    start: str         # 'HH:MM' planned start
    planned_duration: float  # hours chosen within range if variable
    travel_in: float   # hours travel into this job
    comment: str = ""

# Travel model
def travel_hours(prev_zone: Optional[str], next_zone: str, is_first=False, is_last=False, roadworks=False):
    if is_first or is_last:
        base = 0.3
    else:
        base = 0.25 if (prev_zone == next_zone) else 0.6
    if roadworks:
        base += 0.2
    return base

# Property catalog (subset shown; include all 50 from the handout)
CATALOG: List[PropertyJob] = [
    PropertyJob("P01","Kowalski","A","steady",dur_fixed=2.5,window=("08:30","11:00"),pref_days=["Mon"],freq="W",prio=1),
    PropertyJob("P02","Nowak","B","variable",dur_range=(2.0,3.5),window=("09:00","12:00"),pref_days=["Tue"],freq="W",prio=2),
    PropertyJob("P03","Wiśniewska","C","variable",dur_range=(3.0,5.0),window=("10:00","15:00"),pref_days=["Wed"],freq="O",prio=1,notes="rental"),
    # ... add P04..P50 per spec ...
]

# Crew availability (hours of work; lunch floats)
CREWS = {
    "A": {"Mon":(8.0,17.0),"Tue":(8.0,17.0),"Wed":(8.0,17.0),"Thu":(8.0,17.0),"Fri":(8.0,17.0),"Sat":(9.0,14.0),"Sun":None},
    "B": {"Mon":(8.0,17.0),"Tue":(8.0,17.0),"Wed":(8.0,17.0),"Thu":(8.0,17.0),"Fri":(8.0,17.0),"Sat":(9.0,14.0),"Sun":None},
    "C": {"Mon":(8.0,17.0),"Tue":(8.0,17.0),"Wed":(8.0,17.0),"Thu":(8.0,17.0),"Fri":(8.0,17.0),"Sat":(9.0,14.0),"Sun":None},
}

# Simple greedy baseline: schedule by (priority, preferred day, earliest window)
def choose_duration(job: PropertyJob) -> float:
    if job.type == "steady":
        return job.dur_fixed
    lo, hi = job.dur_range
    # Greedy baseline: choose median to hedge
    return round((lo + hi) / 2.0, 2)

def jobs_for_day(day: str) -> List[PropertyJob]:
    day_idx = DAYS.index(day)
    # Include W and O on their preferred day; include 2W on preferred day (this week on)
    jobs = []
    for j in CATALOG:
        if j.pref_days and day in j.pref_days:
            if j.freq in ("W","O","2W"):
                jobs.append(j)
    # You can add logic to move 2W or O if necessary
    return sorted(jobs, key=lambda j: (j.prio, j.window[0]))

def hhmm_to_float(s: str) -> float:
    h, m = map(int, s.split(":"))
    return h + m/60.0

def float_to_hhmm(x: float) -> str:
    h = int(x)
    m = int(round((x - h) * 60))
    return f"{h:02d}:{m:02d}"

def greedy_schedule_day(day: str, roadworks=False) -> List[Assignment]:
    assignments: List[Assignment] = []
    pool = jobs_for_day(day)
    # Simple policy: pack by zone to reduce cross-zone travel; then by earliest window
    pool.sort(key=lambda j: (j.zone, j.window[0], j.prio))
    # Track crew clocks and last zone
    clocks = {c: CREWS[c][day][0] if CREWS[c][day] else None for c in CREWS}
    last_zone = {c: None for c in CREWS}

    for job in pool:
        dur = choose_duration(job)
        win_start = hhmm_to_float(job.window[0])
        win_end = hhmm_to_float(job.window[1])

        # try crews in order A,B,C picking earliest feasible start >= window
        placed = False
        for crew in ["A","B","C"]:
            if CREWS[crew][day] is None:
                continue
            start_of_day, end_of_day = CREWS[crew][day]
            t = max(clocks[crew] if clocks[crew] is not None else start_of_day, win_start)

            # travel in from last job (or depot)
            tin = travel_hours(last_zone[crew], job.zone, is_first=(last_zone[crew] is None), roadworks=roadworks)
            t_start = max(t + tin, win_start)
            t_finish = t_start + dur

            if t_start <= win_end and t_finish <= end_of_day:
                assignments.append(Assignment(day, crew, job.pid, float_to_hhmm(t_start), dur, tin))
                clocks[crew] = t_finish
                last_zone[crew] = job.zone
                placed = True
                break

        if not placed:
            # Could not place; leave unscheduled for now (students must resolve)
            assignments.append(Assignment(day, "UNASSIGNED", job.pid, "—", dur, 0.0, comment="No feasible slot"))
    return assignments

def apply_event_modifications(day: str, events: Dict[str, dict]):
    # Stub to mutate CATALOG or day rules based on events E1..E8
    pass

def kpis(assignments: List[Assignment]) -> Dict[str, float]:
    travel = sum(a.travel_in for a in assignments if a.crew != "UNASSIGNED")
    billable = sum(a.planned_duration for a in assignments if a.crew != "UNASSIGNED")
    unassigned = sum(1 for a in assignments if a.crew == "UNASSIGNED")
    return {"travel_h": round(travel,2), "billable_h": round(billable,2), "unassigned_jobs": unassigned}

if __name__ == "__main__":
    # Example: build a naive baseline for Monday only
    mon_plan = greedy_schedule_day("Mon", roadworks=False)
    print("MON PLAN")
    for a in mon_plan:
        print(a)
    print("KPIs:", kpis(mon_plan))

Student TODOs

• Complete the CATALOG with P04..P50 as specified.
• Implement weekly loop + event handling: apply E1–E8 on the correct days and re-plan.
• Add overtime accounting (finish time beyond crew end), window violation checks, and reschedule counts vs baseline.
• Improve heuristic: try zone-block packing, priority-first, or smallest-slack-time first.
• (HL) Implement an ILP/CP-SAT model for Mon–Wed and compare to greedy.

Marking Guide

• Correctness (Feasibility): satisfies windows, daily capacities, change events; prio-1 coverage (baseline + final).
• Modeling Choices: clear definitions, justified duration choices for variable jobs, travel model applied consistently.
• Optimization Quality: reduced travel/overtime; stability under changes (low reschedules).
• Analysis & Evaluation: KPIs computed; trade-off discussion between heuristics and exact methods; robustness test (max durations).
• Code Quality: readable, modular, correct checks (violations flagged), reproducible output.