Scheduling with Constraints

Overview

Students investigate how real-world tasks can be assigned to workers or machines efficiently. Building on prior work with representing tasks and constraints, they use the list processing algorithm to create schedules, then compare schedules and discuss whether a schedule is optimal using critical-path reasoning.

Learning intentions

Students will be able to:

• Recognize situations that can be represented as scheduling problems.
• Apply the list processing algorithm to schedule independent tasks.
• Calculate and compare the total completion time of different schedules.
• Use critical-path reasoning to decide whether a schedule is optimal or can be improved.

Success criteria

• I can identify the tasks, processing times, and available workers in a scheduling problem.
• I can assign tasks in order using the list processing algorithm.
• I can calculate when all tasks will be completed.
• I can explain why a schedule is or is not optimal using evidence from my schedule.

Curriculum links

• Discrete Mathematics — using heuristic algorithms to solve real-world problems.
• Discrete Mathematics — recognizing situations appropriate for modeling or scheduling.
• Discrete Mathematics — solving independent task scheduling problems using the list processing algorithm.
• Discrete Mathematics — determining whether a schedule is optimal using critical-path reasoning and list processing.

Lesson structure (60 minutes)

1. 0–7 min · Hook: Which team finishes first? Teacher opens the scheduling hook and learning target slides and presents six school-event tasks with different completion times and two available workers. Students make a quick individual prediction about the best assignment, then explain their reasoning to a partner.

2. 7–17 min · Identify the problem. Teacher models how to identify independent tasks, task durations, available workers, and the objective of minimizing the finishing time; emphasize that this is a scheduling problem rather than a bin-packing problem. Students annotate the example and answer two oral checks: “What information matters?” and “What are we trying to minimize?”

3. 17–27 min · Model the algorithm. Using the list processing example slides, teacher demonstrates the list processing algorithm: order tasks from longest to shortest, assign each task to the worker with the smallest current load, and update the schedule after every assignment. Students copy the running table and complete the final two assignments with teacher guidance.

4. 27–43 min · Partner investigation. Teacher distributes the independent task scheduling practice worksheet to pairs and directs students to complete Problems 1–3, recording each worker’s assignments, running load, and final completion time. Students use the algorithm, check calculations with their partner, and justify why the task order matters. With 13 students, create six pairs and one teacher-supported trio.

5. 43–52 min · Compare and critique. Teacher displays the schedule comparison and critical-path discussion slides and asks pairs to compare their schedule with a deliberately inefficient schedule. Students calculate both finishing times, identify the latest-completing worker, and discuss whether the list-processing schedule is optimal for the given independent tasks. Invite two pairs to share different strategies or corrections.

6. 52–60 min · Exit ticket and debrief. Teacher returns to the summary and exit-ticket prompt slides and asks students to complete the final worksheet item independently: schedule four tasks of 9, 7, 5, and 3 minutes across two workers and state the completion time. Students submit the response and complete the sentence, “The list processing algorithm is useful when…”

Resources

• the complete scheduling slide deck
• the independent task scheduling practice worksheet
• Whiteboard or display
• Student pencils and highlighters
• Calculators, if permitted
• Timer
• Two different colored markers for worker schedules
• Prepared example of an inefficient schedule

Assessment

• During modeling, check whether students correctly identify task duration, worker load, assignment order, and completion time.
• Circulate during partner work and use questioning: “Why did you assign that task there?” and “Which worker has the smallest current load?”
• Collect the independent exit response. Look for a correct task order, valid assignments, accurate finishing time, and a written explanation connecting the result to the algorithm.

Differentiation

• Support students with a partially completed worker-load table, color-coded tasks, and the sentence starter: “I assigned this task to Worker ___ because ___ currently has the smaller load.”
• Read the word problem aloud and clarify terms such as task, duration, independent, worker load, and completion time; pair students strategically and allow calculator use for arithmetic.
• For students needing additional structure, have them physically point to or highlight the worker with the smaller current load before each assignment.
• Challenge early finishers to test whether a different task order produces a shorter schedule, then explain whether their result proves the schedule is optimal or only provides a better comparison.