用改进的蛙跳算法求解一类模糊Flow Shop调度问题

对加工时间不确定的Flow Shop调度问题进行研究,提出了一种改进的蛙跳算法(NewShuffled Frog Leaping Algorithm,NSFLA)。蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)的局部搜索采用类似粒子群算法的搜索机制,全局搜索采用洗牌策略即种群间定期进行信息交换。为了解决SFLA的局部搜索易出现不合法调度的问题,在交换子和交换序概念的基础上,提出了交换序构造的初始位置随机机制和交换子的随机插入机制这两种追踪策略。仿真实验结果验证了NSFLA解决模糊Flow Shop问题的有效性。     

车间流程的免疫调度算法

为了高效地解决车间流程(Flow Shop)问题,提出了一种利用免疫算法求解Flow Shop调度问题的方法.该算法是根据人或者其他高等动物的免疫系统机理设计的,将调度目标和约束条件作为抗原,将问题的解作为抗体,对抗体采用按工件加工顺序进行自然数编码,并把最大流程时间的倒数作为适应度函数,新抗体的繁殖是通过部分匹配交叉算子和按工件顺序互换的变异算子实现的,对抗体产生的刺激和抑制通过抗体浓度来调节,而抗体浓度通过计算抗体之间的最大亲和力获得.通过对Flow Shop问题的基准测试表明,该算法不仅在求解问题的规模上具有很好的可伸缩性,而且在运算时间上也低于遗传算法和模拟退火算法.     

加工时间线性恶化的成组加工流水作业问题

文章讨论了m台机器的Flow Shop成组加工问题.工件在不同机器上的加工时间以相同的系数(斜率)线性恶化.目标函数分别为极小化时间表长和总完工时间.对于目标函数为极小化时间表长的Flow Shop成组加工问题.再进一步细分为组间无调整时间和组间有相同调整时间的两种情形来讨论,都得到了最优调度(排序).对于目标函数为总完工时间的Flow Shop成组加工问题,只要组内按qij单调递增(SPT)序加工,组间按S.单调递增序加工可得最优调度.     

用改进的协同免疫算法求解Flow Shop调度问题

利用改进的协同免疫算法(improved co-evolutionary immune algorithm,ICIA)求解FlowShop调度问题.算法中的疫苗取自迭代N次的局部最优解,并随着每代最优值的变化不断更新.为了克服协同免疫算法初期收敛速度慢的问题,加入了局部搜索算法;针对算法后期求解目标函数值差的问题,提出了一种新的种群选择机制"80/20法则".通过与遗传算法(genetic algorithm,GA)和未改进的协同免疫算法(co-evolutionary immune algorithm,CIA)比较,仿真实验结果验证了ICIA解决Flow Shop问题的有效性.     

改进协同粒子群优化算法及其在Flow Shop调度中的应用

针对协同粒子群优化算法存在的停滞现象,提出了一种改进的协同粒子群优化算法。采用优化法的子群协作方式,既保证了收敛速率,又可以防止陷入局部最优。同时引入综合学习策略,增加种群的多样性,防止种群出现停滞现象。在此基础上,又加入了扰动机制,进一步避免算法陷入局部最优。采用该算法对3个经典函数进行测试,并将其应用于Flow Shop调度问题,仿真实验结果表明:新算法有效克服了停滞现象,增强了全局搜索能力,比基本协同粒子群优化算法的优化性能更好。     

基于改进分布估计算法的带并行机模糊混合Flow Shop调度

针对处理时间不确定情况下带并行机的混合Flow Shop调度问题,基于模糊规划理论,采用一种模糊数排序的方法建立了调度模型;以最小化加权模糊最大完工时间的平均值和不确定度作为调度目标,提出一种改进分布估计算法(IEDA)求解上述问题。IEDA算法采用基于NEH(Nawaz-Enscore-Ham)和破坏重建策略的初始化方法,对较优个体进行变邻域局部搜索以提高算法的局部搜索能力,同时采用破坏重建策略增加种群多样性,在最优解连续若干代没有改进时对其进行基于破坏重建策略的变邻域局部搜索,增强算法跳出局部最优的能力,并用正交设计的方法调节算法参数。仿真实验结果验证了本文算法的优越性。     

求解中间存储有限Flow Shop调度问题的离散群搜索优化算法

针对中间存储有限的Flow Shop调度问题,提出了一种离散群搜索优化算法来最小化工件加工的总流水时间。该算法首先采用基于工件排列的离散编码方式,使得能够直接求解离散的调度问题;其次提出了新的初始化方法,确保了初始种群既具有一定的多样性,又有较好的性能;还引入了离散差分进化的思想,增强了算法的运算效率与搜索能力。最后使用正交设计的方法设置算法参数,通过对Taillard算例的仿真计算,验证了本文算法的优越性。     

量子寄生遗传算法求解Flow Shop及两阶段配送的集成调度问题

针对Flow Shop及两阶段配送的集成调度问题,考虑各种约束条件,以交货时间最短为目标构建混合整数规划模型。该模型中,第1阶段配送是工件原材料从仓库由吊车搬运到生产车间的加工机器上,第2阶段配送是工件完工后由一辆卡车运送至顾客。根据该集成调度问题特点,提出了基于量子理论和寄生理论的量子寄生遗传算法(Quantum Bio-parasitic Genetic Algorithm,QBGA)。该算法设计了能够同时带有工件的运输批次和生产排序信息的编码,该编码保证了每个个体都是充分协调生产能力和运输能力的可行解,同时构建了两个种群——宿主群和寄生群,执行寄生机制与反寄生机制从而增加基因多样性和加快算法收敛速度,最后通过仿真实验验证了QBGA算法的有效性。     

基于新型蛙跳算法的带阻塞流水线调度问题

针对目标函数为最小化Makespan的带阻塞流水线问题,提出了一种新型的蛙跳算法(New Modified Shuffled Frog Leaping Algorithm,NMSFLA)并对其求解。在蛙跳算法的局部搜索步骤中引入带约束的交叉变异思想,针对调度问题对青蛙的跳跃规则做出了改进,有效地解决了传统蛙跳算法局部搜索易出现不合法解从而导致算法效率不高的问题。仿真实验结果验证了NMSFLA解决带阻塞的Flow Shop问题的有效性。     

一类调整时间可分离的Flow Shop 排序问题F3│S│Cmax的最优算法

讨论调整时间可分离的Flow Shop排序问题F3│S│Cmax，对其一类特殊情况给出了最优算法。     

柔性流水作业排序问题的贪心算法求解

柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题,给出了求解柔性流水作业排序问题近似解的贪心算法,并对其性能进行了分析测试。结果表明,虽然该贪心算法求出的近似解与最优解相比有一定误差,但由于其时间复杂度较小,因此对求解车间作业调度问题仍有一定的现实意义。     

不确定条件下的零等待Flow shop生产调度问题

研究了处理时间不确定条件下,含零等待模块的模糊Flowshop生产调度问题;采用三角模糊数描述处理时间的不确定性,用零等待策略对加工过程进行约束,建立了基于模糊规划理论的零等待Flowshop调度模型,通过中间值最大隶属度的方法,将原有的模糊调度模型转化为清晰的调度模型;最后应用改进的模拟退火算法对模型进行仿真优化,制定了适用于实际排产过程中的GANTT图,仿真结果说明了调度模型的正确性和改进算法的有效性。     

最佳觅食算法求解多目标混合流水车间调度问题

针对生产车间中需要同时考虑减少生产时间、确保加工质量以及通过减少能耗而降低生产费用的需求,建立以完工时间、空闲时间、加工质量和机器能耗为目标的多目标混合流水车间调度模型,提出一种基于直觉模糊集相似度的最佳觅食算法.为有效求解此问题,提出基于Largest Order Value规则的双层整数编码方式,在机器层编码部分采用权重法来计算机器的选择概率.针对多目标优化,提出直觉模糊集相似度的解比较策略,采用直觉模糊集相似度的大小衡量Pareto解与理想解的相似程度,判断Pareto解的优劣.通过测试实例和实际案例,验证本算法求解多目标混合流水车间调度问题的有效性和可行性.     

不确定性条件下存储时间有限型Flow Shop问题的提前/拖期调度研究

研究了具有不同交货期窗口的Flowshop提前／拖期调度问题,并考虑处理时间的不确定性以及存储时间的有限性,在模糊规划理论基础上,建立了带有提前／拖期的存储时间有限型Flowshop的调度模型,通过中间值最大隶属度算法,将原有的模糊调度模型转化为清晰的调度模型,并应用了遗传算法进行优化求解。仿真实验验证了算法的有效性。     

A Novel Particle Swarm Optimization for Flow Shop Scheduling with Fuzzy Processing Time

Since in most practical cases the processing time of scheduling is not deterministic, flow shop scheduling model with fuzzy processing time is established. It is assumed that the processing times of jobs on the machines are described by triangular fuzzy sets. In order to find a sequence that minimizes the mean makespan and the spread of the makespan, Lee and Li fuzzy ranking method is adopted and modified to solve the problem. Particle swarm optimization （PSO） is a population-based stochastic approximation algorithm that has been applied to a wide range of problems, but there is little reported in respect of application to scheduling problems because of its unsuitability for them. In the paper, PSO is redefined and modified by introducing genetic operations such as crossover and mutation to update the particles, which is called GPSO and successfully employed to solve the formulated problem. A series of benchmarks with fuzzy processing time are used to verify GPSO. Extensive experiments show the feasibility and effectiveness of the proposed method.     

调整时间可分离的无等待FlowShop调度问题

研究了3台机器调整时间可分离的无等待FlowShop调度问题,目标函数为极小化加权完工时间和·基于对问题的分析,给出了目标函数的一般表示·对某些特殊情况,给出了问题存在多项式最优算法的充分条件·在此条件下,将单机调度问题的WSPT规则应用到无等待FlowShop调度问题,得到了求解无等待FlowShop问题最优调度的分派规则·通过反例指出了文献中的某些错误·     

面向分段涂装作业的混合流水车间调度

基于船舶分段涂装作业,提炼出具有重入和等待时间约束的两阶段混合流水车间调度问题.其中第一阶段含多台批处理机,第二阶段含多台离散机且存在一次重入过程,两阶段间有等待时间约束.以最小化最大完工时间为优化目标建立数学模型,提出一种结合Metropolis抽样准则和变邻域搜索的混合量子粒子群优化算法,并利用多种启发式规则进行解码.实例验证和数值分析表明,所提算法是解决分段涂装调度问题的一种有效方法.     

基于演化多目标算法的混合流水作业调度优化

针对供应链网络优化领域中的混合流水作业调度问题提出了一种新的多目标演化优化算法。给出了这类问题的通用优化模型，在此基础上，提出了基于流程的矩阵基因编码方案，动态适应度分配机制，并引入小生境保优策略构造了算法过程，利用收敛进程参数分析了算法的收敛性能。性能分析和算例实验表明算法对于高维多目标优化问题是有效的，且能够以较快的速度收敛。     

改进遗传算法求解带不相关并行机的HFSP

以最小化最大完工时间为目标的不相关并行机混合流水车间调度问题.首先建立了不相关并行机混合流水车间调度问题的数学模型;然后提出了改进的遗传算法进行求解.为弥补遗传算法的迭代后期容易陷入局部搜索的缺陷,在传统遗传算法的基础上利用改进的自适应交叉和变异概率因子及模拟退火局部搜索策略,增强遗传算法在迭代后期跳出局部最优的能力....     

面向作业车间调度问题的遗传算法改进

为了获得遗传算法在作业车间调度问题上的最优化解,提高算法的迭代速度,研究了遗传算法的改进方法,以工件的加工时间最短为目标建立调度模型。在算法上提出了基于概率改进的具有自适应能力的交叉与变异算子,以求作业车间调度问题的最优解。在遗传算法上采用精英保留策略方法,并结合改进的自适应算子对问题进行求解。以基准案例LA01和FT06作为实验仿真对象,获得了相应的甘特图以及搜索过程曲线。仿真结果表明,与未改进的算法相比,该算法能够更加快速地获得最优解。改进后的算法在搜索上更加快速有效,在求解作业车间调度问题上具有一定的可行性,更加适合工业加工生产。