三台平行机排序的一个复合半在线问题的算法

本文讨论一个三台平行机半在线排序问题.对预先知道工件的总加工时间和最大的工件的加工时间的复合半在线模型,我们证明了不存在半在线算法,其竞争比为4/3,并给出了一个竞争比为7/5的半在线算法,两者的差距小于0.067.     

面向成套订单问题的工艺规划与排序的集成研究

本文从工艺规划与排序的集成优化角度研究了成套订单问题^[1],克服了单独研究工艺规划和排序局部优化的局限性.文章中考虑了同一工件内部各道工序之间存在的优先加工限制,以及工件在不同机器上加工需要转移时间和工序间接连加工需要机器调整时间的情况,建立了成套订单问题的集成排序模型,并提出了针对求解大规模问题的基于遗传算法的启发式算法,最后通过一个算例对所研究的集成排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性.     

加工能力受限的单机干扰管理研究

针对单机环境下最小化加权折扣加工时间和的排序问题,研究如何应对可预见的干扰事件。由于干扰事件使得机器加工能力受限,初始最优加工时间表不再可行,采用外包的方式来进行干扰管理。构建了排序模型,同时考虑原目标和与初始计划偏离的扰动目标,选择外包工件集并对所有工件进行重排序。为了求解得到的双目标排序问题,基于理想点法设计了一种动态规划算法和量子遗传算法相结合的算法。最后通过一个数值算例说明,该排序模型对于求解加工能力受限的单机干扰管理问题是有效的。     

安装时间与次序相关的生产调度干扰管理研究

在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。     

等待时间受限的流水车间调度问题的启发式算法

针对等待时间受限的流水车间调度问题,分析了等待时间上限与可行解的解析关系以及目标函数的特殊性质,以此为基础,提出了一种启发式算法.算法采用贪婪与插入相结合的启发式规则构造工件加工序列,通过递归回溯解消其等待时间受限约束.仿真实验表明,该启发式工件排序规则在等待时间约束较紧或问题规模较大时,较其他几种常用排序规则具有更好的效果.     

预知两种信息带准备时间的平行机半在线排序

本文研究了P2,rj/sum & max/Cmax问题,即预知所有工件加工时间总和sum和最大工件加工时间max的两台处理器的带准备时间的半在线问题,并给出了竞争比为6/5的最优半在线算法.     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

基于微粒群算法的单机不同尺寸工件批调度问题求解

提出了一种改进的具有全局搜索能力的微粒群算法,对工件尺寸有差异的单机批调度问题的制造跨度进行优化。针对问题中工件尺寸不同且分批加工的特点,设计了微粒的编码方式;对进化过程中产生的极优解,采用了混沌优化策略进行改进,避免早熟收敛的问题。仿真实验结果表明,本文算法的时间性能和近似解质量均优于现有的其他方法。