基于混合流水作业组织的港口拖轮调度优化

在对拖轮调度问题进行分析的基础之上,将拖轮调度问题归结为一类具有多阶段共用机器特征的混合流水车间调度问题.建立了针对多停泊基地不同作业模式下、且考虑靠泊与停泊两阶段的拖轮调度优化模型,推导了基于混合流水作业组织的港口拖轮调度优化问题的理论下界值,并设计了启发式规则与模拟退火相结合的混合算法(HSA)求解该模型.通过运用该算法求解仿真算例,并将其结果与模型理论下界值、三种基于现行调度规则及基于Johnson规则的调度方案进行比较.结果表明,运用HSA求解的结果与理论下界值的平均偏差值为5.39%,且该结果远小于基于现行调度规则及Johnson规则的求解值,验证了模型与算法的高效性,可以为拖轮作业模式的选择以及调度方案的制订提供决策支持.     

基于折衷策略的Blocking流水车间调度构造启发式算法

针对目标函数为Makespan的Blocking流水车间调度问题,经过对目标函数结构的分析,提出了一种基于折衷策略对工件进行初始排序的启发式算法.通过对大量典型算例的计算,实验结果证明了设计的算法在解的质量上超越了NEH算法.     

基于蚁群优化的置换流水车间调度算法

针对置换流水车间调度问题,提出了一种基于蚁群优化的调度算法.该算法的要点是将NEH启发式算法和蚁群优化结合起来:首先,将蚁群优化中的能见度定义为NEH中所用的工作加工时间之和.其次,对于部分解采用了NEH中的步骤2和步骤3进行局部调整.最后,对构造出的解做插入型局部搜索.用所提算法对置换流水车间调度问题的基准问题进行了测试,测试结果表明提出算法的有效性.     

基于混合电磁算法求解置换流水车间调度问题

为了求解置换流水车间调度问题,提出了一种基于混合电磁算法的调度算法。首先,采用最小位置值法将算法中连续向量转换为工件排列顺序。其次,对随机生成的一部分初始解用基于启发式信息的贪婪随机自适应算法得到的结果加以改造,使其质量得到提高。最后,加入局部搜索增强算法性能。通过对Car系列和Rec系列基准测试结果表明,提出的算法性能优良。另外,还讨论了一些参数对算法优化性能的影响。     

多工件族无缓冲混合Flow Shop问题的模型和算法构建

旨在研究并解决一类从集装箱混合装卸作业环境中提取的多工件族无缓冲混合Flow Shop问题. 针对该问题的多工件族、无缓冲、部分专用机、与机器和顺序相关的准备时间和作业时间等特点, 构建了问题的混合整数线性规划模型. 鉴于问题的NP-hard特性, 构造型的启发式算法被构建, 核心思想是基于提出的机器库存和配额等概念, 动态构建含有三元副的调度列表, 三元副表示与其一一对应的工件在3阶混合Flow Shop中的加工轨迹. 通过仿真实验、下界分析, 发现算法能获得好的近优解和低的计算成本. 更为重要的是, 算法尤其适合解决大规模的实际问题.     

集装箱码头集成调度模型与混合优化算法

为提高集装箱码头作业中各种设备的协调性,提高整体作业效率,建立了集成调度模型,模型集成了装卸桥、集卡与龙门吊的调度问题.同时,设计了求解模型的混合优化算法,此算法集成了神经网络良好的近似估计功能与模拟退火算法有效的搜索能力.算法流程是:初始化集装箱装卸序列;基于一定的分配规则为集装箱分配作业设备;采用模拟退火算法搜索解空间,更新装卸序列.在算法过程中,用神经网络预测目标函数,并且过滤明显的劣质解.最后,通过算例分析验证了模型与算法的有效性.结果表明,混合优化算法可以提高模型求解效率,对于规模为400个集装箱的调度问题,平均偏差为7.52%,计算时间为8.9s,模型与算法可行.     

求解混合流水车间调度的改进贪婪遗传算法

针对最小化最大完工时间的带有不相关并行机的混合流水车间调度问题,提出了改进贪婪遗传算法。首先,该算法染色体编码采用基于工件加工顺序的编码,解码提出了两种设备分配方案,并考虑到不同阶段加工设备配置不同对算法的影响,采用了正序解码和逆序解码加再调度并用的解码策略。其次,提出贪婪交叉算子和贪婪变异算子,这些算子不仅承担改进种群,增加种群多样性的功能,同时还具有较强的局部搜索能力。最后通过正交实验确定算法的参数设置,与已有算法对已知案例的求解结果进行了比较,说明了该算法的有效性。同时实验表明了正序和逆序解码策略的必要性以及正序或逆序解码的时机。     

一种求解两机成组作业流水车间优化调度问题的遗传算法

当优化目标是总的流时间时,两机成组作业流水车间调度问题是NP难解的.本文提出了一种两机成组作业流水车间优化调度的遗传算法.该遗传算法分两层一层优化组内作业排序,一层优化组排序.仿真结果表明该方法的有效性.     

一类多资源作业车间混合优化调度方法

针对多资源作业车间调度问题,结合启发式算法和遗传算法的特点,提出了混合优化调度方法,建立了多资源约束的车间优化调度模型.根据启发式算法中调度优先规则对调度目标的影响程度,设计了新的编码规则.采用正弦函数作为改进遗传算法中的自适应因子,使交叉概率和变异概率随群体的适应度自动改变,提高了运算的效率.通过实例仿真并与其他算法比较结果表明,该混合调度算法可以进行作业车间在机床、刀具等多种生产资源约束下的优化调度,并在评价指标上较其他算法更优.     

工艺路线可变车间作业调度的两级遗传算法

车间作业调度问题是一个著名的NP难题，而工艺路一可变的车间作业调度是一个更一航意义的问题，算法研究是车间作业调度问题的一个重要研究方向，最近几年，遗传算法开始在调度问题中得到广泛应用，分析了工艺路线可变的车间作业调度问题的特点，并建立了相应的优化模型，提出了一种两级遗传算法，重新设计了算法的遗传编码方案以及选择、交叉和交异算子，通过实例仿真，表明了用两级遗传算法求解工艺路线可变的车间作业调试问题是有效和可行的。     

两阶段流水车间成组调度问题的迭代贪婪算法

针对两阶段流水车间成组调度问题，在同时考虑序列不相关准备时间和阶段间双向运输时间约束的情况下，以最小化最大完工时间为目标建立了混合整数线性规划模型，结合问题特征提出一种协同进化迭代贪婪算法.算法将工件组间排序和各工件组内工件间排序两个子问题进行统一编码，设计了不同的启发式规则产生问题的初始解，并提出一种协同导向迭代贪婪规则对两个子问题进行联合优化，进而给出了问题的三个下界以评估算法的性能.通过不同规模的数据实验和与对比算法的比较分析，验证了所提算法的高效性和稳健性.     

不确定条件下的flow shop问题的免疫调度算法

生产调度是企业生产过程中一个重要部分，而且实际的生产过程中会存在各种各样的不确定性，针对不确定条件下的flow shop（流水车间作业）调度问题，采用模糊数学的方法来处理数据的不确定性，在基于模糊规划理论的基础上建立了相应的调度模型，并结合免疫算法的特点，提出了解决此类问题的模糊免疫调度算法．通过仿真试验，证明了模型和算法的可行性和有效性．     

基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题

针对以最小化最大完工时间为目标的无等待柔性流水车间调度问题,提出了一种混合粒子群-NEH算法.该算法 利用粒子群优化算法解决机器分配问题,并进行全局优化;利用改进的NEH算法确定工件加工顺序,并首次提出差值 平移算法计算问题目标值.在算法求解过程中,通过不断对停滞粒子实行变异操作,避免粒子群陷入早熟收敛状态.基 于典型算例的仿真实验,证明了所提算法求解该类问题的可行性和有效性.     

Job shop scheduling problem based on DNA computing

1 .INTRODUCTIONDNA is a high-molecular weight compound. Itsbasic composition includes one phosphate group,one deoxyribose sugar ,and one nitrogenous base .There are four kinds of nitrogenous bases :adenine(A) , guanine ( G) , cytosine ( C) , and thymine(T) . DNAis a double helix consisting of two sin-gle strand deoxynucleotide chains runningin an an-tiparallel configuration (Fig. 1) . After determi-ning the precise structure of DNA, many experi-mental methods have been invented inclu…     

基于大规模FSP问题Block性质的SA算法

对于大规模流水线调度问题(FSP),模拟退火算法(SA)中邻域候选解的被接受概率,因邻域增大和邻域中的劣解数的增多而大大降低,SA算法的性能因而大为降低。针对这一问题,提出一种基于FSP问题Block性质的SA算法。将邻域划分成若干个子邻域,用子邻域中的最好解作为候选解,以提高候选解被接受的概率。引入FSP问题的Block性质,减小邻域尺寸,将搜索集中在邻域中“最有希望”的区域,进一步增强算法性能。数值仿真实验表明,该算法能在较短时间内获得大规模FSP问题的近优解。     

设备具有恶化特性的多目标流水车间调度模型与算法

考虑到现实流水车间调度中设备具有恶化特性,针对作业处理时间是其开始时间的线性递增函数的流水车间调度问题,建立了最小化最大完成时间和总延迟时间的多目标优化模型;进而设计了一种基于分解的自适应多种群多目标遗传算法进行求解.该算法将多目标优化问题分解为多个单目标子问题,并分阶段地将这些子问题引入求解过程.在每次迭代时,根据种群在目标空间和解空间的分布情况,自适应地为当前求解的子问题分别构造子种群进行求解.通过对数值算例仿真实验,验证和分析了所提出的算法在解决该问题上能够获得较好质量和分布性的非支配解集.     

多目标置换流水车间调度的混沌杂草优化算法

针对最小化最大完工时间,总流程时间及总延迟时间的多目标置换流水车间调度问题,提出一种改进的混沌杂草优化算法,该算法采用基于熵值权重的灰熵关联度适应值分配策略,引入快速非支配排序法生成外部档案,并将进化种群的更新和最优位置的混沌搜索相结合,用于维护外部档案,提升算法的寻优性能.通过与NSGA-Ⅱ算法进行OR-Library典型测试算例的对比实验,验证该算法的有效性.     

基于混合遗传退火算法的并行测试任务调度优化

并行测试任务的优化调度是并行测试技术的核心问题之一。可以充分利用混合遗传退火算法优异的全局最优搜索能力来寻找具有最大并行率的并行任务序列。首先,建立了并行测试任务调度问题的数学模型;给出了并行率的定义,设计了一种满足资源约束与任务时序约束的基因编码方法及相应的遗传退火操作方案。最后,对实例进行仿真实验,结果验证了该算法的有效性及优越性。