论文部分内容阅读
调度问题是组合优化领域中的一类重要问题,在工业生产、柔性制造系统、现代物流、计算机科学等领域有着非常广泛的应用。批调度问题是重要的一类现代调度问题,它打破了经典调度问题中对机器的限制,即一台机器可以同时加工多个工件而非仅仅一个工件。差异工件批调度问题是对传统批调度问题的进一步扩展,即工件是有差异的,同一批中工件的总尺寸不能超过批的容量限制,因此,包含在各个批中的工件数可能不同。这类问题比经典调度问题、传统批调度问题更加复杂,但它更加接近实际工作环境,对此问题的研究具有重要的理论经济价值。本文首先介绍关于调度基本知识,接着从调度到经典调度,再到批调度,最后引出差异工件批调度的介绍。并说明了差异工件批调度的研究现状。对差异工件单机批调度问题的性质进行分析研究,给出了该问题的数学规划模型,并对已有的若干启发式算法进行改进。其次,本文介绍了差分进化算法的原理及背景,分析了该算法的特点以及在解决连续性优化问题上的优势。同时,指出差分进化算法在解决具有离散特性的调度问题上的劣势。针对调度问题的离散特性,我们重新设计了差分进化算法的交叉操作和变异操作。并在算法核心思想不变的前提下提出具有新的迭代模式的新差分进化算法。接着,通过大量试验比较,确定了新差分进化算法的参数配置。利用与文献中相同的方法产生若干种类算例,并对算法进行仿真实验。同时把本文所提的新差分进化算法与经典文献中具有代表性的两个算法(模拟退火算法和遗传算法)进行比较,来检测新差分进化算法的性能。试验结果表明,与文献中以往算法相比,差异工件单机批调度问题的新差分进化算法在仿真实验中具有更好的效果。最后,在总结全文的基础上,对今后的研究提出了建议和展望。