Scheduling - Intermediate Level: schedule logic INTERMEDIATE

Step-by-step solution (Time Arithmetic):

1. Goal: To find the earliest start time for Event B, we must use the earliest possible schedule for Event A.
2. Calculate Earliest Finish Time for Event A:
- Earliest Start for A: 9:00 AM
- Duration of A: 90 minutes (1 hour 30 minutes)
- Earliest Finish for A: 9:00 AM + 1 hour 30 minutes = 10:30 AM.
3. Apply Minimum Gap:
- Earliest Start for B = (Earliest Finish A) + (Minimum Gap)
- Minimum Gap: 2 hours (120 minutes)
- Earliest Start for B: 10:30 AM + 2 hours = 12:30 PM.
4. Check Deadline for Event B:
- If B starts at 12:30 PM, its finish time is 12:30 PM + 60 minutes = 1:30 PM.
- The latest finish time for B is 3:00 PM. Since 1:30 PM is before 3:00 PM, the schedule is valid.
Answer: The earliest possible start time for Event B is 12:30 PM.
Key Strategy: To find the minimum time for the second event, use the minimum time for the first event, plus the mandatory gap.

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. Total demand: 20
2. Vehicle capacity: 11
3. Minimum vehicles: ⌈20 ÷ 11⌉ = 2

Answer: 2 vehicles

Step-by-step solution (Bottleneck Analysis):

1. Calculate total load per production line:
- Line 1: 135 minutes
- Line 2: 20 minutes
- Line 3: 130 minutes

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

Answer: Line 1 (135 minutes)

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

Step-by-step solution:

1. Patients: 15
2. Capacity per nurse: 5
3. Minimum nurses: ⌈15 ÷ 5⌉ = 3

Answer: 3 nurses

Step-by-step solution:

1. Calculate utilization:
- Task A: 3/30 = 0.100
- Task B: 2/10 = 0.200
- Task C: 2/50 = 0.040
Total U = 0.340
2. RM schedulability bound for 3 tasks: 0.780
3. Conclusion: Utilization 0.340 ≤ 0.780 (RM bound)

Answer: Schedulable

Step-by-step solution (Redundancy Detection):

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

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

3. Verify other constraints are independent:
- Constraint 4 (Task 1 after Task 2) 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:

Timeline Approach:
1. Convert all times to 24-hour format for easy comparison
- Evening Walk: 6:00 PM
- Office Work: 9:00 AM
- Morning Yoga: 6:00 AM
- Breakfast: 7:30 AM

2. Arrange in chronological order:
1. Morning Yoga at 6:00 AM
2. Evening Walk at 6:00 PM
3. Breakfast at 7:30 AM
4. Office Work at 9:00 AM

Final Schedule: Morning Yoga -> Evening Walk -> Breakfast -> Office Work

Key Strategy: Convert all times to 24-hour format and arrange from earliest to latest.

Data Sufficiency Reasoning:

Step 1 - Analyze Statement (1) alone: A is standing immediately before C.
This gives partial information but not enough to determine the answer uniquely.

Step 2 - Analyze Statement (2) alone: There are exactly two people between B and E.
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 sufficient but neither alone is sufficient.

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

Step-by-step solution:

1. Identify peak demand: 6 staff at hour 4
2. Staff can work multiple hours → schedule around peak
3. Minimum staff needed: 6

Answer: 6 staff

Step-by-step solution:

Table Method with Constraint Elimination:
1. Create a 3D table: Days x Shifts x Employees

2. Apply direct constraints:
- Monday Morning: Alice (fixed)
- Tuesday Evening: Charlie (fixed)
- Bob: Never Night shift (all days)

3. Apply rotation constraint:
- Alice (Morning Mon) cannot be Morning Tue
- Charlie (Evening Tue) cannot be Evening Wed

4. Fill Monday:
- Morning: Alice
- Evening: Charlie (can work evening)
- Night: Diana (Bob can't do night)

5. Fill Tuesday:
- Morning: Bob (Alice can't repeat, Charlie is evening)
- Evening: Charlie (fixed)
- Night: Diana (Bob can't)

6. Fill Wednesday:
- Charlie can't be Evening (was Evening Tue)
- Alice can be Evening (was Morning Mon, okay to shift)
- Answer: Alice works Evening on Wednesday

Key Strategy: Apply fixed constraints first, then use rotation rules to eliminate impossible assignments systematically.

Step-by-step solution:

1. Machine load bound: 70
2. Job processing bound: 71
3. Lower bound: 71

Answer: 71

Step-by-step solution (Redundancy Detection):

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

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

3. Verify other constraints are independent:
- Constraint 4 (Task 4 after Task 3) 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 (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 F → Job A → Job D → Job B → Job E → Job C
3. Calculate makespan: 228

Answer: 228

Step-by-step solution:

1. Round trip time: 46 × 2 = 92 minutes
2. Headway: 12 minutes
3. Buses needed: ⌈92 ÷ 12⌉ = 8

Answer: 8 buses

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)
- Q on 15th (any month, date 15)
- Two people between S and R
(If S at position 1, R at position 4)
- P and T in same month

3. Systematic placement:
- Place V at Mar 5 (satisfies March constraint)
- Place Q at Mar 15 (satisfies 15th constraint)
- For 'two between' constraint: If S at Jan 5, R at Mar 15
- P and T 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:

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:

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:

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

Answer: 3 rounds

Step-by-step solution (Fairness Scheduling):

1. Total shifts to assign:
- 7 days × 3 shifts = 21 shifts
2. Shifts per person: 21 ÷ 5 = 4 with 1 extra shifts
3. Undesirable weight distribution:
- Alice: 2 points
- Bob: 5 points
- David: 2 points
- Emma: 3 points
- Frank: 3 points

4. Fairness gap: 5 - 2 = 3

Key Strategy: Fair scheduling aims to minimize the maximum difference in undesirable shift assignments across all staff.