Lower bounds for scheduling on identical parallel machines with heads and tails

In this paper, we investigate new lower bounds for the P|rj, qj|Cmax scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP-hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.King Saud University, Riyadh, Saudi Arabi