搜索
调度：原理、算法及系统课程论文FLOWSHOP调度问题研究1FlowShop调度问题描述FlowShop调度问题是很多实际流水线生产调度问题的简化模型，也是一个典型的NPhard问题，因此其研究具有重要的理论意义和工程价值，他也是目前研究最广泛的一类典型调度问题。FlowShop调度问题研究m台机器上n个工件的流水加工过程，每个工件在各机器上的加工顺序相同，同时约定每个工件在每台机器上只加工一次，每台机器一次在某一时刻只能够加工一个工件，各工件在各机器上的加工时间和准备时间已知，要求得到某调度方案使得某项指标最优。进一步，若约定每台机器加工的各工件顺序相同，则称其为置换FlowShop问题。2FlowShop调度问题研究尽管相对JobShop调度而言，FlowShop的工艺约束比较简单，但是它仍然是一个非常复杂和困难的组合优化问题其NP-hard特性和强大的工程背景使其一直成为理论界和工程领域研究的热点问题2.1FLOWSHOP调度问题的启发式算法[1]2针对以总完工时间最小为目标的FlowShop调度问题，基于全局插入和任务交换两种方法，提出一个启发式算法RP。RP算法的种子序列采用分组加权规则产生，并在调度改进阶段依据种子序列应用全局插入和任务交换方法对当前调度进行改进，以提高算法的搜索能力。模拟实验表明，在调度结果的平均质量、最好调度的获取能力和算法稳定性方面，RP算法优于目前最好的启发式算法RZ、WY、Ⅸ和FL。针对总完工时间最小为目标的FlowShop调度问题，本文提出一个启发式算法RP，RP种子序列按分组加权规则产生，在调度序列构造阶段依据种子序列采用RZ—I／con(PWE)结构对当前序列进行改进，以提高算法搜索能力。实验结果表明RP具有很好的性能，对于不同规模的大多数问题，RP均能取得最好调度；其所得调度的平均质量及算法稳定性也明显优于其他4个启发式算法。虽然RP所需CPU时间比WY和FL要多，但多项式时间复杂性使其能够满足制造加工系统中实时性的需求。在时间和质量要求较高的环境中，RP算法能够更有效地解决以总完工时间最短为目标的FlowShop调度问题。2.2Flow．shop调度问题的自适应模拟退火算法[2]为求得一个强NP-难问题—FlowShop调度问题的最优解或近优解，提出一种自适应模拟退火算法，本算法采用一种基于区段特性的特殊邻域结构、简便的目标函数计算方法和自适应退火策略，通过FlowShop调度问题的基准测试问题的实验，数值结果证实了该方法的有效性。自适应模拟退火算法采用了简化的邻域结构、快速简便的目标函数计算方法和自适应退火策略，加速了算法的运行速度，同时寻优性能明显提高，数值计算结果证实了本算法的性能明显强于目前著名的Taillard的禁忌搜索算法和Osman的模拟退火算法．2.3多目标FlowShop调度问题的改进TA求解算法[3]应用TA算法的关键在于如何合理设置一系列递减的门槛值T,传统TA算法中邻域搜索结果对于门槛值设置没有反馈作用,这种开环控制方式,使得求解过程盲目性较大,无法合适权衡搜索的分散性与收敛性,很难找到既能使算法收敛,又3能使其摆脱局部最优的T值序列.一般来讲T值对于问题的类型和规模是敏感的,只有通过大量试验,经验地确定算法的参数.离散最优化问题,尤其多目标优化问题,往往存在多个局部最优,为避免陷入局部最优,算法参数设定和搜索的控制方式尤为关键.速度和质量是算法设计中的两个矛盾指标,门槛值设定控制是TA综合上述二者的关键性算法构件.加大T值下降速率无疑会提高算法速度,但很可能陷入局部最优.考虑在搜索过程陷入局部最优时,适时提高门槛值,可以摆脱局部最优.因此,改进TA算法设计的基本思想为:在搜索过程中,以较大的T值下降率实现算法的快速性,同时允许对T值进行必要的小范围局部增加,保证寻求到合适的T值序列,避免陷入局部最优;引入搜索进展对于算法构件的反馈机制,考虑T值设定控制、邻域搜索强度（次数）和算法终止条件相配合，由算法过程自动触发。计算比较结果表明：对于上述各规模问题，ATA算法求解质量均好于H&C，随着问题规模加大，表现得更加明显。像所有迭代改进算法一样，ATA的平均计算时间要长于H&C，这是由于构造型启发方法固有的近于直觉的启发准则可免去大量的搜索探测，因而拥有很快的速度，但其解的质量极大依赖于启发准则对于解性质的刻划，对于不同的问题实例，解的稳定性有所波动。ATA算法可以求得较稳定的高质量解，从这一意义上优上H&C算法。42.4供应链下FlowShop调度问题的多目标混合算法研究[4]针对供应链环境下一类多目标FlowShop调度问题，构建了相关模型并提出一种新的基于PSO、SOM和VNS的混合算法。该算法运用新的思想和多种优化策略，可在单个解的质量、解分布的均匀与分布的广度3个指标上同时达到远优于原算法的效果。仿真实验显示，该算法对求解该类调度问题十分有效。关键词：多目标；供应链；FlowShop调度问题；自组织神经网络算法；粒子群；变邻域搜索.关于多目标算法的优劣目前学界并无一个统一的评价标准，研究人员所使用的评判方法也多种多样D-az]，评价指标主要有解的分布范围、分布均匀程度以及单个解的质餐。因此，要得到更优的解集就要将以上三者有机地综合起来。然而，由于各目标进化方向上的不统一，研究人员在追求单个解的质量的过程中往往不得不让前两者做出极大让步，导致解集的范围往往过于局限，无法给决策者提供更多不同的选择方案。出于兼顾三者的目的，本文算法将首先凭借PSO粒子群算法在单目标问题求解上的优势，分别找到2个进化方向上的最优个体，再利用SoM自组织神经网络算法良好的学习能力，向先前得到的2个解序列学习并由此得到2个目标值都较为优秀的解，最后通过拟合Pareto曲线并找出均匀分布点的方法实现最终结果的优化。用本文算法求解供应链下多目标FlowShop调度问题的具体过程如下：(1)随机生成初始种群。(2)对生成的种群分别以目标值一和目标值二为评估标准，通过新的PS0算法进行处理，生成2个解集，如图1a所示。(3)将得到的3个解集的解作为输入序列，运用SOM自组织神经网络算法进行处理，通过向输入序列的学习，生成一个原始的兼顾2个目标值的解前端，如图1b所示。(4)执行VNS变邻域搜索算法，进一步优化各个所得解，如图1c所示。(5)得到解集的Pareto前端，如图1d中的1、2所示。(6)对Pareto解集进行曲线拟合，计算曲线长度并得到曲线的等长分割点，通过这些分割点对Pareto前端的集进行筛选，得到分布更均匀的多目标解集，方便5决策者从不同解中找到所需的满意解，如图1d中的3所示。6本文对供应链环境下的一类单工厂多分销中心FlowShop调度问题进行了分析，建立了相关模型并提出了一种新的解决多目标问题的混合算法。实验结果显示，该算法很好地解决了多目标进化中不同目标间进化方向不同所带来的相互干扰，从而在解的质量、分布的广度上都达到了预期的效果；除此之外，算法还对解的均匀度做了优化，避免了目标值函数近似的解对决策者的影响。2.5基于遗传算法的混合Flow-shop调度方法[5]混合Flow-shop调度问题(Hybridflow-shopschedulingproblem,HFSP)是一般Flow-shop调度问题的推广,由于在某些工序上存在并行机器,所以比一般的Flow-shop调度问题更复杂.本文提出了遗传算法求解混合Flow-shop调度问题的方法,给出了一种新的编码方法,设计了相应的交叉和变异操作算子,能够保证个体的合法性,同时又具有遗传算法本身所要求的随机性.利用模糊控制原理设计了借助于现有城市道路交通控制系统对道路服务水平进行控制的模糊控制算法,控制算法通过改变道路进口信号灯的绿灯显示时间得以实现这种思想设计的模糊控制器简单方便,易于实现,而且在实际应用中不会影响原有系统的性能,在有关模糊规则推理方面,本文采用了专家的知识和经验,建立了规则库城市网络交通流的变化,是有规律的利用专家的知识和经验对道路服务水平进行控制,控制效果是很理想的.在实际对道路服务水平进行控制时,为了使模糊控制器能够及时决策和适应交通流的动态变化,模糊控制器的设计采用离线计算产生一个模糊控制总表,在系统运行时只需对偏差和偏差变化的实测值离散并量化到相应的论域中,再根据它们的量化值查模糊控制总表,即可得到控制量,本文设计的模糊控制算法可以7用到高速公路服务水平的控制和城市干道服务水平的控制上。2.6加工时间依赖开工时间的FlowShop调度问题[6]在这类问题中工件的加工时间是开工时间的简单线性函数机器间满足某种优势关系对于这类问题当目标函数是极小化最大完工时间时尽管比相应的经典问题复杂但仍存在多项式算法如果目标函数是极小化加权完工时间和或极小化最大延误则经典问题中的结论未必成立。本文讨论了工件的加工时间是开工时间的简单线性函数机器满足优势关系的Flowshop问题对于这类问题当目标函数是极小化最大完工时间机器满足一般增减优势关系时问题存在多项式算法即相应的经典问题中的结论可以推广到工件的加工时间是开工时间的简单线性函数的Flowshop问题如果目标函数是极小化加权完工时间和或极小化最大延误则只有机器满足单调增加优势关系时问题才存在多项式算法而对于机器满足单调减少优势关系或一般增减优势关系时相应的经典问题中的结论并不成立由此可见加工时间是开工时间的函数的调度问题和经典调度问题有很大区别。对于一般情况的加工时间是开工时间简单线性函数的Flowshop调度问题虽然不能用本文结论直接得到求解最优调度的多项式算法但这些结论可以在构造求解一般性问题的启发式算法和分枝定界算法时起到一定作用。2.7具有简单线性恶化加工时间的FlowShop调度问题[7]讨论工件具有简单线性恶化加工时间的FloWShop调度问题，对于两台机器目标函数为极小化最大完工时间的FloWShop调度问题，证明了利用Johnson规则可以求得最优调度·对于多台机器的一般FloWShop调度问题，如果工件在各机器上的加工时间均相等，目标函数为极小化最大完工时间或最大延误的问题可以转化为单机调度问题·如果目标函数为极小化完工时间和，则利用SPT规则可以求得最优调度·本文讨论了工件具有简单线性恶化加工时间的Flowshop调度问题·对于两台机器目标函数为极小化最大完工时间的Flowshop调度问题，证明了利用8Johnson规则可以求得最优调度·对于多台机器的一般Flowshop调度问题，当工件在各机器上的加工时间均相等，目标函数为极小化最大完工时间或最大延误的问题可以转化为单机调度问题·如果目标函数为极小化完工时间和，则利用SPT规则可以求得最优调度·2.8具有零等待的不确定性FlowShop调度问题[8]针对实际的生产环境中存在的数据模糊、不确定的情况，采用模糊数学的方法来处理数据的不确定性，在模糊规划理论的基础上，建立了处于时间不确定条件下的具体零等待的flowshop模糊调度问题的模型，通过模糊截集的方法将其进行了转化。并在模糊运算的基础上，借鉴自然界生物免疫系统的概念和机理，提出了解决此类调度问题的模糊免疫调度算法。通过仿真试验，表明了该模型所有效性和算法的较好的收敛效率。本文对不确定条件下的生产调度问题进行了研究，针对流程工业中处理时间不确定的具有零等待的flowshop调度问题，在模糊数的!截集的基础上建立了相应的调度数学模型，并且结合免疫算法的特点，采用模糊免疫调度算法进行求解，仿真实验表明了该模型和算法的可行性和有效性。2.9利用DNA遗传算法求解Flow-Shop调度问题[9]由于经典遗传算法在求解调度问题尤其是处理复杂的、混淆的和多任务问题时不够灵活且计算速度慢，论文引入DNA技术借助生物学理论对其进行改进。DNA遗传算法继承了遗传算法全局搜索的能力，同时利用DNA双螺旋结构和碱基互补配对原则进行编码运算，提高了算法的有效性和收敛速度，从而很好地解决了NP-hard性质的Flow—Shop调度问题。在该