共查询到19条相似文献,搜索用时 62 毫秒
1.
为了解决单一算法求解Job Shop调度问题存在的不足,该文提出了一种混合算法,将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况,提出了一种基于关键工序的邻域搜索方法,将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力,提高了蚁群算法的优化能力,达到改善Job Shop调度问题解的质量。实验结果表明,混合算法在较短的时间内,找到了FT10、LA24、LA36等典型benchmarks问题的最优解,得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。 相似文献
2.
针对加工时间具有随机特性的Job shop 调度问题, 提出基于分布估计算法的混合算法. 为增强分布估计算法的种群多样性, 定义了父代工序继承率并设计一种可保留父代个体优良结构特征的重组方法, 该方法在继承父代个体优良结构特征的同时避免了非法解的产生. 在个体选择评价阶段, 采用最优计算量分配策略为每个个体分配模拟量以提高个体评价的精确性. 仿真算例表明了所提出算法的有效性和鲁棒性.
相似文献3.
4.
基于联姻遗传算法的混合FloWshop提前/拖期调度问题 总被引:2,自引:0,他引:2
混合流水车间(Flowshop)提前/拖期调度问题的目标是4~_r-件的提前/拖期惩罚成本最小,这是一个NP完全问题,很难用一般的方法解决。文中首先给出了问题的数学模型,然后采用联姻遗传算法求解该问题。仿真结果表明此算法能有效地解决该类复杂调度问题。 相似文献
5.
6.
公共交货期窗口下提前/拖期问题的多机调度算法 总被引:2,自引:1,他引:1
提出了求公共交货期窗口下提前/拖期都有惩罚的单机零件排序问题最优解的新算法,建立了相应多机零件排序问题的数学模型。在证明关于单机问题最优排序和最优公共交货期性质的若干定理的基础上,给出了求解多机问题的一个启发式算法。数值例子表明,该算法有较为理想的优化效果和工程实用价值。 相似文献
7.
传统遗传算法在求解Job Shop调度问题时存在收敛速度慢,易于早熟的缺点。在病毒遗传算法(VEGA)和灾变遗传算法的基础上提出了一种带有灾变因子的病毒遗传算法(IVEGA-C)。该算法在传统遗传算法的基本结构上加入了病毒感染操作和灾变操作,病毒感染操作实现了同代个体之间横向传递进化信息,灾变操作采用灭绝操作。正是这种改进加快了遗传算法的收敛速度,避免了早熟现象和陷入局部最优解。通过仿真实验验证了IVEGA-C算法在解决Job Shop调度问题中的性能优于传统GA算法和VEGA算法。最后给出了应用该算法的一个实例。 相似文献
8.
针对JIT生产模式下的混合流水车间调度问题特点,提出了采用DE算法与指派规则联合调度策略求解流水车间提前/拖期调度问题。构建了混合流水车间的提前/拖期调度模型。详细论述了DE算法的实施流程和关键问题。在算法实施过程中,首先,采用DE算法进行全局寻优,完成生产任务指派,确定某个工件在某个工序在哪个工位加工;然后采用局部指派规则来确定工件在该工序的开工时间。在满足目标完成时间(交货期)的前提下,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该算法的有效性。 相似文献
9.
不确定条件下的中间存储时间有限的Flow Shop提前/拖期调度问题 总被引:5,自引:0,他引:5
生产调度是企业生产过程中一个重要的部分,在实际生产调度过程中,会存在各种各样的不确定性.本文针对不确定条件下的具有不同交货期窗口的F low Shop提前/拖期调度问题,考虑了产品中间存储时间的有限性,用模糊数学的方法来表示产品的不确定处理时间,在模糊规划理论的基础上建立了相应的调度模型.并借鉴生物免疫系统的概念和机理,提出了解决此类特殊问题的模糊免疫调度算法.仿真结果表明了该模型的有效性和算法的较好的收敛效率. 相似文献
10.
11.
在多平行工作站环境下,为使限定资源分配下的车间调度问题(Job Shop problem,JSP)具有最小总延迟时间;同时又可设定各订单具有不同的开工日(release date)及到期日,提出以可开工时间与结束时间为基础的分解解法,并在遗传算法的基础上构造混合遗传算法(hybrid genetic algorithm,HGA)来实现目标设定。实验结果表明,HGA在问题求解质量与Lingo解的最佳解差异在15%以内,并具备较基本型遗传算法更佳的稳定性。结果显示该算法可帮助管理人员实现智能资源配置与订单调度。 相似文献
12.
解特殊工艺约束拖后调度问题的并行遗传算法 总被引:1,自引:1,他引:0
非等同拖后调度问题作为家纺企业的车间调度问题重要组成部分,有着独特的特点,一方面生产设备非等同,另一方面受特殊工艺的约束。针对该问题的特点,设计了一个基于向量编码的遗传算法。此算法编码方法简单,能有效地反映实际调度方案,并能保证满足约束条件,收敛速度快。同时为更好地适应调度实时性和解大型企业此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性。 相似文献
13.
14.
15.
This paper considers the problem of scheduling a single machine, in which the objective function is to minimize the weighted quadratic earliness and tardiness penalties and no machine idle time is allowed. We develop a branch and bound algorithm involving the implementation of lower and upper bounding procedures as well as some dominance rules. The lower bound is designed based on a lagrangian relaxation method and the upper bound includes two phases, one for constructing initial schedules and the other for improving them. Computational experiments on a set of randomly generated instances show that one of the proposed heuristics, used as an upper bound, has an average gap less than 1.3% for instances optimally solved. The results indicate that both the lower and upper bounds are very tight and the branch-and-bound algorithm is the first algorithm that is able to optimally solve problems with up to 30 jobs in a reasonable amount of time. 相似文献
16.
In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a genetic approach based on a random key alphabet. Several genetic algorithms based on this approach are presented. These versions differ on the generation of the initial population, as well as on the use of local search. The proposed procedures are compared with existing heuristics, as well as with optimal solutions for the smaller instance sizes. 相似文献
17.
对具有不同时间窗的提前/拖期调度方法应用于飞机地面作业调度进行了研究,用模糊规划建立数学模型,用三角模糊数表示了地面作业中时间的不确定性,应用粒子群优化算法对模型进行了仿真。实验结果表明,在不同情况下该算法都能取得较为满意的结果。 相似文献
18.
Amir Hamidinia Sahand Khakabimamaghani Mohammad Mahdavi Mazdeh Mostafa Jafari 《Computers & Industrial Engineering》2012,62(1):29-38
This paper endeavors to solve a novel complex single-machine scheduling problem using two different approaches. One approach exploits mathematical modeling, and the other is based upon genetic algorithms. The problem involves earliness, tardiness, and inventory costs and considers a batched delivery system. The same conditions might apply to some real supply chains, in which delivery of products is conducted in a batched form and with some costs. In such delivery systems, the act of buffering the products can have both positive effects (i.e., decreasing the delivery costs and early jobs) and negative ones (i.e., increasing the number of tardy and holding costs). Accordingly, the proposed solution takes into account both effects and tries to find a trade-off between them to hold the total costs low. The suggestions are compared to existing solutions for older non-batched systems and have illustrated outperformance. 相似文献
19.
Job shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对该问题提出一种新型萤火虫求解算法,分析了萤火虫算法的仿生原理,给出了萤火虫算法求解JSP问题的求解步骤,并通过典型基准测试实例对算法进行了仿真实验,并与GA和PSO算法进行了比较,验证了该算法参数少,操作简单,收敛速度快,在生产调度中有广泛的应用前景。 相似文献