Unit-Time Job Scheduling

Unit-time job scheduling assigns jobs of duration one to time slots on a given number of identical machines. In the precedence-constrained problem, an acyclic digraph specifies which jobs must finish before others start. Each graph vertex represents a job and each directed graph edge requires job to precede job . A job occupies one machine for its entire slot.

With machines and jobs, a schedule ending by slot is a function such that at most jobs have any one value of , and for every directed graph edge . The objective is to minimize the final completion time, called the makespan. For three unrelated jobs on two machines, the minimum makespan is 2.