A general lower bound for the makespan problem

The problem of scheduling jobs on identical parallel processors to minimize makespan is NP-hard. We introduce a general lower bound which includes as special cases bounds that either dominate, or are equivalent to, lower bounds previously proposed in the literature. The general lower bound unifies earlier results and can be used to identify new bounds, improve previously proposed bounds, and extend bounds for the problem with identical processor ready times to the problem with variable processor ready times.