 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
In computer science and operations research, Fernandez’s bound (FB) is a lower-bounding technique used in exact algorithms for multiprocessor scheduling problems, particularly within branch-and-bound frameworks. It provides tighter lower bounds than some earlier methods (e.g., Hu's bound).
Using Big O notation, a naïve computation of the bound requires O(n3) time, as it examines O(n2) task combinations, each taking O(n) time in the worst case. Efficient implementations reduce the complexity to O(n2).
