一种基于双线性链表结构编码的遗传算法

针对基于以往经典编码方式的遗传算法解决并行机大批量成组调度问题时的弊端,提出了一种基于双线性链表结构编码的遗传算法(DLGA),并设计了相应的遗传算子。应用于某轮胎厂的硫化工序调度问题,进行了多次仿真实验与分析,结果表明该算法在优化调度性能指标、提高应用可行性方面有显著成效。

并行多机成组工作总流水时间调度问题

有N个成组工件将在M台并行一致的机器上加工 ,当一个工件接在不同组的工件之后时需要装设 ,而接在同组工件之后时不需要重新装设 ,目标函数是使总的通过时间最短。这是一个NP难题 ,最优解很难找到。笔者在文中提出了一个启发式算法 ,为了验证该算法的结果 ,又提出了一个求解最优解下界的线性规划模型 ,并用分枝定界法求解出下界解。在中小规模问题条件下 ,将下界解、启发式的解及最优解进行比较 ,证明了下界解的有效性。然后 ,在中等规模水平上 ,将启发式算法的结果与下界解进行了比较 ,最终证明该启发式算法具有解决大规模实际问题的潜力。

具有两台专用机、两台通用机的Q_4//C_(max)问题的近似算法

本文讨论具有两台专用机、两台通用机的两组工件的同种类平行机的Q4／／Cmax问题，对这类特殊的排序问题，提出一种启发式算法，得到了最差情况下性能指标的严格的界．

基于模糊规则的GA求解成组调度

研究并行多机成组工件flow-time问题，利用模糊规则量化，使用遗传算法内嵌入模糊控制规则的智能化算法求解这类复杂的组合优化问题，最后给出计算实例及仿真结果,证明了该算法具有解决大规模实际问题的能力。

软计算求解并行多机成组工件调度问题

自从Zade将模糊理论引入求解组合优化问题以来,出现了很多基于模糊规则与智能优化算法相结合的软计算方法.文章尝试将这种方法用于解决并行多机成组工件flow＿time问题.本问题中,设有n个工件计划在M台并行一致的机器上加工.这n个工作根据相似性分为b组.开始加工时,需要一个准备时间.当工件接续在同组工件之后加工时,不需要准备时间;反之,接续在不同组工件之后加工时,需要一个准备时间.本问题的目标是找到一个工件加工的调度顺序序列,使M台机器总的流水时间最小.在文章中,作者首次利用模糊规则量化结合遗传算法的软计算方法求解这类复杂的组合优化问题,最后给出计算实例及仿真结果.

考虑恶化和学习效应的单机成组排序问题

讨论了工件加工时间同时具有恶化和学习效应的单机成组排序问题。在这类问题中,同一组中的工件不允许分开加工,各组之间有安装时间,其中安装时间是工件组开始加工时间的简单线性函数,各组内工件的实际加工时间是关于恶化和学习效应的函数。对目标函数为最大完工时间和总完工时间两类问题分别给出了多项式时间最优算法。

成组加工的单机延误工件个数问题

证明了成组加工的单机延误工件个数问题是强ＮＰ困难的，即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件有相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期，又有相同加工时间的进一步限制情形，由于输入规模的减少，证明了其是普通意义下ＮＰ困难的。

并行多机成组工件调度的禁忌搜索方法

本文讨论的是并行多机成组工件的极小化最大通过时间调度问题。在没有 GT假设下 ,它是一个非常复杂的组合优化问题 ,是 NP难题。在本文中 ,为了解决此类问题 ,作者尝试采用了两种禁忌搜索的智能优化算法方法 :1 )利用单机条件下的最优解的性质 ,提出了禁忌搜索结合启发式的算法 ( TS- HEU) ;2 )禁忌搜索结合分支定界法的算法 ( TS- B&B)。作者作了大量的仿真实验 ,将两种方法进行了比较。实验结果证明 :虽然两种算法都可以求解本问题 ,但是 TS- HEU方法有更高的可靠性和快速的运算能力 ;它同时表明 ,虽然并行多机成组调度问题异常复杂 ,但禁忌搜索结合启发式的智能优化算法仍然有能力有效地解决大规模实际问题。

机器使用时间受限的线性恶化成组排序问题

讨论了单机成组加工问题,工件加工时间是开工时间的简单线性恶化函数,并假设机器在某一时间段内不能进行工件的加工,目标函数为极小化时间表长。给出了该问题的一种0-1整数规划解法。

并行多机成组工件调度的启发式算法

N个成组工件将在M台并行一致的机器上加工 ,当一个工件接在不同组的工件之后时需要装设 ,而接在同组工件之后时不需要重新装设 ,目标函数是使总的通过时间最小·利用最优解的必要条件 ,将单个工件组成基本运行 ,在研究基本运行组合规则的基础上 ,提出了一个基于基本运行的并行多机成组工件调度的启发式算法·在中、小规模水平问题上 ,将启发式算法的结果与最优解的结果进行了比较·效果令人满意·实验证明该启发式算法能够有效地解决成组工件调度的实际问题 ,具有解决中大规模实际问题的潜力·