Is makespan the duration of the longest task?

Not generally. A sequence of shorter dependent tasks or resource conflicts can determine a later final completion.

Can tasks finish before the makespan?

Yes. Makespan is the latest relevant completion time, so other tasks or jobs may finish much earlier.

Does minimizing makespan minimize everyone's waiting time?

No. Waiting and individual completion times are different objectives and can trade off against the time needed to finish all work.

AI Glossary / Graphs and symbolic AI / Beginner

Makespan

Definition

Makespan is the time at which all scheduled work has finished, measured from a specified scheduling origin. With the usual origin at zero, it is the maximum completion time across jobs or tasks. Minimizing makespan means trying to finish the entire collection of work as early as possible while respecting the scheduling constraints.

What it means

A schedule can complete some tasks early and still finish the overall workload late because one final task remains. Makespan focuses on that last completion. It does not add together every task's duration or every job's waiting time.

This distinction matters when activities run in parallel. Two machines each working for five hours may complete ten hours of processing within a five-hour makespan, if the jobs and constraints allow simultaneous work. Conversely, dependencies, unavailable resources, or required waiting periods can extend makespan beyond the busiest machine's processing total.

How it works

Represent each task's start, duration, and completion time. Add constraints for dependencies, resource capacity, machine availability, and other required conditions. Define a variable at least as large as every relevant completion time, then minimize it as the makespan objective.

For a job-shop model, tasks within a job must follow their specified order, and tasks assigned to the same machine cannot overlap. Other scheduling models can allow preemption, multiple identical machines, setup times, or release dates; these assumptions change the feasible schedules.

Always specify the time origin and what counts as finished. If the metric is instead elapsed time between the first actual start and the last completion, say so explicitly. Subtracting the first start can differ from measuring maximum completion time from a fixed origin when release delays are present.

Three practical examples

1. A production planner minimizes the completion time of an entire batch while respecting machine capacity and processing order.

2. A computing team schedules a collection of dependent processing tasks and measures when the last result becomes available, accounting for shared processors or other resources.

3. An event-preparation plan uses makespan to assess when every required setup activity will be finished, rather than averaging the completion times of individual activities.

Think of it this way

Think of a team preparing several dishes for a shared meal. The meal is fully ready only when the last required dish is complete, even if some dishes finished earlier.

The analogy highlights the final completion point, but it does not make makespan the only sensible objective. Finishing a delicate dish too early may be undesirable, just as a real scheduling problem can have freshness, due-date, fairness, or waiting-time concerns that makespan alone does not capture.

Worked example

Consider two jobs and two machines, with nonpreemptive tasks and all jobs available at time zero. Job A needs three hours on Machine 1 followed by four hours on Machine 2. Job B needs two hours on Machine 1 followed by one hour on Machine 2.

In Schedule 1, Machine 1 processes A from 0 to 3, then B from 3 to 5. Machine 2 processes A from 3 to 7, then B from 7 to 8. Both job orders and machine nonoverlap constraints are respected. Job completion times are 7 and 8, so makespan is 8 hours and their sum is 15.

In Schedule 2, Machine 1 processes B from 0 to 2, then A from 2 to 5. Machine 2 processes B from 2 to 3, then A from 5 to 9. Completion times are 3 and 9, so makespan is 9 hours but their sum is 12.

The first schedule finishes all work sooner; the second has a lower sum of job completion times. This hand comparison shows why the objective must be specified. It does not claim an executed optimization search.

Illustrative case study

Fictional case: Juniper Fabrication evaluates schedules for a small production batch. Management wants the whole batch ready for collection, so the planning team initially uses makespan as its primary objective.

Customer-service staff then identify an individual order whose early completion also matters. The team compares makespan with that order's completion time and considers whether an additional constraint or objective is needed. It checks machine availability and setup assumptions before interpreting the proposed schedule. This fictional case reports no actual production saving or delivery improvement.

Common misconceptions and mistakes

Do not confuse makespan with total processing time. Processing can overlap across resources, so adding durations generally answers a different question.

Do not confuse it with total completion time, average flow time, or lateness against deadlines. The worked example shows that improving one measure can worsen another. Also, a schedule with a smaller makespan is not necessarily more profitable or fair.

Finally, a solver returning a feasible schedule has not necessarily proved the minimum makespan. Distinguish a feasible result, the best result found within a budget, and a result accompanied by an optimality guarantee under the stated model.

Business use

Makespan is useful when an organization needs an entire workload completed by a common point, such as a batch handoff or a coordinated launch. Its usefulness depends on accurately modeling durations, resource limits, and dependencies.

Review critical delays and compare alternative schedules under the same assumptions. If processing times are uncertain, a nominally short makespan can be fragile; assess how disruptions affect completion. Keep the optimization model's objective separate from the broader decision: an operational plan may also need limits on overtime, individual deadlines, work-in-progress, or resource changes.

Check your understanding

Which worked-example schedule has the better makespan, and which has the smaller sum of completion times?

Answer: Schedule 1 has the better makespan, 8 rather than 9 hours. Schedule 2 has the smaller completion-time sum, 12 rather than 15, illustrating distinct scheduling objectives.

Related terms

Scheduling
Precedence constraints
Critical path
job-shop scheduling
completion time
precedence constraint
resource capacity
optimization objective
tardiness

Learn next

Draw a small two-machine schedule and calculate makespan, total processing time, and the sum of job completion times separately. Then change one dependency or resource limit and identify which values change and why.

Sources

Google OR-Tools, job-shop scheduling, precedence, machine nonoverlap, and makespan objective: https://developers.google.com/optimization/scheduling/job_shop

The two schedules and fictional fabrication case are original teaching examples. Times are deterministic for illustration; no solver run or real production performance is claimed.

Previous: Majorize-minimize Next: Malvar - He - Cutler demosaicking