论文部分内容阅读
差异工件单机批调度问题( Single Batch-processing Machine with Non-identical Job Sizes,SBMN)是同时考虑到工件尺寸和机器约束的一类二维调度问题,是生产调度领域一个新的研究方向,在实际经济活动中有广泛的应用。然而差异工件单机批调度问题的特点使得其具有高复杂性,从而给问题的求解提出了新的挑战。因此,寻找有效的算法对差异工件单机批调度问题进行优化具有重要的应用意义。微粒群优化算法是一种新型的群体智能优化技术,具有结构简单、通用性强、容易实现、群体记忆等优点。目前,微粒群算法已在多个领域获得了广泛应用,但是在离散性组合优化问题中的应用较少。本文就如何改进传统的微粒群算法、如何改进离散的微粒群算法及如何将改进的两种算法应用到差异工件单机批调度问题的求解中展开了深入研究。本文的主要创新点如下:(1)研究了基于云模型的改进传统PSO算法在差异工件单机批调度问题中的应用。首先提出了一种新的随机位置和速度更新方法,然后在根据微粒的适应度划分种群的基础上,引入基于云模型的自适应参数策略对不同的子群采用不同的惯性权重生成方法,最后将该算法应用于优化制造跨度的差异工件单机批调度问题的求解。实验比较结果表明,改进后的混合算法相比遗传算法和传统的PSO算法具有更好的优化效果。(2)研究了基于云模型的改进离散PSO算法在差异工件单机批调度问题中的应用。首先重新定义了用于求解差异工件单机批调度问题的离散PSO算法的各类操作算子,然后通过定义种群“聚集”信息与参数间的多条定性关联规则,构造新的云自适应参数调整策略,动态调整算法的惯性权重和多样性系数。实验结果表明,提出的基于云模型的改进离散PSO算法在求解SBMN问题时表现出优异的性能,特别是在大规模问题的求解中,算法的搜索质量大大提高。