论文部分内容阅读
调度(Scheduling)研究的问题是将有限的资源实行任务的时间分配,以实现某性能指标最优。而现实中的调度问题多为复杂的组合优化问题,如车间调度问题(Job-shop Scheduling Problem, JSP)即为典型的NP难问题,在其复杂多项式时间内难以找到最优解。因车间调度问题的研究具有理论和实践意义,所以一直是调度问题中研究的热点,也是难点,近年来对JSP的研究主要集中于利用现代智能算法以及各种改进的混合算法求近似解。本文利用新兴的蚁群优化算法,结合约束满足技术对车间调度问题进行求解。蚁群优化算法(Ant Colony Optimization Algorithm, ACO)因其鲁棒性、正反馈性、并行性等优点,已经在求解很多组合优化问题方面取得了良好的效果,算法的效率也很高;但是蚁群算法也存在着收敛慢、易停滞的缺点。本文在充分利用蚁群算法优点的前提下,对蚁群算法进行改进,采用全局和局部信息素更新相结合的信息素更新策略以避免算法过早停滞;而对于收敛慢的缺点,采用约束满足技术修剪搜索空间,以加快搜索速度,提高算法效率。另外,蚁群算法中各参数的选取对算法的性能也有较大的影响,本文也给出了详细的分析。约束满足(Constraint Satisfaction)作为求解大规模组合优化问题的方法之一,能对搜索空间进行修剪,从而大大减少搜索的次数和时间。一致性预处理技术和约束传播技术可以在搜索过程中动态地排除不符合约束条件的区域,使搜索过程不必遍历所有的变量和赋值,只须保持局部一致性。混合算法充分利用二者的优点,约束满足技术的使用使得蚁群算法的效率有了更进一步的提高,从而很快地找到可行解和最佳方案。本文通过实验验证了混合算法的可行性,并通过标准的车间调度实例进行仿真实验,实验结果的分析比较(和其他算法进行比较)证明,改进的混合算法不但具有可行性,而且具有高效性。另外,本文还实现了实际生产调度过程中并行机存在时的调度情况,使算法的求解更符合实际生产的要求。最后,本文利用C++Builder和Microsoft SQL Server 2000开发了车问调度系统,实现了车间资源的信息管理;并在系统中集成了混合算法的调度优化。