• • 上一篇    下一篇

极大-加线性系统的单局部优化及其在任务调度中的应用

杨威黎1,陶跃钢1,王彩璐2   

  1. 1. 河北工业大学人工智能与数据科学学院,天津 300130; 2. 北京理工大学自动化学院, 北京 100081
  • 出版日期:2021-06-25 发布日期:2021-09-17

杨威黎, 陶跃钢, 王彩璐. 极大-加线性系统的单局部优化及其在任务调度中的应用[J]. 系统科学与数学, 2021, 41(6): 1507-1519.

YANG Weili, TAO Yuegang, WANG Cailu. Single Local Optimization for Max-Plus Linear Systems and Its Application in Task Scheduling[J]. Journal of Systems Science and Mathematical Sciences, 2021, 41(6): 1507-1519.

Single Local Optimization for Max-Plus Linear Systems and Its Application in Task Scheduling

YANG Weili1,TAO Yuegang1, WANG Cailu2   

  1. 1. School of Artificial Intelligence, Hebei University of Technology, Tianjin 300130; 2. School of Automation, Beijing Institute of Technology, Beijing 100
  • Online:2021-06-25 Published:2021-09-17
研究极大-加线性系统的单局部优化. 对于决策变量取实值和非负实值两种情形, 证明单局部优化问题存在最优解, 特别地, 当决策变量取实值时, 最优解是唯一的. 通过 分析具有仿射等式约束的极大-加线性方程组的可解性以及解的结构, 给出寻求单局部最 优解的多项式算法. 同时, 还将极大-加线性系统的单局部优化方法用于计算机操作系统 任务调度方案设计, 以使总体任务的完成时间最早.
The single local optimization of max-plus linear systems is considered. For both the cases that the decision variables are real and non-negative, it is proven that the locally optimal solutions exist, in particular, for the single local optimization without the non-negative constraint, the locally optimal solution is unique. Two polynomial algorithms are developed to find the locally optimal solutions by solving systems of max-plus linear equations with affine equality constraints. Furthermore, the single local optimization is applied to design the scheduling scheme of computer operating systems, so that the completion time of the overall task are the earliest.
()
No related articles found!
阅读次数
全文


摘要