Scheduling - Beginner Level: timetable puzzles BEGINNER

Step-by-step solution (Interval Graph):

1. Plot intervals on timeline:
Event A: ████ from 1 to 5
Event B: █ from 15 to 16
Event C: ███████ from 19 to 26
Event D: ████ from 12 to 16
Event E: ███ from 20 to 23
Event F: █████ from 16 to 21
Event G: ███████ from 14 to 21

2. Find maximum overlap:
Maximum 4 events overlap at once

Answer: 4 rooms needed

Step-by-step solution:

1. **Model as edge coloring of complete graph K_8
2. Vizing's theorem: χ'(K_n) = n-1 for even n, n for odd n
3. For 8 teams: 7 colors/rounds needed

Answer: 7 rounds

Step-by-step solution:

Set Intersection Method:
1. List all availability:
- Alex: {9:00 AM, 10:00 AM, 2:00 PM, 3:00 PM}
- Ben: {10:00 AM, 11:00 AM, 2:00 PM}
- Cara: {9:00 AM, 11:00 AM, 12:00 PM, 3:00 PM}
- Diana: {10:00 AM, 12:00 PM, 2:00 PM, 3:00 PM}

2. Find common slots (intersection):
- Common to all = Alex AND Ben AND Cara AND Diana
- Result: Empty set (No common time)

3. Conclusion: No common time slot available

Key Strategy: Use set intersection to find common availability, then choose the earliest time.

Step-by-step solution (Bottleneck Analysis):

1. Calculate total load per production line:
- Line 1: 115 minutes
- Line 2: 130 minutes
- Line 3: 40 minutes

2. Identify bottleneck: The line with maximum load = Line 2
3. Bottleneck load: 130 minutes

Answer: Line 2 (130 minutes)

Key Strategy: The bottleneck determines maximum throughput; optimize the bottleneck first for overall efficiency.

Step-by-step solution:

1. Calculate utilization:
- Task A: 16/50 = 0.320
- Task B: 8/30 = 0.267
- Task C: 8/30 = 0.267
- Task D: 3/10 = 0.300
Total U = 1.153
2. RM schedulability bound for 4 tasks: 0.757
3. Conclusion: Utilization 1.153 > 0.757 (RM bound)

Answer: May not be schedulable

Step-by-step solution:

1. Convert all times to minutes for easier calculation:
- Flight 101: Departs at 8:00, Arrives at 10:00
- Flight 102: Departs at 10:30, Arrives at 12:30
- Flight 103: Departs at 13:00, Arrives at 15:00
- Flight 104: Departs at 15:30, Arrives at 17:30
- Flight 105: Departs at 18:00, Arrives at 20:00

2. Duty time limit: 480 minutes (8 hours)
3. Minimum connection time: 30 minutes

4. Find optimal sequence of flights:
Best sequence found: Flight 103 → Flight 104 → Flight 105
- Take Flight 103: Departs at 13:00
- Connection time: 30 minutes
- Take Flight 104: Departs at 15:30
- Connection time: 30 minutes
- Take Flight 105: Departs at 18:00

Total duty time: 420 minutes (7 hours, 0 minutes)

5. Maximum flights possible: 3

Answer: 3 flights

✓ Duty time check: 7h 0m ≤ 8h (PASSED)

Step-by-step solution (Johnson's Rule):

1. Apply Johnson's Rule:
- If M1 time < M2 time, schedule early
- If M2 time < M1 time, schedule late
2. Optimal sequence: Job A → Job C → Job B → Job D
3. Calculate makespan: 161

Answer: 161

Step-by-step solution:

Conflict Detection Method:
1. Create doctor-time matrix:
Doctor | 10:00 | 10:30 | 11:00 | 11:30
------------|-------|-------|-------|-------
Dr. Patel | A | C | E | ---
Dr. Kumar | B | --- | --- | ---
Dr. Shah | D | --- | --- | ---

2. Check for conflicts:
- Dr. Patel at 10:00: Only Patient A (No conflict)
- Dr. Patel at 10:30: Only Patient C (No conflict)
- Dr. Patel at 11:00: Only Patient E (No conflict)
- Dr. Kumar at 10:00: Only Patient B (No conflict)
- Dr. Shah at 10:00: Only Patient D (No conflict)

3. Verification:
- No doctor has multiple patients in same slot
- All preferences can be honored

Answer: 0 patients need rescheduling

Key Strategy: Map all appointments to a doctor-time grid and identify slots where multiple patients request the same doctor.

Step-by-step solution:

1. Identify courses with prerequisites:
- CS201 needs CS202
- CS301 needs CS201
- CS401 needs CS202
- CS102 needs CS201

2. Courses without prerequisites (can take first): CS202

Answer: CS202

Step-by-step solution:

Timeline Grid Method:
1. Create month-date grid:
Jan 5 | Jan 15 | Mar 5 | Mar 15 | May 5 | May 15 | Jul 5 | Jul 15

2. Apply constraints:
- V in March (Mar 5 or Mar 15)
- T on 15th (any month, date 15)
- Two people between S and R
(If S at position 1, R at position 4)
- P and U in same month

3. Systematic placement:
- Place V at Mar 5 (satisfies March constraint)
- Place T at Mar 15 (satisfies 15th constraint)
- For 'two between' constraint: If S at Jan 5, R at Mar 15
- P and U together: May 5 & May 15

4. Verification:
All constraints satisfied with S in March

Key Strategy: Use grid to visualize all slots, apply direct constraints first, then deduce positions using gap constraints.

Step-by-step solution (Redundancy Detection):

1. List all constraints:
1. Task 2 must be before Task 3
2. Task 3 must be before Task 1
3. Task 2 must be before Task 1
4. Task 4 must be after Task 1

2. Check for transitive relationships:
- From Constraint 1: Task 2 before Task 3
- From Constraint 2: Task 3 before Task 1
- By transitivity: Task 2 before Task 1
- This makes Constraint 3 unnecessary (redundant)

3. Verify other constraints are independent:
- Constraint 4 (Task 4 after Task 1) adds unique information

Answer: Constraint 3 is redundant

Key Strategy: Look for transitive relationships (A→B, B→C implies A→C).

Step-by-step solution:

1. Machine load bound: 82
2. Job processing bound: 94
3. Lower bound: 94

Answer: 94

Data Sufficiency Reasoning:

Step 1 - Analyze Statement (1) alone: Testing starts exactly 5 days after Design ends.
This gives partial information but not enough to determine the answer uniquely.

Step 2 - Analyze Statement (2) alone: Planning takes 3 days and ends before Design starts.
This also gives partial information insufficient by itself.

Step 3 - Combine statements:
Together, they provide enough constraints to solve uniquely.

Conclusion: Both statements together are still insufficient.

Key Strategy: Test each statement independently first, then combine only if neither alone works.

Step-by-step solution:

Priority-Deadline Scheduling Algorithm:
1. Assign priority weights:
- High = 3, Medium = 2, Low = 1

2. Create priority-deadline table:
Task | Priority | Deadline | Duration
--------------|----------|----------|----------
Report | High | 5 | 3
Email | Low | 6 | 1
Presentation | High | 4 | 2
Analysis | Medium | 7 | 2

3. Sorting criteria:
- Primary: Highest priority first
- Secondary: Earliest deadline (if priority is same)

4. Sorted order:
1. Presentation (Priority: High, Deadline: 4)
2. Report (Priority: High, Deadline: 5)
3. Analysis (Priority: Medium, Deadline: 7)
4. Email (Priority: Low, Deadline: 6)

Answer: Presentation should be completed first

Key Strategy: Sort by priority first (descending), then by deadline (ascending) for tasks with equal priority.

Step-by-step solution:

1. Identify courses with prerequisites:
- CS101 needs CS401
- CS301 needs CS401
- CS102 needs CS401
- CS201 needs CS401

2. Courses without prerequisites (can take first): CS401

Answer: CS401

Step-by-step solution (Breakdown Recovery):

1. Original SPT order: Job D → Job A → Job C → Job E
2. Simulate processing with breakdown:
- Job D: 0 → 55
- Job A: Starts at 55, breakdown at 79 (24 min completed), repair 21 min, resume 32 min → completes at 132
- Job C: 132 → 211
- Job E: 211 → 297

3. Total makespan: 297 minutes
4. Delay caused by breakdown: 21 minutes

Answer: 297 minutes

Key Strategy: Simulate the timeline, account for breakdown during active job processing.

Step-by-step solution:

1. **Model as edge coloring of complete graph K_10
2. Vizing's theorem: χ'(K_n) = n-1 for even n, n for odd n
3. For 10 teams: 9 colors/rounds needed

Answer: 9 rounds

Step-by-step solution (Interval Graph):

1. Plot intervals on timeline:
Event A: █ from 20 to 21
Event B: ██████ from 8 to 14
Event C: █ from 1 to 2
Event D: ████████ from 7 to 15
Event E: ████████ from 3 to 11
Event F: █████ from 1 to 6
Event G: ████████ from 3 to 11
Event H: █████ from 11 to 16

2. Find maximum overlap:
Maximum 5 events overlap at once

Answer: 5 rooms needed

Step-by-step solution:

Scheduling Grid Analysis:
1. Fix direct constraints:
- Dr. Smith at 11:00-12:00
- Cloud Computing in Hall A
2. Apply consecutive constraint: Dr. Lee and Prof. Brown in consecutive slots
3. Apply conflict constraint: AI Ethics and Machine Learning not together

4. Final Schedule:
9:00-10:00:
- Hall A: Cloud Computing by Dr. Chen
- Hall B: AI Ethics by Prof. Jones
- Hall C: Blockchain by Dr. Lee
10:00-11:00:
- Hall A: Data Science by Prof. Wilson
- Hall B: Machine Learning by Prof. Brown
- Hall C: (empty)
11:00-12:00:
- Hall A: Robotics by Dr. Smith
- Hall B: (empty)
- Hall C: (empty)

Answer: Prof. Brown presents Machine Learning

Key Strategy: Use a grid to solve the assignment problem and satisfy all constraints sequentially.

Step-by-step solution (JIT Penalty Calculation):

1. EDD Sequence: Component C → Component A → Component D → Component B
2. Calculate completion times and penalties:
- Component C: completes at 28, due 57, early by 29 min → penalty 58
- Component A: completes at 61, due 68, early by 7 min → penalty 14
- Component D: completes at 81, due 78, late by 3 min → penalty 33
- Component B: completes at 103, due 82, late by 21 min → penalty 399

3. Total penalty: 504

Answer: 504 penalty points

Key Strategy: JIT scheduling minimizes total earliness + tardiness penalties, balancing inventory costs and customer satisfaction.