带恶化工件的PFS调度的混合遗传算法北大核心CSSCI

研究了带恶化工件的置换流水车间调度问题,其中工件的加工时间是与开始时间有关的线性函数,考虑不同工件在不同机器上具有不同的恶化率,以最小化最大完工时间为目标,建立数学规划模型,进而提出了一种混合遗传算法来求解。该算法引入一种启发式规则以产生m-1条染色体改进初始种群的40%,结合遗传算法的初始种群产生方法共同生成种群,设计遗传参数自适应调节。仿真实验测试和对比了启发式法、遗传算法和混合遗传算法三种求解方法,实验结果表明所提出的混合遗传算法能更有效地求解这类NP-hard问题。     

带恶化工件的PFS调度的混合遗传算法

研究了带恶化工件的置换流水车间调度问题,其中工件的加工时间是与开始时间有关的线性函数,考虑不同工件在不同机器上具有不同的恶化率,以最小化最大完工时间为目标,建立数学规划模型,进而提出了一种混合遗传算法来求解。该算法引入一种启发式规则以产生m-1条染色体改进初始种群的40%,结合遗传算法的初始种群产生方法共同生成种群,设计遗传参数自适应调节。仿真实验测试和对比了启发式法、遗传算法和混合遗传算法三种求解方法,实验结果表明所提出的混合遗传算法能更有效地求解这类NP-hard问题。     

结合Setup和有限等待时间的两阶段混合流水调度优化

基于某洗发水生产企业的运作场景,研究了一种非同质并行机环境下的两阶段混合流水生产调度优化问题。问题综合考虑了各阶段的机器适用性、各机器上的序列相关准备时间(Sequence-dependent setup time,SDST)以及两阶段间的有限等待时间(Limited waiting time),以最小化最大完工时间(Makespan)。在问题建模的基础上,借助作业块划分规则构造了一种基于模型的启发式算法,并设计和实现了针对本问题的遗传算法。通过大量计算实验,将直接求解模型、基于模型的启发式算法和遗传算法这三种方法进行对比分析,验证了算法有效性,并利用遗传算法求解了大规模实际问题。     

无空闲占优机器的加工时间可变流水作业排序

研究了基于实际应用背景提炼出的工件加工时间是其开工时间的线性函数的无空闲流水作业排序问题。在机器分别具有某些优势关系的情形下,探讨了目标函数为极小化最大完工时间和极小化总完工时间之和的情况。对于每种情况,分别给出了工件按某种规则排序为最优序的多项式时间算法。     

加工时间存在双重约束的批调度模型及算法

为了提高热处理的加工效率并实现准时交货,本文根据热处理各批次加工时间受装炉量和批中最大工件尺寸双重约束的特点,分别以最小化最大完成时间和最小化最大拖期量为调度目标,构建混合整数线性规划模型Model C和Model L。根据分批数量上界设定值与Model C运算结果的关系特性,构建启发式算法HC提高Model C的运算效率。通过反例说明Model C所具有的特性并不适用于求解Model L。提出启发式算法HL求解最小化最大拖期量问题,并证明算法HL的计算复杂度。通过大量实验数据验证,结果显示两个数学模型都分别能够求得最优解,但调度规模不超过18个工件;算法HC能得到调度规模为60个工件的最优解;算法HL与最优解相比平均偏差不超过15%,调度性能明显优于其他2种典型算法。     

考虑公共交货期窗口问询的退化工件排序问题

工件的实际加工时间是其开始加工时间的线性递增函数,且不同的工件有不同的退化率。所有工件需要在相同的时间间隔内完工。以此模型为基础,研究了同时确定最优的交货期窗口和最优的工件加工顺序以最小化提前工件个数、延误工件个数以及交货期窗口问询产生的总成本的单机排序问题。分析了最优决策具有的特征,并基于上述性质提出了求解问题的多项式时间最优算法。利用随机产生的算例说明了最优算法的应用。     

一类具有三重指标的分批排序问题

本文研究现代排序问题一具有三重指标的批容量无限制平行分批排序问题。第一指标为最大延迟,第二指标为最大完工时间,第三指标为关于工件完工时间的任意正规函数。本文通过分析前两个指标最优解的性质给出了此问题的多项式时间算法。     

考虑交货期和等待时间受限的HFS调度问题的混合算法

针对工件具有交货期要求以及等待时间受限的混合流水车间调度问题,提出了一种回溯、启发式修复与邻域搜索相结合的混合算法.工件按启发式规则形成加工序列,以排列排序方式经过各加工阶段,采用递归回溯消除工件在相邻阶段的等待时间受限冲突,形成所有机器上的操作加工序列;通过对最后阶段机器上的操作加工序列进行移动修复以最小化其提前/拖期成本;对工件排序进行邻域搜索以改进目标函数值.数据实验表明该混合算法具有可行性和有效性.     

一种单机加权成套订单数问题的遗传算法

在基本的单机加权成套订单数问题[1]研究的基础上,增加考虑加工工件具有多种类型,且同类工件可分开加工,不同类工件之间接连加工需要机器调整时间的情况.建立了该类问题的0-1整数规划模型,设计求解该类问题的遗传算法,并通过一个算例对这类排序问题和所提出的算法进行说明.算法在文中所列三种初始种群规模下的10次运算内都能得到算例的最优解0.77,每次运算大都在100代以内得到收敛,多次试验结果显示算法具有较强的寻优功能、收敛平稳且运算时间较短,表明了算法求解此类问题的有效性.     

单台机器排序问题关于加工时间的反问题

本文研究单台机器总完工时间排序问题关于加工时间的反问题,研究尽量"小"地调整工件的加工时间使给定工件的加工次序成为最优的排序。我们考虑尽量"小"地调整是分别使最大带权相对离差的绝对值为最小、使总的带权相对离差的绝对值为最小或者使总的带权相对离差的平方为最小等三种情况。通过把问题转化成数学规划,我们分别指出这三种情况下的三个反问题都可以在多项式时间内求解。     

缓冲区容量约束下发动机混流装配线排序研究

为解决缓冲区容量约束下发动机混流装配排序问题,以关键部件消耗均匀化和最大完工时间最小化为目标,建立了优化数学模型,设计了一种多目标遗传算法,采用了混合交叉算子和启发式变异方法,并设计了基于帕累托分级和共享函数的适应度函数,将多目标遗传算法和多目标模拟退火算法的优化结果进行了比较。研究结果表明,多目标遗传算法在满意度和计算效率方面均优于多目标模拟退火算法,是一种有效的混流装配线排序问题求解算法。     

基于改进遗传算法的导向辊生产调度方法研究

目的 研究导向辊生产车间中的调度优化问题,有利于缩短工件的完工时间,提高产线生产效率。方法 以某导向辊生产车间为研究对象,以最小化最大完工时间为目标建立数学模型。针对该导向辊生产车间的实际工况,提出一种改进的遗传算法进行求解。通过对10种不同尺寸的导向辊进行生产调度,分别采用改进的遗传算法和传统遗传算法进行试验分析。结果 改进的遗传算法相比传统遗传算法寻优能力更高,工件的完工时间从139 min缩短为113 min,缩短了18.7%左右,生成了完工时间为113 min的生产调度甘特图。结论 与传统遗传算法相比,改进的遗传算法在导向辊生产调度优化中具有更高的全局优化能力和寻优精度。     

关于M类机器的非流水复杂作业排序问题的一种启发式算法

本文分析了Ｎ种零件（各项任务的工艺流程不同）需经Ｍ类机器加工的复杂非流水型作业系统，以误工工件数最少为目标函数，建立了问题求解的数学模型；在此基础上兼顾同类机器各台负荷必尽可能均匀的原则，构造了具有一定优度的启发式算法；接着，开发了计算机辅助编制生产作业计划的子系统；最后，通过实例分析，说明了这一启发式算法的有效性。     

改进离散候鸟优化算法求解带缺失阶段的柔性流水车间问题

针对每阶段包含不相关并行机的柔性流水车间调度，研究了具有缺失阶段的总加权完工时间问题。由于该问题是NP-hard的，因此，提出基于两段式编码和组合邻域策略的改进离散候鸟优化算法进行求解。基于机器和工件编号设计两段式编码，利用最短加工时间规则和随机策略获得初始候鸟种群。领飞鸟和跟飞鸟进化中引入组合邻域策略以产生邻域解，最后对最差个体设计重置机制以再次提高解的质量。针对不同规模问题，对所提算法和四种启发式算法进行仿真实验，实验结果表明改进离散候鸟优化算法得到了更高质量的满意解。     

带恶化工件和缓冲区的置换流水车间调度优化

本文研究了带恶化工件和缓冲区的置换流水车间调度问题,其中工件的加工时间是与开始时间有关的线性函数。假设每个工件在不同机器上有不同的恶化率,相邻机器之间的缓冲区容量有限,目标是最小化最大完成时间。针对该NP-hard问题,提出一种嵌入CDS算法和化学反应优化的混合遗传算法进行求解。首先,结合CDS算法和随机规则产生初始工件加工序列群,以改善初始工件加工序列群质量和提高工件加工序列群多样性;然后,基于工件加工位执行双亲双子单点交叉操作,应用基于反转逆序和交换的两种单点变异操作更新解;为进一步改进遗传算法解,引入化学反应优化的合成反应产生邻域解。仿真实验测试了不同规模的实例,通过与已有算法求解实例的结果进行比较,说明了所提出算法的有效性。     

基于三方博弈的改进遗传算法求解多目标柔性作业车间调度

针对柔性作业车间的特点,以最小化完工时间、总机器负荷最小和临界机器负荷最小为目标,提出了基于三方博弈的改进遗传算法求解多目标柔性作业车间调度模型。通过三方博弈,使三个优化目标之间的博弈策略实现最优组合,从而获得子博弈完美纳什均衡,即为问题的优化组合解。为优化种群质量,将改进遗传算法应用于多目标柔性作业车间调度问题的求解过程,采用帕累托分类思想,对种群进行选择和精英保留,以优化种群结构;通过设计交叉、变异和局部搜索机制进一步寻找目标函数的最优解。为证明算法的有效性,运用基准算例对算法的求解性能进行了验证。其结果表明,所提算法在求解结果上有明显的改善,求解效率更高。     

零等待混合流水车间问题优化研究

研究了带零等待的混合流水车间调度问题,考虑工件动态到达的实际生产特征,以最小化总加权完成时间为目标,建立整数规划模型,然后设计一种基于代理次梯度法的改进拉格朗日松弛算法.基于工件分解策略将拉格朗日松弛问题分解为多个工件级子问题,不同于每次迭代要求最优求解所有子问题的次梯度法,所设计的代理次梯度法通过每次迭代最优求解几个子问题得到松弛问题的近似解,进而获得搜索拉格朗日乘子的代理次梯度方向,最后设计启发式构造可行时间表.通过仿真实验,证明了所设计的算法在解的质量和收敛性方面均优于传统的使用次梯度法的拉格朗日松弛算法.     

反相容工件系统的加权完工时间和的重新排序问题(英文)

重新排序问题是指在原始工件已经安排好的情形下,新到的工件集与原始工件集一起重新再排序,这是实际工作中常见一类优化问题。本文考虑了单机上当工件加工时间与权重反相容时,在最大错位量约束下的加权完工时间和最小化的重新排序问题。对于提出的四个问题,即在最大序列错位、最大时间错位、总序列错位和总时间错位约束下的加权完工时间和重新排序,基于问题的结构性质,运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法。     

有分离调整和移走时间的两机器流水作业总完工时间问题

对有分离调整和移走时间的两机器流水作业问题,同一工件的调整和移走在不同机器上是可以重叠的,但加工时间不能重叠。本文以总完工时间为准则研究调整时间和移走时间均独立于加工时间的两机器流水作业问题,给出了问题最优解中工件排列应满足的条件;同时也讨论了该类问题多项式可解的情形。     

基于最早完工时间疫苗的免疫遗传算法求解FJSLP

在生产过程中,车间作业调度的主要任务是确定工件在各台设备上的加工顺序,合理的调度方案能提高设备的利用率和企业的效益。针对柔性车间分批调度问题,采用免疫遗传算法进行求解。在疫苗技术方面,依据工件工序的加工信息,选择工件工序所能最早完工的机器作为疫苗,对相应工件个体机器码进行接种。通过对案例的测试,结果表明所采取的方法能求得更好的调度方案,减少作业总流程时间。