An Improved Max-Flow Based Lower Bound for Minimizing Maximum Lateness on Identical Parallel Machines

Journal Article

Haouari, Mohamed . 2003

• Publication Online URL: An Improved Max-Flow Based Lower Bound for Minimizing Maximum Lateness on Identical Parallel machines
• Tags: Identical parallel machines, Release dates, Due dates, Maximum lateness, Lower bound, Preemption
• Magazine \ Newspaper: Operations Research Letters
• Issue Number: 1
• Volume Number: 31
• Pages: 49–52

Publication Abstract

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.