共查询到18条相似文献,搜索用时 62 毫秒
1.
2.
3.
4.
一种使用再编码染色体求解Job-Shop问题的并行遗传算法 总被引:2,自引:0,他引:2
使用遗传算法求解Job Shop问题的一个关键问题是编码。本文提出了一种求解Job Shop问题的新遗传算法———RPGA(Re encodingParallelGA)。此方法的编码方式将Job Shop问题转换为一个TSP(TravelingSalesmanProblem)问题 ,使得关于TSP问题的遗传算法的方法可以用于解决Job Shop问题。这种编码方式可以满足Job Shop问题对工件加工顺序的要求 ,避免在进化过程中产生非可行解。RPGA最重要的特点在于染色体的再编码过程 ,再编码过程根据各工序的开工时间先后对染色体的各基因重新赋值 ,使得编码空间和解空间一一对应。最后 ,本方法使用MPI并行编程技术实现了粗粒度的并行模型 ,在此模型上我们对Fisher和Thompson的 10× 10问题进行了求解实验。实验表明本方法有着良好的求解效率 ,也证明了对染色体再编码过程对此问题的重要性。 相似文献
5.
Job-Shop调度问题的分批和最优化策略 总被引:3,自引:0,他引:3
缩短Job-Shop生产的工期除了用优化调度方法外,还可以对批量进行适当的分割,进一步优化生产计划.论述一种简化的Job-Shop批量分割的优化调度的方法,解决分批调度的原则、位置和对工期影响等问题,提出分批的步骤和方法.根据工艺路线的约束,用状态变量描述调度过程,在此基础上用一种启发式的算法进行通常的优化调度,在此调度计划中用一种算法找出工期最长的关键路径.分批应遵循3个规则:①分批的步骤是先优化后分批;②分批应该在这样的一个设备上,即该设备-任务完成后其加工路线上的下一个设备应该有空闲时间;③该任务工序及其后续工序至少有一个位于关键线路上.将任务-工序的等待空闲时间和回溯等待时间与当前工序和后续工序的工时等分后的可能节约工期比较,决定此处是否可以分批及其分批的大小.分批和优化达到了目标--最长工期最小. 相似文献
6.
7.
求解作业车间调度问题的双倍体遗传算法与软件实现 总被引:15,自引:1,他引:15
作业车间调度问题是最困难的组合优化问题之一,也是计算机集成制造系统中的一个关键环节,在实际生产中具有广泛应用。为此,提出了双倍体遗传算法。该算法提供了一种记忆以前有用的基因块的功能,保留了某些低适应度染色体中的一些局部基因块,构成最优解中的基因片段,提高遗传算法的适应能力。与已有算法相比,基于双倍体遗传算法的作业车间调度方法,显著提高了搜索效率,改进了收敛性能。 相似文献
8.
提出了将Hopfield神经网络与模拟退火相结合以求解Job-Shop类调度问题的算法.该算法给出了Job-Shop类调度问题的约束条件,并且直接把问题的各种约束条件表示为Hopfield神经网络的能量函数项.为避免Hopfield神经网络容易收敛到局部极小解而产生非法调度解的缺点,将模拟退火算法应用于Hopfield神经网络求解,使Hopfield神经网络收敛到能量函数的全局最优解,从而保证神经网络输出是一个可行的调度方案.通过仿真实例验证了该算法的可行性. 相似文献
9.
求解作业车间调度问题的一种改进遗传算法 总被引:19,自引:3,他引:19
为克服传统遗传算法解决车间作业调度问题的局限性,综合遗传算法和局部搜索的优点,提出一种改进的遗传算法。为基于工序的编码提出了一种新的POX交叉算子。同时,为克服传统遗传算法在求解车间作业调度问题时的早熟收敛,设计了一种子代交替模式的交叉方式,并运用局部搜索改善交叉和变异后得到的调度解,将提出的改进遗传算法应用于MuthandThompson基准问题的实验运行,显示了该算法的有效性。 相似文献
10.
基于主-从遗传算法求解柔性调度问题 总被引:1,自引:1,他引:1
通过分析柔性作业车间调度问题中工件与设备的特征及两者间的关系,提出了一种主一从遗传算法的调度方案。在该算法中,主、从染色体分别采用工件基因块和设备基因块的分块编码。主染色体代表可行加工路径组合,从染色体代表主染色体约束下的可行调度方案。然后,以最小化工件延迟时间为目标,为主染色体设计选择和多点变异两类遗传操作;以最小化设备空闲时间为目标,为从染色体设计选择、多点交叉和多点变异3类遗传操作。从染色体适应值取其代表的调度方案中工件流通时间的倒数,主染色体适应值取其对应从染色体种群的最优适应值。这种双层多点遗传操作避免了非可行解的产生,并可采用类似旅行商问题的遗传操作。最后,通过仿真和比较实验,验证了该算法的有效性。 相似文献
11.
12.
13.
14.
用效率调度算法求解非标准作业车间调度问题 总被引:3,自引:2,他引:3
作业车间调度问题是一类具有次序约束和资源约束的较大规模的组合优化问题,本文所描述的非标准作业车间调度问题,放宽了资源约束的条件,具有更大的寻优空间,针对这种复杂的组合优化问题,本文构造了相应的目标函数并提出一种效率调度算法来求解此问题,经分析和实践验证,获得了满意的结果。 相似文献
15.
16.
基于过滤定向搜索的Job-Shop调度算法及评价 总被引:1,自引:0,他引:1
对以Makespan最小为目标的Job Shop调度问题进行了研究。首先对Job Shop调度问题进行了描述,在此基础上建立了一种求解Job Shop调度问题的启发式优化算法———基于过滤定向搜索的算法,同时结合实例对算法的优化过程作了具体描述。最后通过不同规模的Benchmark实例对该算法进行了仿真评价,结果表明基于过滤定向搜索的算法搜索效率高,解的性能好,是一种有效的优化算法。 相似文献
17.
一种车间调度系统算法的设计与实现 总被引:1,自引:0,他引:1
采用一种混和编码方式,并将局部搜索运用到变异算子,该方法能及时反映种群在进化过程中的过早收敛程度,不仅能加快计算速度,而且还能增强算法的全局收敛性.算法以其通用性强,算法简单等特点,可被广泛应用到车间调度问题的优化中. 相似文献
18.
基于细菌觅食算法车间调度系统的研究 总被引:1,自引:0,他引:1
细菌觅食优化算法最早于2002年提出,是一种于基于人体内的大肠杆菌的觅食行为提出来的新的进化计算方法.在本文中,我们改进的基于群体搜索方法是细菌觅食算法的一个重要内容,细菌觅食算法在这里被运用到了车间生产调度系统中来,极大地优化了车间调度系统的加工生产过程. 相似文献