提出了一种求解机组组合问题的改进拉格朗日松弛算法。与现有此类方法相比，此算法进行了以下三个方面改进：基于启发式排序法得到较优的拉格朗日乘子初值；改进了动态规划求解单机问题时的累计费用以获得更优的机组启停决策；采用自适应性次梯度法结合集结投影次梯度法的联合优化策略加快算法收敛速度。10机到100机的6个算例表明，自适应性次梯度法和集结投影次梯度法的联合优化策略更易跳出其单一策略时的振荡现象，从而加快收敛。