拉格朗日松弛的改进及其在动态HFS调度中的应用研究

许多实际生产与物流管理问题，如生产调度问题，都可归结为组合最优化问题。由于理论上多数生产调度问题都属于NP-hard问题，而实际生产调度问题因为包含更为复杂的约束和目标函数从而多数也是强NP-hard，拉格朗日松弛（LR）算法作为一种典型的基于最优化的近似算法，因其迭代的方向性和算法的自我评价性，使它已成功用于求解多类组合最优化问题。本课题对改进LR算法进行基础研究，并以从钢铁生产中提炼出的动态HFS调度为对象进行应用研究。首先，从LR的结构和影响算法性能的要素出发，提出LR算法的改进算法；其次，从钢铁生产实际提炼出带不同生产特征的动态HFS调度问题，建立数学规划模型；然后，研究改进LR的具体实现方式；最后，以钢铁生产为背景对所提出的理论方法进行验证。本课题的研究不但扩展了现有的LR算法理论，而且其应用对实际生产具有重要的理论价值，在工业中的应用将有助于降低能耗和成本，提高产品生产率。

拉格朗日松弛算法作为基于最优化的近似算法，因其迭代的方向性和算法的自我评价性，使其已成功用于求解多类组合最优化问题。本课题对拉格朗日松弛算法的分解策略、对偶问题求解以及子问题求解策略进行研究，并探讨了它们在动态混合流水车间调度的应用。提出了结合阶段分解策略的改进拉格朗日松弛算法，将拉格朗日松弛问题分解为多个同构平行机总加权完成时间问题，子问题数即为加工阶段数，以带有限运输机的动态混合流水车间调度为研究对象对该算法进行了应用研究。提出了结合批分解策略的改进混合流水车间算法，将拉格朗日松弛问题分解为多个批级子问题，每个子问题包含多个有优先级要求的工序，子问题数即为批数，以初始阶段为批处理机的动态混合流水车间调度问题为研究对象对该算法进行了应用研究。提出了结合代理次梯度法的改进拉格朗日松弛算法，它要求近似求解松弛问题从而获得乘子更新方向，以带有限等待时间的动态混合流水车间调度问题为研究对象进行了应用研究。上述算法均通过仿真验证了有效性。针对松弛问题或子问题含工件或工序优先级要求的工件问题，提出了基于混合前后向动态规划的改进拉格朗日松弛算法，使其能处理工件（工序）有多个紧前和紧后工件（工序）的情况，分别对带工件或工序优先级要求的单机调度和多阶段混合流水车间调度进行了应用研究。围绕上述研究，发表和录用论文23篇，其中SCI收录源刊上发表论文1篇，EI收录8篇，国家自然科学基金委员会管理科学部A类重要期刊3篇，B类重要期刊2篇，中文核心期刊17篇。