Asymptotic behaviour of some scheduling algorithms

Asymptotic behaviour of some scheduling algorithms

0.00 Avg rating0 Votes
Article ID: iaor19941876
Country: Singapore
Volume: 10
Issue: 1
Start Page Number: 79
End Page Number: 91
Publication Date: May 1993
Journal: Asia-Pacific Journal of Operational Research
Authors:
Keywords: computational analysis
Abstract:

All scheduling theory reviews show that determining the optimal solution for large-scale problems requires a large amount of processing time and involves a search procedure, which calculates and estimates a large set of feasible schedules. As an alternative, approximate and heuristic methods are suitable from the point of view of the processing time required. However, the methodical basis for their implementation is often rather weak since they are mostly based on a series of experimental calculations that are not always convincing. The proof of applicability of some approximate methods may be obtained by examining the asymptotic properties of the solutions. Such an approach is described for several scheduling theory models. It is proved that approximate solutions obtained by simple heuristic rules converge to the optimal solution asymptotically. As real problems usually are of a large scale, the result gives grounds for the application of simple algorithms to practical planning.

Reviews

Required fields are marked *. Your email address will not be published.