  We present a new flow-based formulation for identical parallel machine
scheduling with a regular objective function and without idle time. The
formulation is constructed with the help of a decision diagram that represents
all job sequences that respect specific ordering rules. These rules rely on a
partition of the planning horizon into, generally non-uniform, periods and do
not exclude all optimal solutions, but they constrain solutions to adhere to a
canonical form. The new formulation has numerous variables and constraints, and
hence we apply a Dantzig-Wolfe decomposition in order to compute the linear
programming relaxation in reasonable time; the resulting lower bound is
stronger than the bound from the classical time-indexed formulation. We develop
a branch-and-price framework that solves several instances from the literature
for the first time. We compare the new formulation with the time-indexed and
arc-time-indexed formulation by means of a series of computational experiments.
