调度是指在既定的约束条件下,通过合理分配资源来完成已给定的工件作业或任务,并且达到某些性能评价指标的最优。单机调度是调度领域中的一类热点问题,也是运筹学研究领域一个异常活跃的分支。理论上通常把它作为复杂调度系统的一个子系统,实际生产中比较复杂的调度问题往往可以分解为多个单机问题来解决,研究单机调度问题可以帮助理解和解决更为复杂的多机调度问题。科学合理的单机调度方案可以有效地减少设备的空置率,控制在制品库存水平,提高生产率,缩短产品生产周期和增加顾客满意度等,进而降低企业生产成本提高企业效益。因此,合理的单机调度方案及优化技术的研究与应用,是企业提高生产效率和核心竞争力的基础和关键。本文以一类单机调度问题为研究对象,以设计求解该类问题的有效算法为研究重点,设计了求解具有环约束的单机调度问题的拉格朗日松弛算法。首先,详细分析两类由工件优先级构成的优先级图：含无向环的连接图和含无向环的非连接图。然后,在上述基础上,针对实际生产环境中不同的生产特征和优化目标,建立整数规划模型,通过引入拉格朗日乘子松弛机器能力约束,形成较易求解的拉格朗日松弛问题,进而设计双向动态规划求解该问题；为了加快算法的收敛速度和保证解的质量,设计了启发式算法构造可行解；采用次梯度算法更新拉格朗日乘子。最后,对不同规模的问题进行大量的实验测试,结果表明,结合双向动态规划的拉格朗日松弛算法能够在较短的时间内获得令人满意的近优解。