改善地理学算法求解柔性作业调度问题论文

改善地理学算法求解柔性作业调度问题论文

　　1、问题描述

　　本文采用最小化最大完工时间作为目标函数，假定：(1)工序的加工顺序既定，且在可供选择的机器上的加工时间确定；(2)所有机器相互独立，且在t＝0时刻均可用；(3)所有工件相互独立，且在t＝0时刻均可被加工；(4)工件或机器之间具有相同优先级；(5)不同工件的工序之间没有相互约束；(6)同一时刻，一台机器只能加工一个工件；(7)某个工序一旦开始加工就不能中断；(8)不考虑工件在不同机器之间的移动时间。

　　2、BBO算法求解

　　2.1算法概述

　　BBO算法是以栖息地（habitat）作为个体进行操作。栖息地适合物种生存的优劣程度用栖息适应指数（habitatsuitabilityindex，HSI）来表示，具有较高HSI的栖息地更适合物种生存。与HSI相关的因素包括该区域的降雨量、植被多样性、地貌特征和温度等，将其称为适应指数变量（suitabilityindexvariables，SIV)。HSI较高的栖息地容纳的物种数目较多，而HSI较低的栖息地容纳的物种数目较少。对于HSI较高的栖息地，随着大量物种的涌入，使得容纳的物种数趋于饱和，就会有大量的物种迁出，即有较大的迁出率和较小的迁入率。相应地，对于HSI较小的栖息地，其物种数量稀疏，就会有较多的物种迁入和较少的物种迁出，即有较大的迁入率与较小的迁出率。由于HSI与生物多样性成正比，因此新种群的迁入同时又会使HSI升高。如果某个栖息地的HSI一直较低，那可能导致该栖息地物种的灭绝，或者有大量其他物种的迁入。栖息地的迁入和迁出机制使得HSI较高的个体提供优秀个体的变量（SIV）与适应度较低的个体共享，同时又使适应度低的个体接受来自优秀个体好的特征变量，从而可能提高自己的适应度。此外，BBO算法通过对栖息地进行突变操作，使得算法具有较强的自适应能力[14]。以生物地理学数学模型为基础，将模型中各变量与优化算法中的变量以及问题空间相对应，其对应关系如表2所示。

　　2.2编码

　　本文采用两段式实数编码，一段是基于工序的工序排序编码（OperationSequence，OS)，确定各工序的加工顺序；另一段是基于机器的机器分配编码(MachineAssignment，MA)，确定每道工序的加工机器。本文采用的分段式编码能直接体现问题的约束条件，从而保证编码后个体的有效性。基于工序编码OS：长度为工序总数L，每个OS编码是所有工序的一个排列，每个工件的工序用相应的工件序号表示。从左到右依次扫描OS，第j次出现的工件序号，表示该工件的第j道工序。基于机器编码MA：长度与OS编码相等，每个编码位对应每道工序的加工机器。机器顺序是按照每个工件的加工顺序排列，不需要与基于工序的编码对应，即从第一个工件的第一道工序开始，到最后一个工件的最后一道工序结束。其中MA的每个位置表示工序选择的机器在可选机器集中的序号，而不是对应的机器号[15]。

　　3、仿真实验与结果

　　根据上述改进BBO算法的描述，采用VisualC++7.0作为编程语言，在IntelCore2CPU/主频2.00GHz/内存2.00G的电脑上进行仿真实验。为了评估该算法的性能，本文选取研究较普遍的Kacem基准问题进行测试，问题用N×M（工件数×机器数）来表示，分别是4×6、8×8、10×10、15×10柔性作业车间调度实例，对该数据集进行仿真实验，验证算法的有效性。

　　4、结论

　　本文在运用BBO算法求解FJSP时，(1)首先在初始种群中引入基于规则的启发式算法生成的优良个体，保证多样性的同时，加快了搜索进程；(2)其次在迭代过程中采用了精英保留策略，通过保留一定数量的最优或次优个体进行下次迭代，可避免由于特征迁移而导致的算法退化；(3)然后对迁移策略进行了改进，采用了更加符合FJSP的迁移率模型，当HSI从0开始变化时，迁移率的变化率不断增大，从而不断加大搜索空间，提高了全局搜索性能，随着HSI增大到最大值附近时，迁移率的变化趋于平稳，局部搜索能力得到加强；(4)最后完善自适应变异机制，HSI较低或较高的栖息地比处于稳态的栖息地更易受到外界干扰而发生突变，这样的变异有利于HSI较低的解集有机会获得提高，同时又能防止陷入局部最优。从仿真结果可以看出，改进的BBO算法表现出了良好的搜索能力和鲁棒性，能有效地求解柔性作业车间调度问题。在算法研究上，今后还可以考虑尝试用其他优化算法与BBO算法结合，取长补短设计出更好求解FJSP问题的混合算法。另外在调度问题上，我们将进一步探讨一些企业的多目标车间调度问题，满足更多企业的生产需求。

【改善地理学算法求解柔性作业调度问题论文】相关文章：

应用遗传算法解决车间作业调度问题03-07

柔性机械臂逆动力学问题的分析和求解03-20

车辆路径调度问题的启发式算法综述11-22

人文地理学论文写作问题03-27

遗传算法及其在求解TSP中的应用03-07

小学数学作业批改问题的研讨论文12-08

矿山机电设备管理的问题及改善途径论文11-20

初中化学教学问题与改善对策论文11-08

调度算法等对NCS性能影响的仿真与分析03-07

迭代注水算法求解高斯矢量信道和容量研究03-07