Scheduling Worksheet 29 - Expert Level (priority scheduling) | 20 Questions

Question 1

Four team members (Eva, Alice, David, Charlie) must be assigned to four unique tasks (Deployment, Documentation, Design, Testing). The assignments must follow these rules: 1. Eva must handle Deployment. 2. Alice cannot handle Testing. 3. David and Charlie must be adjacent in (Deployment → Documentation → Design → Testing). Based on the constraints, which statement MUST be true?

No valid schedule found given the constraints. The only guaranteed assignment is: Eva must handle Deployment.
If the constraints cannot all be satisfied, fallback is to force rule 1's assignment.

multi-person, shift-scheduling, constraint-satisfaction, puzzle

Question 2

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

2. Check for transitive relationships:
- From Constraint 1: Task 2 before Task 4
- From Constraint 2: Task 4 before Task 3
- By transitivity: Task 2 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

Question 3

Four team members (Bob, Eva, Frank, Charlie) must be assigned to four unique tasks (Design, Testing, Deployment, Documentation). The assignments must follow these rules: 1. Bob must handle Design. 2. Eva cannot handle Documentation. 3. Frank and Charlie must be adjacent in (Design → Testing → Deployment → Documentation). Based on the constraints, which statement MUST be true?

No valid schedule found given the constraints. The only guaranteed assignment is: Bob must handle Design.
If the constraints cannot all be satisfied, fallback is to force rule 1's assignment.

multi-person, shift-scheduling, constraint-satisfaction, puzzle

Question 4

Given these scheduling constraints: - Task B must be before Task C - Task D must be after Task C - Task A must be immediately after Task B Is a valid schedule possible?

Step-by-step solution:

1. Check for cycles: No circular dependencies
2. Check immediate constraints: Can be satisfied
3. Conclusion: Yes, a valid schedule exists

Answer: Yes, a valid schedule exists

feasibility, satisfiability, constraint-check, logic, verification

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 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 7

Hospital OR scheduling with 2 operating rooms (8 hours each): - Emergency: 35 min, Priority 1 - Urgent: 77 min, Priority 2 - Elective A: 83 min, Priority 3 - Elective B: 72 min, Priority 3 - Routine: 123 min, Priority 4 Can all surgeries be completed in one day?

Step-by-step solution:

1. Total surgery time: 390 min = 6.5 hours
2. Available OR hours: 2 × 8 = 16 hours
3. Total ≤ Available → Can complete in one day

Answer: All surgeries can be scheduled within one day

surgery, operating-room, hospital, healthcare, critical

Question 8

A school needs to schedule 6 courses. The following courses have overlapping students and cannot be scheduled at the same time: - Physics conflicts with History - Physics conflicts with Biology - Physics conflicts with English - Biology conflicts with Chemistry - Biology conflicts with History - Biology conflicts with Math - Math conflicts with Chemistry - Math conflicts with English - Chemistry conflicts with History 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:
- Physics: Slot 1
- Biology: Slot 2
- Math: Slot 1
- Chemistry: Slot 3
- History: Slot 4
- English: Slot 2

3. Colors/slots used: 4

Answer: Minimum 4 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 9

A machine needs to process 4 jobs. Processing times: - Job D: 52 minutes - Job A: 43 minutes - Job E: 52 minutes - Job C: 89 minutes The machine breaks down at 92 minutes and takes 31 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 A → Job D → Job E → Job C
2. Simulate processing with breakdown:
- Job A: 0 → 43
- Job D: Starts at 43, breakdown at 92 (49 min completed), repair 31 min, resume 3 min → completes at 126
- Job E: 126 → 178
- Job C: 178 → 267

3. Total makespan: 267 minutes
4. Delay caused by breakdown: 31 minutes

Answer: 267 minutes

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

manufacturing, breakdown, recovery, simulation, reliability

Question 10

A delivery company has vehicles with capacity 19 units. Customer demands: - C1: 8 units - C2: 8 units - C3: 5 units - C4: 3 units - C5: 3 units What is the minimum number of vehicles needed to serve all customers?

Step-by-step solution:

1. Total demand: 27
2. Vehicle capacity: 19
3. Minimum vehicles: ⌈27 ÷ 19⌉ = 2

Answer: 2 vehicles

vehicle-routing, logistics, delivery, optimization, VRP

Question 11

A project consists of the following tasks: - Task A (Requirements Analysis): 2 days, Depends on: None - Task B (Design): 3 days, Depends on: A - Task C (Database Setup): 2 days, Depends on: A - Task D (Development): 5 days, Depends on: B, C - Task E (Testing): 3 days, Depends on: D What is the minimum number of days required to complete the entire project?

Step-by-step solution:

Critical Path Method (CPM):
1. Identify dependencies and calculate earliest start times:
- Task A: Starts on Day 0, Duration 2 days
Finishes on Day 2
- Task B: Starts on Day 2, Duration 3 days
Finishes on Day 5
- Task C: Starts on Day 2, Duration 2 days
Finishes on Day 4
- Task D: Starts on Day 5, Duration 5 days
Finishes on Day 10
- Task E: Starts on Day 10, Duration 3 days
Finishes on Day 13

2. Task timeline:
Task A: Days 0-2
Task B: Days 2-5 (after A)
Task C: Days 2-4 (after A)
Task D: Days 5-10 (after B and C)
Task E: Days 10-13 (after D)

3. Critical path: A -> B -> D -> E (or A -> C -> D -> E)
4. Total project duration: 13 days

Key Strategy: Calculate earliest start time for each task based on predecessor completion times; the longest path determines total duration.

project-management, dependencies, critical-path, professional

Question 12

A delivery company has vehicles with capacity 16 units. Customer demands: - C1: 5 units - C2: 6 units - C3: 3 units - C4: 5 units What is the minimum number of vehicles needed to serve all customers?

Step-by-step solution:

1. Total demand: 19
2. Vehicle capacity: 16
3. Minimum vehicles: ⌈19 ÷ 16⌉ = 2

Answer: 2 vehicles

vehicle-routing, logistics, delivery, optimization, VRP

Question 13

A football league has 6 teams. Each team plays every other team twice (home and away). What is the minimum number of rounds needed if each round has the maximum possible matches?

Step-by-step solution:

1. Total matches in double round-robin: 6 × (6-1) = 30
2. Maximum matches per round: 3
3. Minimum rounds: 30 ÷ 3 = 5 rounds

Answer: 5 rounds

league, fixture, home-away, sports, optimization

Question 14

A JIT manufacturing system has 4 jobs with the following data: | Job | Processing (min) | Due Date (min) | Early Penalty/min | Late Penalty/min | |-----|-----------------|----------------|-------------------|------------------| | Component C | 31 | 74 | 1 | 20 | | Component A | 55 | 125 | 5 | 15 | | Component D | 32 | 44 | 1 | 18 | | Component B | 57 | 93 | 3 | 17 | 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 C → Component B → Component A
2. Calculate completion times and penalties:
- Component D: completes at 32, due 44, early by 12 min → penalty 12
- Component C: completes at 63, due 74, early by 11 min → penalty 11
- Component B: completes at 120, due 93, late by 27 min → penalty 459
- Component A: completes at 175, due 125, late by 50 min → penalty 750

3. Total penalty: 1232

Answer: 1232 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 15

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

Step-by-step solution:

1. Total slots available: (4 × 60) ÷ 20 = 12
2. Patients: 8
3. All patients can be scheduled

Answer: All 8 patients can be scheduled

clinic, appointment, doctor, healthcare, wait-time

Question 16

Round Robin scheduling with time quantum = 2: - P1: Burst time 5 - P2: Burst time 11 - P3: Burst time 14 - P4: Burst time 5 - P5: Burst time 13 What is the average completion time?

Step-by-step solution:

1. Round Robin simulation:
2. Completion times:
- P1: 21
- P4: 26
- P2: 41
- P3: 47
- P5: 48

3. Average: 183 ÷ 5 = 36.6

Answer: 36.6

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

Question 17

Eight people attend seminars in four different months (January, March, May, July) on two dates (5th and 15th). Two people attend per month. The constraints are: - V attends in March - U attends on the 15th - Exactly two people attend between Q and S - P attends in the same month as W In which month does Q attend?

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

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

4. Verification:
All constraints satisfied with Q in March

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

month-based, date-based, gap-constraints, banking-exams

Question 18

A factory produces Widgets with a 80% learning curve (each doubling of cumulative production reduces time by 19%). First unit takes 97 minutes. Batch sizes (in order): 40, 10, 30 units. What is the TOTAL production time for all batches (in minutes, rounded to nearest minute)?

Step-by-step solution (Learning Curve):

1. Learning curve formula: T_n = T_1 × n^-0.322
where exponent = log(0.8)/log(2) = -0.322

2. Calculate cumulative time using integration:
Cumulative time for N units = T_1 × N^0.6780719051126377 / (learning_exponent + 1)

3. Time per batch:
Batch 1 (40 units): 43.6 minutes
Batch 2 (10 units): 28.5 minutes
Batch 3 (30 units): 25.4 minutes

4. Total time: 97.5 ≈ 98 minutes

Key Strategy: Learning curve reduces time with repetition; use cumulative average method for batch calculations.

learning-curve, improvement, batch-processing, industrial, experience

Question 19

A flow shop has 2 machines (M1 → M2). Jobs and processing times (M1, M2): - Job A: (26, 20) - Job B: (33, 39) - Job C: (37, 32) - Job D: (50, 45) - Job E: (40, 22) - Job F: (48, 18) Using Johnson's Rule, what is the minimum makespan?

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 D → Job C → Job E → Job A → Job F → Job B
3. Calculate makespan: 273

Answer: 273

flow-shop, multi-stage, makespan, johnsons-rule, manufacturing

Question 20

A student has 7 days to prepare for three exams: Mathematics, Computer Science, Physics. The required preparation days are: - Mathematics: 3 days - Computer Science: 1 days - Physics: 2 days If the student follows the optimal schedule starting today, on which day will the last exam be?

Step-by-step solution:

Timeline Planning Method:
1. Calculate total preparation time needed:
- Mathematics: 3 days
- Computer Science: 1 days
- Physics: 2 days
- Total: 6 days

2. Available days: 7 days
3. Extra buffer days: 1 days
4. Optimal schedule:
- Days 1-3: Prepare for Mathematics
- Day 4: Mathematics exam
- Days 5-5: Prepare for Computer Science
- Day 6: Computer Science exam
- Days 7-8: Prepare for Physics
- Day 9: Physics exam

Answer: The last exam will be on Day 7

Key Strategy: Schedule exams immediately after preparation period ends, accounting for all required prep days.

academic, deadline, preparation, timeline

Scheduling - Expert Level: priority scheduling EXPERT

What you'll learn in this worksheet: