Precedence Constraint

A precedence constraint expresses a partial-order relation between two tasks or activities: task i must be completed before task j can start. It is the foundational constraint family across many OR scheduling and assignment problems. In the Assembly Line Balancing Problem (Salveson 1955; Boysen, Fliedner and Scholl 2007), the station index that contains task i must be less than or equal to the station index that contains task j; in the Resource-Constrained Project Scheduling Problem (RCPSP), it cascades into activity start times; in job-shop scheduling, it dictates the operation order of a part. Precedence is typically expressed as a directed acyclic graph (DAG); the transitive closure is used for equivalent compact formulations. Variants extend it: time-lag precedence (j may start t minutes after i finishes), synchronisation (start-start, finish-finish) and generalised precedence between bundled activities. In MIP models it is usually encoded as a linear inequality between binary decision variables.