Abstract
We consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to release dates. New procedures are proposed for effectively bounding the completion time of a given job that is processed at a given position. New assignment-based lower bounds are derived as well as an enhanced mathematical programming formulation. Our computational analysis shows a consistent tightness of the proposed lower bounds and a high outperformance of the enhanced mathematical formulation with respect to the classical one.