基于空间收缩的演化算法与其应用.研究

《基于空间收缩的演化算法与其应用.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．1课题背景第一章绪论随着过程工业生产规模的大型化、激烈的市场竞争和市场需求的多样化，现代企业不但对过程控制的要求越来越高，而且对优质、高效的生产管理的要求也越来越强烈。自动化孤岛模式已不再适应现代工业企业的生产要求，国内外企业已把注意力转移到节能降耗、少投入多产出的高效生产模式上，即集直接数字控制、监控优化、生产调度、经营决策等功能于一体的综合自动化模式(cws)。生产管理与调度是综合自动化系统的核心，直接关系到企业的经济效益和社会效益。随着综合自动化的实施，人们已经认识到，单纯提高个别生产装置的控制

2、水平，寻求局部最优的投入产出比远远低于提高整体调度水平的投入产出比。一个合理的调度方案能给企业带来很大的经济效益。生产调度即在一定时间内进行可用资源的分配和加工任务的排序，以满足某个或某些特定的生产指标。由于调度主要涉及一定时间内共享资源的可用性和设备分配等问题，因此生产调度大都形成混合整数线性规划模型(MILP)或混合整数非线性规划模型(Mrt忆v)。从数学角度讲，调度就是对上述模型的求解问题，是一个多目标、多约束的优化问题。优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术，作为一个重要

3、的科学分支一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应用，如系统工程、人工智能、模式识别、生产调度、计算机工程等等。优化方法涉及的工程领域很广，问题的种类与性质繁多。归纳第4页而言，最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到满足用户要求的问题的解。在很多情况下，一个最优化问题可以用许多方法加以解决，而每种方法又能够

4、采取多种算法予以实现。寻找一种快速而有效的算法的研究正方兴未艾。但目前在实际生产过程中的优化问题大多是NPC问题，也就是说，随着问题规模的扩大，会发生组合爆炸，算法复杂性呈指数增长，求解难度也相应增大。虽然人们早己采用了遗传算法、模拟退火等现代优化算法解决这类问题，但是由于算法本身的局限性，在很多问题上还无法达到高精度和高效率。在现代优化算法的基础上，从对搜索空间进行优化的角度入手，引入另一种寻优机制——空间划分与空间收缩，这类对搜索空间进行选择淘汰或压缩的优化方法，正凭借其高效、快速的优点日益受到人们的

5、重视。实现生产过程的最优化，对提高生产效率与效益、节省资源具有重要的作用。同时优化方法的理论研究对改进算法性能、拓宽算法应用领域、完善算法体系同样具有重要作用。因此，优化理论与算法的研究是一个同时具有理论意义和应用价值的重要课题㈦】。1．2生产调度1．2．1调度的概念调度问题就是在满足一定约束的前提下，寻求某一调度目标最优的过第5页山东大学硕士学位论文程，也就是在资源基础上确定最优的行为序列。当行为是确定时，这类问题就转化为优化问题，在第一次世界大战中Gantt图的应用标志着形式化的调度模型的出现，随后采

6、用的关键路径(CriticalPath)法成为调度问题中最广泛运用的工具【41。在五十年代中期，随着调度问题形式化数学模型的出现，其研究也越来越引起人们的重视。直至七十年代，调度问题的研究还局限于运筹学(OperationsResearch)范畴。随着对调度问题计算复杂性的研究，调度问题中的大部分被归结为NPC问题【51。在自动化及计算机领域中，调度问题都得到了深入的研究，在计算机集成制造系统(CIMS)及柔性制造系统①Ms)中，如何安排各工序的处理次序及占用资源，使之满足一定优化目标(如完成时间最短等)

7、，这就是调度所要研究的问题[61。典型的调度问题有生产调度(ProductionScheduling)、工程调度(ProjectScheduling)、电力调度(ElectricPowerScheduling)、铁路时刻表(R越1wayTime-tabling)等。1．2．2生产调度生产调度就是在一定的时间内，进行可用共享资源的分配和加工任务的排序，以满足某个或某些特定的生产指标。它和生产计划的区别在于：生产计划主要关心资源的需求和粗分配，而生产调度主要涉及加工作业的具体安排和资源的详细分配【71。理论研

8、究中，生产调度问题常又称为排序问题或资源分配问题。在实际生产领域，生产调度问题被称为生产作业计划，它在企业生产管第6页理决策层次中的位置如图1．1所示。图1．1企业生产管理决策层次框图企业的生产调度属于层次模型中的协调层，与之相应的层次是下面的生产过程和上面的计划管理。生产调度与短期计划并没有明显的界线，如果短期计划时间较短，则无须再分为几个调度期，或把短期计划作为调度问题来处理。生产的调度问题可以粗略地定义为：在一定的时间范