为解决计算网格中有向无环图表示的截止期约束下的工作流时间费用优化问题,提出了一个新的启发式优化算法——相对效费比算法。该算法首先根据调度系数得到初步方案,再逐步调整,当方案完工时间小于截止期时,用时间换成本,选择成本消减最快的节点进行调整,中选服务有最大的正相对效费比值;当方案完工时间超过截止期时,用成本换时间,调整成本增加最慢服务的节点,中选服务有最大的负相对效费比值,该方法在保证截止期约束的同时能有效降低总成本。通过大量模拟实验和与最小关键路径、正向分层费用优化算法、逆向分层费用优化算法的比较,证明了相对效费比的有效性。