【摘要】 对分布式内存机器中相互依赖多任务的优化调度问题,将约束条件归纳为任务约束、链路约束和资源约束,建立了允许任务复制情况下多任务静态调度问题的数学模型.描述了有向无回路图的构造性定义,指出问题一定有不超过所有任务执行时间总和的解.推出以最短时间完成任务集所需的最小资源数与任务数一样大.阐明了问题具有可计算性.研究结果改进了原有的问题描述和数学模型,使对问题的认识更深入,并有利于寻求更好的求解策略.更多还原

【Abstract】 Optimal scheduling of mutual dependent multi-tasks in distributed-memory machines was considered.A mathematical model was built for static scheduling multi-tasks under the task duplication after constraints were divided into task constraints,link ones and resource ones.A constructible definition of the directed acyclic graph was described,and the reason why exists a solution that does not exceed the total execution time of all tasks was explained.It is proved that the problem′s optimal solution is not worse than that of a scheduling problem having unlimited resources if the number of resources is equal to the number of the tasks.The computability of the scheduling was elucidated.The results could improve the description of the scheduling and mathematic formulation,making the scheduling explicit and being helpful to find good solving strategies.更多还原