Comparison of three classical lower bounds for the Parallel Machines Scheduling Problem

This paper compares three classical lower bounds for the Parallel Machines Scheduling Problem (PMSP). The first lower bound considered is the makespan of Jackson’s Pseudo Preemptive Schedule (JPPS). The second is the preemptive bound, which is obtained by relaxing the non-preemption constraint, and the third is based on Energetic Reasoning (ER). To compare these three bounds, we first provide a rigorous mathematical characterization. Specifically, we introduce a mathematical definition of the ER-derived lower bound as the smallest value of the trial makespan that results in a successful ER feasibility test. This definition relies on the fundamental concepts of critical intervals and specific operations that we called crossing operations, for which we give some theoretical properties. We establish an Energy theorem , which provides an analytical formulation of the energetic lower bound. In an extension of the JPPS and ER lower bounds, we give an analytical formulation of the preemptive bound. From the analytical characterization of these three bounds, we attempt to analyze their relative performances. In particular, we find that the ER lower bound differs from JPPS because on some machines at least two operations must be scheduled for ER. The preemptive bound differs from JPPS because idle periods may be required in an optimal preemptive schedule. Interestingly, these three characterizations are quite similar, and so can provide insight into the ways in which the bounds differ. Our results can be directly extended to the cumulative scheduling problem, and we report some experimental experiments that compare these bounds and confirm the theoretical results stated above.