多重资源约束下的作业车间优化调度研究

《多重资源约束下的作业车间优化调度研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、广东工业大学T学硕士学位论文且工件的加工路线不同为单件车间(Job．Shop)调度的基本特征；而所有工件的加工路线相同为流水车间(Flow-Shop)调度的基本特征【9】。本文所研究的基本类型为单件车间作业调度(Job．ShopScheduling)，而具体研究的模型为非标准的作业车间调度问题，它与典型的、标准的作业车间调度问题主要区别在于，标准作业车间调度中每道工序排序前均指定机器，而非标准作业车间调度中每道工序在排序前并不指定机器，只指定所属的工作单元，具体的加工机器将在运算中智能地选择；根据性能指标，可分为基于调度

2、费用和调度性能的指标两大类。根据生产环境的特点，也可以将调度问题分为确定性调度和随机性调度问题。根据作业的加工特点，也可以将调度问题分为静态调度和动态调度。实际中，车间调度的类型往往是Job．Shop型，且是动态的。目前研究比较多的是作业车间调度问题‘10圳1和流水车间调度问题‘121，并随着对各类调度问题研究的深入及各种交叉学科的发展，出现了许多新的车间调度理论【13．151和方法【161。研究人员经过多年的研究，提出了上百种调度算法，这些调度算法大致可以划分为如图卜1所示的不同类别【l71。图1-1调度算法的划分Fi

3、g．1一lSchedulingaritl珈eticpartition在当前对单件车间作业调度的研究中，主要集中对标准作业车间调度问题的4第一章绪论研究。它主要研究n个工件在m台机器上的加工组合排序问题，它是一种特殊的组合优化问题，它在学术界上被证明是NP完全问题【18之o】，早在20世纪60年代，人们就开始了解决这一问题的研究。目前国内外的很多学者对该问题都作了深入的理论研究，大致产生了两类研究方法：一类是为了得到问题的精确解而进行的定性研究，它可以得到全局最优解，但所能求解的问题规模比较小，而且速度慢；另一类则利用近似

4、算法来寻求该问题的近似解，即近似求解方法。车间调度问题的精确求解主要集中在分支定界法的研究，它是主要的枚举方法之一。用动态结构分支来描述所有的可行排序的解空间。在对最优解的搜索过程中，它允许把大部分的非最优点分支从搜索过程中去掉，从而避免完全枚举。但它只能解决小规模的车间调度问题，与车间实际调度应用还有较大的差距。目前，对该方法的研究重点放在如何改进分枝定界策略，以便在搜索的最初阶段排除更多的非最优点，从而大幅度减少运算时间【19】。车间调度问题的各种近似算法，诸如基于规则的调度算法，是指系统运行时，根据一定的规则和策略

5、来决定下一步操作的调度方法。它是动态调度的典型代表，它的优点是直观、简单实用，而且花费的求解时间较少、易于实现，在实际生产中获得了广泛的应用，但其往往不能对所得解的次优性进行评估。Panwalke等【2l】总结了113个调度，将调度规则分为三大类，即简单规则、复合规则、启发式规则。拉氏松弛法具有独到的优越性，在可行的时间里能对复杂的规划问题提供好的次优解，并能对解的次优性进行定量评估，近年来已成为解决复杂车间调度问题的一种重要方法。已经用拉氏松弛法解决了单机调度和多台并行机调度问题。但是解的震荡与收敛问题～直是该方法应用

6、的一个巨大障碍。启发式图搜索算法主要有宽度优先、深度优先、Beam搜索、FilteredBeam搜索以及A或者爿+算法等。么。算法将分支定界算法和动态规划相结合，常用于图的路径搜索中。理论上，彳’算法一定能够找到最优解。这些方法原理上都能找到可行解，但受到搜索时间和存储空间的限制。近年来，随着研究的深入，将生物学、物理学、人工智能以及计算机科学等多种技术引入到生产调度领域，提出了解决调度问题的新方法，各种智能算法的提出丰富了解决问题的途径，成为了一个热门课题。(1)进化算法进化算法是基于生物界“物尽天择，适者生存”的进化

7、思想基础之上而发展起来的一种随机搜索技术。主要包括了遗传算法(GA，GeneticAlgorithm)，进化广东『[业大学工学硕上学位论文规则(EP，EvolutionProgramming)、进化策略(ES，EvolutionStrategy)等。它通过模拟群体的进化过程，使得群体中的个体不断朝着好的方向发展，由于算法不苛求待求解问题的具体表达形式以及动力学特性(如：连续、可微等)，因而具有较强的鲁棒性和适应性。遗传算法的特点在于模仿自然界生物的竞争生存机制，通过将问题的解映射为遗传种群中的个体，再运用适当的遗传操作和

8、选择机制，对具有一定规模的种群实施世代更替的遗传演化，最终找出整个过程中性能最佳的个体，即求得所需问题的最优解【22】。遗传算法在求解众多标准作业车间调度问题均能得到最优解。(2)模拟退火算法模拟退火(SimulatedAnnealing，SA)算法最早由Metropolis等人提出，Kirkpatrick等首先将其