两机零等待流水车间调度问题的启发式算法

为实现两机零等待流水车间调度问题的总流程时间最小化,结合问题的结构信息提出了一种快速求解近优解的启发式算法。在该类问题中,工件在每台机器上的操作包括调整、加工和移除3部分,且调整和移除时间都与工件的加工时间相互分离。首先分析了该类问题的优化性质,结合优化性质进而构造出求解算法。在中小规模和大规模问题上,将启发式算法的结果分别与最优解和最优解的下界值进行了比较。大量数值计算实验表明了该算法的有效性和解决大规模实际问题的潜力。     

可重入混合流水车间调度的改进遗传算法

研究了可重入多阶段混合流水车间调度问题,其中至少有一个加工阶段有多台同构并行机。考虑工件在相邻两阶段间的运输时间和工件动态到达等实际生产特征,以最小化最大完工时间为目标建立数学模型。在传统遗传算法的基础上,结合NEH启发式算法产生工件初始加工顺序,令遗传参数随进化代数和个体适应函数值2个方面进行自适应调节,以避免算法陷入早熟,提出改进遗传算法用以求解该NP-hard问题。分别利用所提出的改进遗传算法与传统遗传算法、NEH启发式算法对不同规模的问题进行仿真测试,结果表明,改进遗传算法在较短的计算时间内能够获得较好的近优解。     

不确定条件下具有零等待的流水车间免疫调度算法

为了解决不确定条件下具有零等待的流水车间生产调度问题 ,采用三角模糊数来描述不确定的产品处理时间 ,在模糊规划理论的基础上建立了相应的调度模型。通过中间值最大隶属度算法 ,将原来的模糊调度模型转化为单目标的规划模型 ,并借鉴自然界中生物免疫系统的概念和机理 ,提出了解决此类问题的免疫调度算法。在该调度算法中 ,采用字符编码的方式来表示产品的处理顺序 ,每个抗体表示一组可行的具体调度方案 ,用亲和度来衡量抗体与抗原之间以及抗体与抗体之间的匹配程度 ,同时根据抗体的浓度自适应地调节搜索方向。通过仿真试验 ,表明了所建模型和调度算法的有效性     

一类解决无等待流水车间调度问题的蚁群算法

针对以最大完成时间为目标的无等待流水车间调度问题,提出了一种蚁群算法.首先,基于复杂度为O(n)的最大完成时间算法简化了适应值的计算;其次,基于当前最优解和轨迹密度的新解构造方法提高了求解质量;第三,基于快速插入邻域算法的多重插入移动提高了搜索效率;最后,基于典型算例的仿真试验,表明了所得调度算法的可行性和优越性.     

求解混合流水车间调度问题的改进灰狼算法

针对带有相同并行机的混合流水车间调度问题,以最小化最大完工时间为研究目标,提出一种改进灰狼优化算法.根据问题特征建立了数学模型;对灰狼算法中的重要控制参数C提出一种新的计算公式,保证了算法的初期全局勘探能力和后期局部搜索能力.随着狼群向决策狼聚集,为了保持狼群的多样性,提出一种基于平面镜成像学习策略,以避免算法陷入局部最优.鉴于混合流水车间每个阶段加工设备的配置不均衡,采用正序和逆序解码策略,从而提高找到问题最优解的概率.将所提算法和其他算法应用于某企业实际案例与benchmark案例进行对比,验证了算法的有效性和可靠性.     

利用猫群算法求解流水车间调度问题

流水车间调度问题是一类传统的生产调度问题,其已被证明是NP-hard问题,而群体智能算法在求解此类问题中表现出优秀的性能。猫群算法是一种较新颖的群体智能算法,将猫群的行为模式分为搜寻模式和跟踪模式,通过一定比例的猫群数量执行两种不同的模式来达到优化的目的。通过将猫群算法与标准粒子群算法和蝙蝠算法在求解流水车间调度问题的结果进行比较,表明了猫群算法在调度问题中的良好优化性能以及应用前景。     

蚁群算法求解混合流水车间分批调度问题

为解决混合流水车间分批调度问题,提出一种三级递阶结构的蚁群算法.算法中,第一级蚁群算法设计了一种批量大小动态结合的柔性分批策略,完成产品的批次划分;第二级蚁群算法考虑工件在各设备的加工时间和设备可用能力,设计蚂蚁设备间的转移概率,完成工序约束下各批次的设备选择;第三级蚁群算法考虑同一设备上批次顺序相关的换批时间,设计蚂蚁批次间的转移概率,完成各设备的批次排序.通过实例仿真,分别对分批算法和混合流水车间调度算法性能进行比较分析和评价,结果表明了算法的有效性和优越性.最后从生产实际出发给出算例,验证了算法的有效性和对生产实践的指导作用.     

基于改进遗传算法的车间调度问题求解

针对车间调度问题(Job Shop Problem,JSP)的特点,提出一种改进遗传算法。该方法利用剩余作业时间最多(MostWork Remaining,MWR)的工件优先排列的启发式规则来产生初始种群,并且在进化过程中采用分代交叉算子进行操作来避免算法早熟。通过分析算例结果表明,该改进遗传算法可以在进化初期就得到比较理想的调度方案,而且优化收敛速度快、结果优,更适用于解决车间调度问题。     

基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法

分布式制造(Distributed manufacturing,DM)已成为当前主流制造模式之一,广泛存在于航空、电子等行业实际生产中。在DM中,各个工厂存在诸如机器数量、机器工艺、原料运输条件的差别,即异构性。然而,目前的分布式调度研究中均未考虑工厂的异构性。因此,结合实际需求,研究一种考虑序列相关准备时间的多目标分布式异构零等待流水车间调度问题(Multi-objective distributed heterogeneous no-wait flowshop scheduling problem with sequence-dependent setup time,MDHNWFSP-SDST)。首先,建立了以最大完工时间和总滞后为目标的多目标优化模型。基于问题特征及多目标特性,提出了一种多目标离散人工蜂群算法(Multi-objective discrete artificial bee colony,MODABC)。其次,改进了PWQ算法(Improved PWQ,IPWQ)初始化种群,解决了PWQ存在的数量级和重复解等问题;在雇佣蜂阶段,结合分布式调度问题特点,设计了四种邻域...     

改进遗传算法求解作业车间调度问题

介绍了作业车间调度问题的概念,构造了该问题的数学模型和目标函数,提出了一种解决作业车间调度问题的以最小化最大完工时间为目标函数的改进遗传算法,并运用实例对算法进行了分析。     

解决无等待流水车间调度问题的离散粒子群优化算法

针对以生产周期为目标的无等待流水车间调度问题,提出了一种离散粒子群优化算法.研究了无等待流水车间调度问题的快速邻域搜索技术,并将其分别用于加强粒子、个体极值或全体极值的邻域探索能力,得到了三种改进的离散粒子群优化算法.基于典型算例的试验,表明了上述算法的有效性.     

求解流水车间调度问题的瓶颈指向启发式算法

针对最小化时间表长的流水车间调度问题,提出一种根据工件加工时间特征构建工件调度的瓶颈指向启发式算法。首先,为构建初始工件排序,充分利用各机器负荷一般不相等的特点,瓶颈阶段前加工时间较短而之后加工时间相对较长的工件优先开始加工;其次,当有工件等待加工时,根据工件在瓶颈机器前或后加工时间的特征调整工件加工顺序;最后,采用邻近工件成对交换和插入的方式改进初始调度。当瓶颈机器趋于中间阶段,或瓶颈机器上工件的加工时间趋于增加时,求解效果较好。数据实验表明算法是有效的。     

求解同顺序加工调度问题的一种启发式方法

为了更加有效地求解同顺序加工调度问题,分析了现有启发式求解方法,发现影响解的质量的主要因素是调整近似解的方法和初始解,其中调整近似解的方法对解的质量影响较大。对此,提出了一种新的启发式方法。新方法中的调整方法考虑了调整对最短总加工时间的影响,调整任意给定的近似解不会降低解的质量,经过迭代运算,可以逐步改善近似解;新方法采用了多起点策略,利用调整方法调整不同初始解,选取最好的近似解作为问题的解,从而减小了初始解对问题解的质量的影响。实验结果表明,这种方法是有效的。     

有效的混合粒子群算法求解阻塞流水车间调度问题

针对以最小化完工时间为目标的阻塞流水车间调度问题,提出了一种混合粒子群算法进行求解。该算法将粒子群算法与迭代贪婪算法进行了结合。利用改进的迭代贪婪算法产生问题初始优化解,利用粒子群算法进行全局优化。针对粒子群算法易早熟收敛的特点,提出一种判断粒子停滞和粒子群早熟的方法,并在发现种群早熟后利用迭代贪婪算法的构造操作和毁坏操作对相关粒子进行变异,同时按照一定比例对最差的部分粒子进行重新初始化,以增加种群多样性。通过标准实例测试,验证了所提算法的有效性。     

采用多个体交叉的遗传算法求解作业车间问题

为改善目前求解Job-Shop问题中的遗传算法的性能,加快搜索最优调度解的速度,首先分析了目前Job-Shop问题自身的求解难点和遗传算法的特点,并借鉴生物学的依据,提出了多个体交叉的遗传算法。该算法在遗传过程中采用多个体遗传算子,充分利用个体的优良性质,对不可行调度解根据多个体修补原则进行修正,可保证遗传后代的合法性和多样性,能够加快最优调度解的搜索时间。仿真结果充分证明了该算法的有效性。     

基于DBR—GA的混合流水车间调度方法

针对带有并行机与批处理机的混合流水车间调度问题,提出一种基于“鼓-缓冲器-绳子”一遗传算法的调度方法。首先建立了识别瓶颈工作站的步骤,开发了相应的启发式算法,进行了问题初始解的求解,在此基础上应用改进遗传算法对作业在瓶颈工作站上的加工顺序进行优化,并利用缓冲机制决定了作业的投放策略,同时对非瓶颈设备运用优先级规则进行了作业的排程。最后通过算例实验和性能分析,验证了所提调度方法的有效性与实用性。     

求解无等待流水车间问题的若干算法

提出了解决无等待流水车间问题的离散粒子群优化、离散差异进化、变邻域搜索和阈值接收算法.在离散粒子群优化和离散差异进化中,采用基于工件排列的编码,设计了新的个体生成公式.同时研究了基于串行结构、嵌人结构和协同结构的12种混合算法.仿真计算表明,混合算法具有较高的优化性能.