Scheduling - Advanced Level: temporal logic ADVANCED

Boost your speed and accuracy with this high difficulty set 📈 worksheet. Worksheet 25 of 30 presents 20 advanced-level scheduling problems. Focus on temporal logic while practicing timetable puzzles, appointment logic, calendar scheduling. Difficulty: complex scenarios and multi-step problems. Perfect for advanced test takers.

📝 Worksheet 25 of 30 • 20 questions • ⏱️ Estimated time: 20 minutes • 🎯 Advanced level

What you'll learn in this worksheet:

Analyze complex timetable puzzles patterns systematically
Develop analytical thinking for appointment logic problems
Learn step-by-step high difficulty set 📈 approaches
Understand the logic behind calendar scheduling solutions
Apply critical thinking to temporal logic challenges

Your progress through Scheduling

Worksheet 25 of 30 (83% complete)

Question 1

A machine needs to process 4 jobs. Processing times: - Job D: 79 minutes - Job E: 33 minutes - Job B: 34 minutes - Job A: 87 minutes The machine breaks down at 70 minutes and takes 39 minutes to repair. Jobs are scheduled using Shortest Processing Time (SPT) first rule. What is the total completion time (makespan) after handling the breakdown?

Step-by-step solution (Breakdown Recovery):

1. Original SPT order: Job E → Job B → Job D → Job A
2. Simulate processing with breakdown:
- Job E: 0 → 33
- Job B: 33 → 67
- Job D: Starts at 67, breakdown at 70 (3 min completed), repair 39 min, resume 76 min → completes at 185
- Job A: 185 → 272

3. Total makespan: 272 minutes
4. Delay caused by breakdown: 39 minutes

Answer: 272 minutes

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

manufacturing, breakdown, recovery, simulation, reliability

Question 2

Real-time tasks with Rate Monotonic Scheduling (shorter period = higher priority): - Task A: Execution 2, Period 10 - Task B: Execution 3, Period 10 - Task C: Execution 2, Period 10 - Task D: Execution 2, Period 40 Is the task set schedulable under RM?

Step-by-step solution:

1. Calculate utilization:
- Task A: 2/10 = 0.200
- Task B: 3/10 = 0.300
- Task C: 2/10 = 0.200
- Task D: 2/40 = 0.050
Total U = 0.750
2. RM schedulability bound for 4 tasks: 0.757
3. Conclusion: Utilization 0.750 ≤ 0.757 (RM bound)

Answer: Schedulable

real-time, deadline, rate-monotonic, embedded, OS

Question 3

Five patients need appointments. Their preferences are: - Patient A: Dr. Patel at 10:00 AM - Patient B: Dr. Kumar at 10:00 AM - Patient C: Dr. Patel at 10:30 AM - Patient D: Dr. Shah at 10:00 AM - Patient E: Dr. Patel at 11:00 AM Each doctor can see one patient per 30-minute slot. If all preferences are honored, how many patients need to be rescheduled?

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.

appointment, conflict-resolution, multi-person

Question 4

Round Robin scheduling with time quantum = 4: - P1: Burst time 5 - P2: Burst time 7 - P3: Burst time 15 - P4: Burst time 8 What is the average completion time?

Step-by-step solution:

1. Round Robin simulation:
2. Completion times:
- P1: 17
- P2: 20
- P4: 28
- P3: 35

3. Average: 100 ÷ 4 = 25.0

Answer: 25.0

preemptive, interruptible, round-robin, OS, computer-science

Question 5

Four employees need to be scheduled for three shifts over three days. The constraints are: - Each employee works exactly one shift per day - No employee works the same shift two days in a row - Alice works Morning shift on Monday - Bob cannot work Night shift - Charlie works Evening shift on Tuesday Who works the Evening shift on Wednesday?

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.

shift-rotation, multi-person, constraints, professional

Question 6

A project has 5 tasks with the following requirements: - T1: Duration 2 days, Requires 1 resources - T2: Duration 2 days, Requires 2 resources - T3: Duration 5 days, Requires 3 resources - T4: Duration 4 days, Requires 2 resources - T5: Duration 4 days, Requires 2 resources Maximum 6 resources are available at any time. What is the minimum project completion time?

Step-by-step solution:

Resource-Constrained Scheduling:
1. List all tasks with resource requirements:
- T1: 2 days, 1 resources
- T2: 2 days, 2 resources
- T3: 5 days, 3 resources
- T4: 4 days, 2 resources
- T5: 4 days, 2 resources

2. Available resources: 6 per day

4. Optimal schedule:
Days 0-5: T3 (3 resources)
Days 0-2: T2 (2 resources)
Days 0-2: T1 (1 resources)
Days 2-6: T4 (2 resources)
Days 2-6: T5 (2 resources)

5. Total time: 6 days

Key Strategy: Identify task combinations that fit within resource limits.

resource-constraint, parallel-execution, project-management, olympiad

Question 7

A manager has 4 tasks to complete over 8 working hours. The task details are: - Report: Priority High, Duration 3 hours, Deadline 5 hours - Email: Priority Low, Duration 1 hours, Deadline 6 hours - Presentation: Priority High, Duration 2 hours, Deadline 4 hours - Analysis: Priority Medium, Duration 2 hours, Deadline 7 hours If tasks are scheduled based on priority first and deadline second, which task should be completed first?

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.

priority-based, deadline-driven, task-ordering

Question 8

A project involves two events, Event A (Meeting) and Event B (Training). The constraints are: - **Event A:** Duration 90 minutes. Must start between 9:00 AM and 11:00 AM. - **Event B:** Duration 60 minutes. Must finish by 3:00 PM. - **Gap:** A minimum of 2 hours is required between the end of Event A and the start of Event B. Assuming all constraints must be met, what is the earliest possible start time for Event B?

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.

time-arithmetic, gap-constraint, optimization, banking-exams

Question 9

Round Robin scheduling with time quantum = 3: - P1: Burst time 5 - P2: Burst time 13 - P3: Burst time 5 - P4: Burst time 8 - P5: Burst time 12 What is the average completion time?

Step-by-step solution:

1. Round Robin simulation:
2. Completion times:
- P1: 17
- P3: 22
- P4: 33
- P5: 42
- P2: 43

3. Average: 157 ÷ 5 = 31.4

Answer: 31.4

preemptive, interruptible, round-robin, OS, computer-science

Question 10

A bus route takes 49 minutes one-way. Peak frequency: 1 bus every 12 minutes. What is the minimum number of buses needed to maintain this frequency in both directions?

Step-by-step solution:

1. Round trip time: 49 × 2 = 98 minutes
2. Headway: 12 minutes
3. Buses needed: ⌈98 ÷ 12⌉ = 9

Answer: 9 buses

bus, timetable, frequency, public-transport, optimization

Question 11

A school needs to schedule 6 courses. The following courses have overlapping students and cannot be scheduled at the same time: - Biology conflicts with Math - Biology conflicts with CS - Biology conflicts with Physics - Biology conflicts with Chemistry - Chemistry conflicts with CS - Chemistry conflicts with English - Math conflicts with English - CS conflicts with English - CS conflicts with Physics What is the minimum number of time slots needed to schedule all courses without conflicts?

Step-by-step solution (Graph Coloring):

1. Model as graph coloring problem:
- Vertices = Courses
- Edges = Conflicts (courses that cannot be together)
2. Apply greedy coloring algorithm:
- Biology: Slot 1
- Chemistry: Slot 2
- Math: Slot 2
- CS: Slot 3
- English: Slot 1
- Physics: Slot 2

3. Colors/slots used: 3

Answer: Minimum 3 time slots

Key Strategy: The chromatic number of the conflict graph gives the minimum slots needed.

timetable, conflict-resolution, graph-theory, chromatic-number, advanced

Question 12

A hospital ward has 15 patients. Each nurse can handle at most 4 patients. What is the minimum number of nurses required?

Step-by-step solution:

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

Answer: 4 nurses

nurse, patient, assignment, healthcare, ratio

Question 13

A machine needs to process 4 jobs. Processing times: - Job E: 30 minutes - Job B: 37 minutes - Job D: 83 minutes - Job C: 52 minutes The machine breaks down at 109 minutes and takes 18 minutes to repair. Jobs are scheduled using Shortest Processing Time (SPT) first rule. What is the total completion time (makespan) after handling the breakdown?

Step-by-step solution (Breakdown Recovery):

1. Original SPT order: Job E → Job B → Job C → Job D
2. Simulate processing with breakdown:
- Job E: 0 → 30
- Job B: 30 → 67
- Job C: Starts at 67, breakdown at 109 (42 min completed), repair 18 min, resume 10 min → completes at 137
- Job D: 137 → 220

3. Total makespan: 220 minutes
4. Delay caused by breakdown: 18 minutes

Answer: 220 minutes

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

manufacturing, breakdown, recovery, simulation, reliability

Question 14

Round Robin scheduling with time quantum = 2: - P1: Burst time 9 - P2: Burst time 9 - P3: Burst time 8 What is the average completion time?

Step-by-step solution:

1. Round Robin simulation:
2. Completion times:
- P3: 24
- P1: 25
- P2: 26

3. Average: 75 ÷ 3 = 25.0

Answer: 25.0

preemptive, interruptible, round-robin, OS, computer-science

Question 15

A machine can process up to 6 jobs simultaneously as a batch. Each batch takes 54 minutes. If 12 jobs need to be processed, what is the minimum total time required?

Step-by-step solution:

1. Jobs per batch: 6
2. Number of batches: ⌈12 ÷ 6⌉ = 2
3. Total time: 2 × 54 = 108 minutes

Answer: 108 minutes

batch, parallel-machines, capacity, manufacturing, optimization

Question 16

An airline crew has the following flights: - Flight 101: 08:00 → 10:00 - Flight 102: 10:30 → 12:30 - Flight 103: 13:00 → 15:00 - Flight 104: 15:30 → 17:30 - Flight 105: 18:00 → 20:00 Crew duty time limit is 8 hours. Minimum connection time between flights is 30 minutes. What is the maximum number of flights a crew can operate in a single duty period?

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)

airline, crew, flight, aviation, rostering

Question 17

A clinic operates for 4 hours with 15-minute appointment slots. If 11 patients need appointments, how many can be accommodated?

Step-by-step solution:

1. Total slots available: (4 × 60) ÷ 15 = 16
2. Patients: 11
3. All patients can be scheduled

Answer: All 11 patients can be scheduled

clinic, appointment, doctor, healthcare, wait-time

Question 18

A JIT manufacturing system has 4 jobs with the following data: | Job | Processing (min) | Due Date (min) | Early Penalty/min | Late Penalty/min | |-----|-----------------|----------------|-------------------|------------------| | Component D | 58 | 68 | 5 | 17 | | Component C | 34 | 109 | 4 | 12 | | Component B | 30 | 86 | 3 | 10 | | Component A | 58 | 122 | 4 | 20 | Using the Earliest Due Date (EDD) sequencing rule, what is the total penalty incurred?

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

1. EDD Sequence: Component D → Component B → Component C → Component A
2. Calculate completion times and penalties:
- Component D: completes at 58, due 68, early by 10 min → penalty 50
- Component B: completes at 88, due 86, late by 2 min → penalty 20
- Component C: completes at 122, due 109, late by 13 min → penalty 156
- Component A: completes at 180, due 122, late by 58 min → penalty 1160

3. Total penalty: 1386

Answer: 1386 penalty points

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

JIT, earliness, tardiness, penalty, inventory, lean-manufacturing

Question 19

Trains and their scheduled times (arrival, departure): - Train 3: 4:00 → 7:00 - Train 1: 16:00 → 20:00 - Train 2: 18:00 → 19:00 - Train 4: 20:00 → 22:00 What is the minimum number of platforms needed to avoid conflicts?

Step-by-step solution:

1. Sort trains by arrival time
2. Greedy platform allocation
3. Maximum overlapping trains: 2

Answer: 2 platforms

railway, platform, track, transportation, conflict

Question 20

Four tasks (Task 4, Task 2, Task 3, Task 1) must be scheduled with these constraints: 1. Task 4 must be before Task 2 2. Task 2 must be before Task 3 3. Task 4 must be before Task 3 4. Task 1 must be after Task 3 Which constraint is REDUNDANT (does not add new information beyond the others)?

Step-by-step solution (Redundancy Detection):

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

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

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

Answer: Constraint 3 is redundant

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

redundancy, logic, transitivity, critical-thinking, optimization

🚀 Keep the momentum! Worksheet 25 builds your temporal logic skills.

Previous Worksheet Next Worksheet