以绿色制造为背景,假定机器设备具有不同的能源消耗成本或维护成本,研究了一类考虑成本限制的平行机调度问题.调度的目标是最小化最大延迟时间.为该问题建立了整数规划模型MIP,设计了改进的EDD(earliest due date firstly)算法,命名为MEDD.由于考虑成本限制,证明了MEDD算法的可行性,并进而理论分析了算法的最坏误差界.通过算例说明了算法的执行情况,同时采用大量随机数据实验验证算法的性能.对于小规模问题,将MEDD的解与MIP的精确解进行了对比;对于大规模问题,由于MIP精确解难以获得,以MIP对应的线性规划松弛模型MLP的最优值为下界对MEDD算法的解进行了衡量.实验结果表明了所构建MEDD算法的有效性.