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

Journal Article

Haouari, Mohamed . 2003

• رابط المنشور على الويب: An Improved Max-Flow Based Lower Bound for Minimizing Maximum Lateness on Identical Parallel machines
• الوسوم: Identical parallel machines, Release dates, Due dates, Maximum lateness, Lower bound, Preemption
• المجلة \ الصحيفة: Operations Research Letters
• رقم العدد: 1
• رقم الإصدار السنوي: 31
• الصفحات: 49–52

مستخلص المنشور

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.