论文部分内容阅读
生产调度是现代制造业管理的关键和核心技术,其任务主要是分配企业有限的资源,达到经济上或性能上的需求目标。合理、最优的生产调度方案不仅可以提高企业的综合管理水平,而且可以为企业带来快捷、直接、显著的经济效益。
本文对离散型制造业生产调度问题进行了系统的探讨,对生产调度相关特殊实际问题进行分析、建模,并提出算法对其进行优化。其目的是从理论和实践寻找解决离散型制造业生产调度实际问题的有效途径,为有关技术的进一步完善、发展和开发提供一定的理论基础和实践方法。
本文主要研究成果归纳如下:
(1)全面总结调度的研究成果,介绍了生产调度问题的研究现状、分类、优化调度问题的主要目标;分析了调度问题的特点及研究生产调度问题的理论、方法及技术。
(2)分析了群体智能的生物学特征,系统深入地探讨了群智能中的粒子群算法。介绍了初始粒子群算法的原理,给出其流程图,从数学上证明了初始粒子群算法是收敛的;总结了粒子群算法发展的成果,分析得出粒子群算法各算子的意义及功能,探讨了算法参数变化对优化问题的效率影响;介绍了评价算法效率的性能指标,并概括了粒子群算法在各个领域的应用。
(3)描述了Flow-Shop(FSSP)和Job-Shop(JSSP)调度问题的特性及区别,建立了JSSP的makespan数学模型;借鉴初始粒子群算法的思想及遗传算法交叉操作,采用整数编码,提出适用于调度问题的类粒子群算法(SPSO),给出该算法的操作算子、递推方程、算法步骤,将它与初始粒子群算法(OPSO)及GA的特性进行比较;将SPSO算法应用于优化FSSP,仿真实验验证它优化FSSP的效率比GA优良,然后再对SPSO算法进行改进,也采用整数编码,加入类似于GA算法的变异操作,给出改进的递推方程、步骤,并将改进型的类粒子群算法应用于优化JSSP,仿真实验验证其效率比GA优良。
(4)兼顾局部与全局版粒子群算法各自的优点,充分共享局部与全局最优粒子的信息,采用实数编码,提出了局部与全局相结合的粒子群算法(LGCPSO),给出了该算法的递推方程及流程图,并从数学上证明了该算法是收敛的;将LGCPSO算法应用于连续函数的优化,仿真实验显示其效率比OPSO算法更有效;然后再对LGCPSO算法进行改进,改进型的LGCPSO算法(ILGCPSO)在整个迭代过程中,随机地共享了每一代的局部最优粒子信息,给出其递推方程、伪代码,并分析了它的收敛性;介绍了粒子群算法优化离散问题时,将实数编码转化成整数编码的SPV方法,将ILGCPSO算法应用于优化FSSP和JSSP,其优化的结果明显比OPSO算法及GA优良;通过大量仿真实验研究,找出了ILGCPSO算法优化调度问题时效率高的参数。
(5)针对生产实际需要,建立了基于利润最大化为目标,具有相同交货期约束及提前/脱期惩罚的FSSP(MPPFSSPRCD)与JSSP(MPPJSSPRCD)数学模型,并分析了该类问题的复杂度;针对它们的特点,提出了相应的双重遗传算法,该算法由两个GA嵌套而成,外层功能为选择加工的工件,内层为所选工件的加工排序,给出了该算法的内外层操作及流程图,用双重遗传算法优化MPPFSSPRCD,仿真结果表明是可行有效的。然后将双重遗传算法拓展为双重混合算法,给出该算法的内外层编码操作、步骤,再将其应用于优化MPPJSSPRCD,仿真实验表明其优化该类特殊问题非常有效。
(6)依据生产实际,建立了基于最大化加工工件数目,具有相同与不同交货期约束的FSSP(MJNRCDFSSP,MJNRDDFSSP),及最大化加工工件数目具有相同与不同交货期约束的JSSP(MJNRCDJSSP,MJNRDDJSSP)数学模型;给出了MJNRCDFSSP的一个性质,基于该性质提出了优化MJNRCDFSSP的改进型双重混合算法,它很大程度上提高了算法的效率;针对上述特殊问题,首次提出了倒序画MJNRDDFSSP和MJNRDDJSSP的GATT图方法,并提出了插入粒子的粒子群算法(IPPSO)及改进型的插入粒子的粒子群算法(IIPPSO),给出了他们的模型,伪代码及收敛性分析。并用IPPSO、IIPPSO、OPSO算法及GA对随机产生的MJNRDDFSSP和MJNRDDJSSP各一个实例进行仿真实验,比较分析仿真的结果显示前两者算法比后两者都有效。
(7)本文研究了多目标、不同交货期约束的并行机单工序车间生产调度(MOSODD)问题,建立了该类问题的数学模型;针对该问题的特殊性,提出了局部与全局结合的替换部分坏粒子的粒子群(LGCDPSO)算法,给出了算法的模型、伪代码,将它应用于优化上述调度问题,通过仿真研究表明LGCDPSO算法效率比OPSO及GA明显提高。