| 本文已被：浏览 5132次 下载 6410次 |
码上扫一扫！ |
|
|
| 基于逻辑"或"约束优化的实时系统设计 |
|
刘军祥1,2, 王永吉1,3, 王源1,2, 邢建生1,2, 曾海涛1,2
|
|
1.中国科学院,软件研究所,互联网软件技术实验室,北京,100080;2.中国科学院,研究生院,北京,100049;3.计算机科学重点实验室(中国科学院,软件研究所),北京,100080
|
|
| 摘要: |
| 标准约束优化问题的等式或不等式约束之间是逻辑"与"关系,目前已经有很多高效、收敛的优化算法.但是,在实际应用中有很多更一般的约束优化问题,其等式或不等式约束之间不仅包含逻辑"与"关系,而且还包含逻辑"或"关系,现有的针对标准约束优化问题的各种算法不再适用.给出一种新的数学变换方法,把具有逻辑"或"关系的不等式约束转换为一组具有逻辑"与"关系的不等式,并应用到实时单调速率调度算法的可调度性判定充要条件中,把实时系统设计表示成混合布尔型整数规划问题,利用经典的分支定界法求解.实验部分指出了各种方法的优缺点. |
| 关键词: 标准约束优化问题 不等式约束 分支定界法 混合布尔型整数规划 单调速率(RM) |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.60373053 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2003AA1Z2220 (国家高技术研究发展计划(863)); the Hundred Talents of the Chinese Academy of S |
|
| Real-Time System Design Based on Logic OR Constrained Optimization |
|
LIU Jun-Xiang,WANG Yong-Ji,WANG Yuan,XING Jian-Sheng,ZENG Hai-Tao
|
| Abstract: |
| The logic relationship among the equality and inequality constraints in a standard constrained optimization problem (SCOP) is the logical AND. Various efficient, convergent and robust algorithms have been developed for such a SCOP. However, a more general constrained optimization problem (GCOP) with not only logic AND but also OR relationships exists in many practical applications. In order to solve such a generalized problem, a new mathematical transformations which can transfer a set of inequalities with logic OR into inequalities with logic AND relationships is developed. This transformation provides a necessary and sufficient condition which enables us to formulate real-time system design as a mixed Boolean-integer programming problem. A Branch and Bound Algorithm is applied to find the optimal solution. Experimental results have been presented to show its merits. |
| Key words: SCOP (standard constrained optimization problem) inequality constraint branch and bound algorithm mixed Boolean-integer programming (MBP) RM (rate monotonic) |
