Fernandez's bound
(Redirected from Fernandez's method)
 | 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).[1]
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).
Further reading
[edit]- Adam, Thomas L.; Chandy, K. Mani; Dickson, J. R. (1974). "A comparison of list schedules for parallel processing systems". Communications of the ACM. 17 (12): 685–690. doi:10.1145/361604.361619.
References
[edit]- ↑ Fernandez, Eduardo B.; Bussell, Bertram (31 August 1973). "Bounds on the number of processors and time for multiprocessor optimal schedules". IEEE Transactions on Computers. 22 (8): 745–751. doi:10.1109/TC.1973.5009153.
{{cite journal}}: CS1 maint: date and year (link)
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by adding missing information. |