In this paper, we introduce a new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|rj|Lmax which dominates the well-known preemptive lower bound. We show that, in some cases, the proposed bound strictly dominates the preemptive one while having the same complexity.

We consider the problem of minimizing the makespan on identical parallel machines subject to release dates and delivery times. The objective of this paper is to develop exact branch-and-bound algorithms to solve this strongly NP-hard problem. A preprocessing algorithm is devised to speed up the convergence of the proposed algorithms, and a new tight bounding scheme is introduced. The search tree is also reduced using a polynomial selection algorithm. Extensive computational experiments show that instances with up to 300 jobs can be solved exactly in a moderate CPU time.