An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines |
| |
Authors: | Mohamed Haouari Anis Gharbi |
| |
Institution: | Laboratory of Mathematical Engineering, Ecole Polytechnique de Tunisie, BP 743, 2078 La Marsa, Tunisia |
| |
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. |
| |
Keywords: | Identical parallel machines Release dates Due dates Maximum lateness Lower bound Preemption |
本文献已被 ScienceDirect 等数据库收录! |