论文部分内容阅读
总拖期问题(Total Tardiness Problem，TTP)是调度问题中的经典难题。单机总拖期问题(Single Machine Total Tardiness Problem，1//T)和并行多机总拖期问题(Parallel Identical Machine Total Tardiness Problem，P//T)是许多学者研究的重点问题。然而，P//T更加符合实际生产，由于机器数量的增加必然使得加工的调度更加复杂。因此，调度工作确保尽可能准时交货，或者将总拖期降到最低，成为一大难题。蚁群算法(Ant Colony Optimization，ACO)提出至今，因为其优秀的搜索寻优特性被广泛的应用于组合优化问题，也曾被不同学者应用于单机总拖期问题。
本文在蚁群算法的基础上，针对并行多机总拖期问题的特性，提出了基于启发式规则的改进蚁群算法，并对算法进行了性能优化。其内容包括：
首先，对TTP，P//T和ACO的研究历史，现状进行了研究综述。总结了P/T的最优解调度性质，以及介绍了目前求解P//T的优秀算法。
其二，设计了将ACO用于求解P//T的复杂解构造模型和简单解构造模型。简单解构造模型在复杂解构造模型的基础上，利用P//T的数学模型以及无差别机器特性而提出。
其三，针对ACO求解P//T，提出了基于P//T分解原则的侯选列表构造方法，信息素更新策略以及改进局部搜索算法。
其四，设计了求解P//T的ACO算法实验，验证了算法的准确性，稳定性，和有效性，并且和以往算法进行仿真对比实验。同时也对ACO的参数设置优化进行了初步的研究。
最后，实验显示本文提出的改进ACO算法比以往的算法在不同程度上有所提高。