现有的求解周期性任务最小相对截止期的方法均假定任务集是采取抢占式EDF调度算法，并不适用于当任务为基于非抢占式EDF调度算法的场合，如实时通信领域。在分析了非抢占式EDF调度算法的可调度性判定条件基础上，提出了基于非抢占式EDF调度算法下周期性任务最小相对截止期的计算算法。算法通过逐渐增加任务的相对截止期直到使任务集变为可调度的方式，实现某个任务相对截止期的最小化。仿真实验表明该算法具有较好的计算复杂度。