基于顶点覆盖问题解的与/或优先约束任务调度算法

系统描述了与/或网模型及与/或优先约束任务调度的可行性判定算法.以顶点覆盖问题为基础,证明与/或优先约束任务调度最小完成时间问题是NP完全的.提出一种启发式调度算法,解决与/或优先约束任务调度最小完成时间问题.通过算法示例表明,该算法对与/或优先约束任务图具有良好的调度性能,能够得到一个最优唯与任务图,从而证明在实时优先约束任务调度中引入图优化的理论,是解决优先约束任务调度问题的一个有效途径.