Scheduling Worksheet 10 - Beginner-Intermediate Level (temporal logic) | 20 Questions

Question 1

Events need to be scheduled in rooms. Their time intervals are: - Event A: 8:00 to 14:00 - Event B: 17:00 to 25:00 - Event C: 8:00 to 13:00 - Event D: 14:00 to 21:00 - Event E: 10:00 to 16:00 - Event F: 14:00 to 17:00 - Event G: 9:00 to 16:00 What is the minimum number of rooms needed to schedule all events without overlap?

Step-by-step solution (Interval Graph):

1. Plot intervals on timeline:
Event A: ██████ from 8 to 14
Event B: ████████ from 17 to 25
Event C: █████ from 8 to 13
Event D: ███████ from 14 to 21
Event E: ██████ from 10 to 16
Event F: ███ from 14 to 17
Event G: ███████ from 9 to 16

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

Answer: 5 rooms needed

interval, overlap, room-allocation, graph-theory, optimization

Question 2

A hospital needs one doctor on-call each day for 30 days. There are 4 doctors: Dr. Jones, Dr. Smith, Dr. Brown, Dr. Lee. If the schedule is as fair as possible, how many days will each doctor be on-call?

Step-by-step solution:

1. Total on-call days: 30
2. Base days per doctor: 30 ÷ 4 = 7 days
3. Remainder: 2 doctor(s) get one extra day

Answer: 7 days, with 2 doctor(s) getting 8 days

on-call, availability, emergency, medical, fairness

Question 3

An event runs for 8 hours. Staff needed per hour: - Hour 1: 6 - Hour 2: 4 - Hour 3: 3 - Hour 4: 5 - Hour 5: 6 (PEAK) - Hour 6: 3 - Hour 7: 6 - Hour 8: 4 What is the minimum number of staff needed if staff can work multiple consecutive hours?

Step-by-step solution:

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

Answer: 6 staff

event, staff, venue, hospitality, logistics

Question 4

Computer Science courses with prerequisites: - CS201 requires CS101 - CS301 requires CS201 - CS102 requires CS101 - CS202 requires CS301 Which courses can be taken in the first semester?

Step-by-step solution:

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

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

Answer: CS101

course, registration, prerequisite, academic, student

Question 5

Events need to be scheduled in rooms. Their time intervals are: - Event A: 13:00 to 14:00 - Event B: 20:00 to 21:00 - Event C: 3:00 to 5:00 - Event D: 4:00 to 5:00 - Event E: 8:00 to 11:00 What is the minimum number of rooms needed to schedule all events without overlap?

Step-by-step solution (Interval Graph):

1. Plot intervals on timeline:
Event A: █ from 13 to 14
Event B: █ from 20 to 21
Event C: ██ from 3 to 5
Event D: █ from 4 to 5
Event E: ███ from 8 to 11

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

Answer: 2 rooms needed

interval, overlap, room-allocation, graph-theory, optimization

Question 6

A machine can process up to 6 jobs simultaneously as a batch. Each batch takes 40 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 × 40 = 80 minutes

Answer: 80 minutes

batch, parallel-machines, capacity, manufacturing, optimization

Question 7

A production line needs to manufacture: - Product D: 3 units (each takes 4 hours) - Product A: 2 units (each takes 1 hours) - Product B: 1 units (each takes 1 hours) Setup time required when switching products: - P->P: 1 hour What is the minimum total time if production starts with Product B?

Step-by-step solution:

Production Sequencing with Setup Times:
1. Calculate total production time (without setup):
- Product D: 3 x 4 = 12 hours
- Product A: 2 x 1 = 2 hours
- Product B: 1 x 1 = 1 hours
- Base production time: 15 hours

2. Minimize setup time by batching:
- Optimal sequence: Product B -> Product D -> Product D -> Product D -> Product A -> Product A
3. Total with setups:
- Product B: 1 hours
- Setup Product B→Product D: 1 hour + Product D: 4 hours
- Product D: 4 hours (no setup)
- Product D: 4 hours (no setup)
- Setup Product D→Product A: 1 hour + Product A: 1 hours
- Product A: 1 hours (no setup)

Total: 17 hours

Key Strategy: Batch identical products together to minimize setup changes.

manufacturing, setup-time, sequencing, optimization

Question 8

Computer Science courses with prerequisites: - CS401 requires CS201 - CS101 requires CS201 - CS301 requires CS101 - CS202 requires CS101 Which courses can be taken in the first semester?

Step-by-step solution:

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

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

Answer: CS201

course, registration, prerequisite, academic, student

Question 9

Four tasks (Task 4, Task 3, Task 1, Task 2) must be scheduled with these constraints: 1. Task 4 must be before Task 3 2. Task 3 must be before Task 1 3. Task 4 must be before Task 1 4. Task 2 must be after Task 1 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 3
2. Task 3 must be before Task 1
3. Task 4 must be before Task 1
4. Task 2 must be after Task 1

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

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

Question 10

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

Step-by-step solution:

1. Round trip time: 40 × 2 = 80 minutes
2. Headway: 15 minutes
3. Buses needed: ⌈80 ÷ 15⌉ = 6

Answer: 6 buses

bus, timetable, frequency, public-transport, optimization

Question 11

A conference needs to schedule 6 sessions across 3 time slots and 3 rooms. Each room can hold one session per slot. The constraints are: - Dr. Taylor can only speak at 11:00-12:00 - AI Ethics and Data Science cannot be in the same time slot - Prof. Wilson and Prof. Garcia must speak in consecutive time slots - Cloud Computing must be in Hall A Which speaker presents the Data Science session?

Step-by-step solution:

Scheduling Grid Analysis:
1. Fix direct constraints:
- Dr. Taylor at 11:00-12:00
- Cloud Computing in Hall A
2. Apply consecutive constraint: Prof. Wilson and Prof. Garcia in consecutive slots
3. Apply conflict constraint: AI Ethics and Data Science not together

4. Final Schedule:
9:00-10:00:
- Hall A: Data Science by Dr. Lee
- Hall B: AI Ethics by Dr. Chen
- Hall C: Robotics by Prof. Wilson
10:00-11:00:
- Hall A: Cybersecurity by Prof. Jones
- Hall B: IoT by Prof. Garcia
- Hall C: (empty)
11:00-12:00:
- Hall A: Cloud Computing by Dr. Taylor
- Hall B: (empty)
- Hall C: (empty)

Answer: Dr. Lee presents Data Science

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

multi-constraint, professional, CSP, CAT-level

Question 12

A job shop has 3 machines. Jobs and their routes: - Job A: M1 → M3 → M2 with times 14, 22, 17 - Job B: M1 → M3 → M2 with times 11, 23, 23 - Job C: M3 → M1 → M2 with times 38, 34, 27 What is a lower bound on the minimum makespan?

Step-by-step solution:

1. Machine load bound: 83
2. Job processing bound: 99
3. Lower bound: 99

Answer: 99

job-shop, routing, complex, np-hard, advanced

Question 13

A conference needs to schedule 6 sessions across 3 time slots and 3 rooms. Each room can hold one session per slot. The constraints are: - Dr. Chen can only speak at 10:00-11:00 - AI Ethics and Robotics cannot be in the same time slot - Dr. Lee and Prof. Garcia must speak in consecutive time slots - Cloud Computing must be in Hall A Which speaker presents the AI Ethics session?

Step-by-step solution:

Scheduling Grid Analysis:
1. Fix direct constraints:
- Dr. Chen at 10:00-11:00
- Cloud Computing in Hall A
2. Apply consecutive constraint: Dr. Lee and Prof. Garcia in consecutive slots
3. Apply conflict constraint: AI Ethics and Robotics not together

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

Answer: Prof. Garcia presents AI Ethics

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

multi-constraint, professional, CSP, CAT-level

Question 14

A company has 7 employees working in 2 shifts. Shifts rotate every 14 days. After how many days does an employee return to the same shift pattern?

Step-by-step solution:

1. Rotation cycle: 7 employees × 14 days = 98 days
2. Verification: Each employee cycles through all shifts

Answer: 98 days

rotation, cyclic, shift-pattern, workforce, healthcare

Question 15

A project has 6 tasks with the following requirements: - T1: Duration 4 days, Requires 3 resources - T2: Duration 2 days, Requires 3 resources - T3: Duration 4 days, Requires 3 resources - T4: Duration 3 days, Requires 1 resources - T5: Duration 2 days, Requires 2 resources - T6: Duration 3 days, Requires 1 resources Dependencies: - T1 must be completed before T2 - T5 must be completed before T6 Maximum 5 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: 4 days, 3 resources
- T2: 2 days, 3 resources
- T3: 4 days, 3 resources
- T4: 3 days, 1 resources
- T5: 2 days, 2 resources
- T6: 3 days, 1 resources

2. Available resources: 5 per day

3. Dependencies considered

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

5. Total time: 5 days

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

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

Question 16

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 17

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

Step-by-step solution:

1. Jobs per batch: 5
2. Number of batches: ⌈18 ÷ 5⌉ = 4
3. Total time: 4 × 53 = 212 minutes

Answer: 212 minutes

batch, parallel-machines, capacity, manufacturing, optimization

Question 18

A hospital needs one doctor on-call each day for 30 days. There are 4 doctors: Dr. Brown, Dr. Lee, Dr. Jones, Dr. Patel. If the schedule is as fair as possible, how many days will each doctor be on-call?

Step-by-step solution:

1. Total on-call days: 30
2. Base days per doctor: 30 ÷ 4 = 7 days
3. Remainder: 2 doctor(s) get one extra day

Answer: 7 days, with 2 doctor(s) getting 8 days

on-call, availability, emergency, medical, fairness

Question 19

Four colleagues need to schedule a meeting. Their available time slots are: - 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 What is the earliest time slot when all four can meet?

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.

multi-person, time-slots, availability

Question 20

A hospital needs one doctor on-call each day for 30 days. There are 5 doctors: Dr. Lee, Dr. Brown, Dr. Smith, Dr. Patel, Dr. Jones. If the schedule is as fair as possible, how many days will each doctor be on-call?

Step-by-step solution:

1. Total on-call days: 30
2. Base days per doctor: 30 ÷ 5 = 6 days
3. Remainder: 0 doctor(s) get one extra day

Answer: 6 days each

on-call, availability, emergency, medical, fairness

Scheduling - Beginner-Intermediate Level: temporal logic BEGINNER-INTERMEDIATE

What you'll learn in this worksheet:

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Question 13

Question 14

Question 15

Question 16

Question 17

Question 18

Question 19

Question 20