多目标动态规划时段轮换并行算法

TIME CYCLING PARALLEL ALGORITHM OF MULTIOBJECTIVE DYNAMIC PROGRAMMING

针对ＳＩＭＤ和ＭＩＭＤ结构的并行机提出多目标动态规划时段轮换并行算法，多目标动态规划的时段轮换迭代算法，将全过程优化问题转化成子过程优化问题，然后在子过程非劣解集中寻找全过程非劣解．这样，将多目标动态规划内存不足的问题转化成时间问题，然后利用并行机超高速运算的优势来有效地解决内存不足问题．通过时间复杂性、加速比分析及实例说明了算法的有效性及优越性．

Time cycling parallel algorithm of multiobjective dynamic programming are presented for SIMD and MIMD parallel computers, respectively. The time cycling algorithm of multiobjective dynamic programming is such a method that transforms the optimization problem of whole procedure into the optimization problem of subprocedures, then finds the non-inferior solutions of whole procedure in the set of the non-inferior solutions of subprocedures. With this idea, the problem of memories of multiobjective dynamic programming can be transformed into a problem of time,then the problem can be solved effectively through parallel computers with very high computing speeds.