Makespan

Makespan, in scheduling theory, is the total time required to complete a given set of tasks from the start of the first task to the finish of the last one. It is the completion time of the last operation in a schedule and is commonly denoted as Cmax. The makespan depends on the order of execution and the allocation of tasks to resources, and it serves as a primary objective in many scheduling problems.

In a single-machine setting with n jobs and processing times p1, p2, ..., pn, the makespan equals the sum of the processing times when the jobs are scheduled back-to-back with no idle time. If release dates, due dates, or precedence constraints are present, the makespan is the completion time of the last job under the chosen schedule.

On multiple identical machines (m machines), the makespan is the maximum total processing time assigned to any machine in the schedule. A natural lower bound is the greater of the average load, sum(pj)/m, and the largest individual processing time, max(pj). In more complex settings such as flow shops or job shops, Cmax refers to the finish time of the last operation across all machines and jobs.

Minimizing makespan is a central objective in many contexts, including manufacturing, parallel computing, project management, and cloud resource allocation. The problem is computationally hard in general (often NP-hard), with exact algorithms available for some special cases (for example, Johnson’s rule for two-machine flow shop) and a variety of heuristic and approximation methods used for larger or more complex instances.