DocumentCode :
3371688
Title :
Optimization in real time
Author :
Chu, Lon-Chan ; Wah, Benjamin W.
Author_Institution :
Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA
fYear :
1991
fDate :
4-6 Dec 1991
Firstpage :
150
Lastpage :
159
Abstract :
A search algorithm called real-time search (RTS) for solving combinatorial optimization problems under real-time constraints is presented. The algorithm aims at finding the best possible solution within a given deadline. Since this objective is generally not achievable without first solving the problem, the authors use an alternative heuristic objective that looks for the solution with the best ascertained approximation degree. The algorithm schedules a sequence of guided depth-first searches, each searching for a more accurate solution (based on the approximation degree set), or solutions deeper in the search tree (based on the threshold set), or a combination of both. Five versions of the RTS algorithm for setting approximation degrees and/or thresholds are formulated, evaluated, and analyzed. The authors describe the experimental results obtained for the five versions of RTS
Keywords :
optimisation; real-time systems; scheduling; search problems; trees (mathematics); RTS algorithm; approximation degree; best possible solution; combinatorial optimization problems; guided depth-first searches; heuristic objective; real-time constraints; real-time search; search algorithm; search tree; Algorithm design and analysis; Approximation algorithms; Artificial intelligence; Constraint optimization; Contracts; Heuristic algorithms; Minimization methods; Operations research; Real time systems; Scheduling algorithm;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Real-Time Systems Symposium, 1991. Proceedings., Twelfth
Conference_Location :
San Antonio, TX
Print_ISBN :
0-8186-2450-7
Type :
conf
DOI :
10.1109/REAL.1991.160368
Filename :
160368
Link To Document :
بازگشت