海军装备部装备项目管理中心 林丽娜 胡子颖

本文给出一种基于图约束装箱算法的构件调度策略生成算法，将构件动态部署和调度策略的生成描述成新的装箱问题。实验表明，本文给出的基于图约束装箱算法的构件调度策略生成算法，能够较好地解决大规模构件的动态部署问题。

现有信息系统软件服务构件的部署和调度，通常采用两种简化的策略：基于预案的方法、人工调度方法。而对于抽象问题而言，构件部署问题属于典型的装箱问题，是复杂的组合最优化问题。从计算复杂性来讲，装箱问题是一个NP完全问题，难以精确求解，当下的解决方案是近似算法，包括FF,NF,FFD,BFD算法。

基于预案的调度方法，是事先人为制定好构件与CPU计算单元的对应关系，制定构件缺省加载配置表。基于预案的调度方法缺点在于，对于大型复杂系统软件，完全人工制定预案的方式工作量大，预案效果难以得到保证。完全人工调度的方法则存在效率低和难以给出最优方案的问题。

本文所给出的基于图约束装箱算法BPPR的构件调度策略生成方法，以嵌入式信息处理设备中的CPU为顶点，以CPU计算资源为顶点权重，以单个CPU上RapidIO高速数据传输通道数量限制顶点的最大度约束，以不同CPU之间构件的通信链路为边，形成一张图。因此，该类构件部署的问题即转化为一个最优图的求解问题，要求满足构件运行资源和数据传输需求的同时，使得占用的CPU数目最小，需要建立的高速数据链路数量最少。……