共查询到20条相似文献,搜索用时 0 毫秒
1.
Alkhateeb Faisal Abed-alguni Bilal H. Al-rousan Mohammad Hani 《The Journal of supercomputing》2022,78(4):4799-4826
The Journal of Supercomputing - The job shop scheduling problem (JSSP) is a popular NP-hard scheduling problem that simulates the scheduling problems of different real-world applications in fields... 相似文献
2.
求解TSP问题的改进模拟退火遗传算法 总被引:4,自引:1,他引:4
巡回旅行商问题(TSP)是最典型的NP的难题,遗传算法(GA)是解决这类问题的有效方法之一。由于该问题的解是一种特殊的序列,一般的交叉算子在该问题的求解效果方面并不理想,提出了贪心的3PM交叉算子,同时又引入退火选择方法,形成一种新的模拟退火遗传算法GCBSAGA(Greed Cross-3PM Based on Simulated Annealing Genetic Algorithms)。该算法还将模拟退火算法与遗传算法相结合,使得遗传算法在前期发挥着全局搜索的强大功能,很容易收敛到全局较优解;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能,最终收敛到全局最优解。经过国际公认的TSPLIB提供的实验数据的验证,GCBSAGA在实例eil76、eil101、pr144、st70均找到了比TSPLIB提供的最优路径更优的解。 相似文献
3.
A hybrid simulated annealing algorithm based on a novel immune mechanism is proposed for the job shop scheduling problem with the objective of minimizing total weighted tardiness. The proposed immune procedure is built on the following fundamental idea: the bottleneck jobs existing in each scheduling instance generally constitute the key factors in the attempt to improve the quality of final schedules, and thus, the sequencing of these jobs needs more intensive optimization. To quantitatively describe the bottleneck job distribution, we design a fuzzy inference system for evaluating the bottleneck level (i.e. the criticality) of each job. By combining the immune procedure with a simulated annealing algorithm, we design a hybrid optimization algorithm which is subsequently tested on a number of job shop instances. Computational results for different-sized instances show that the proposed hybrid algorithm performs effectively and converges fast to satisfactory solutions. 相似文献
4.
This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which solve to optimality the resource constrained scheduling problem at the first stage of the flowshop, and at the same time, minimize the makespan in the flowshop by selecting appropriate jobs for simultaneous processing. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing solutions with the lower bound on the optimal makespan. The extensive computational experiment shows that the proposed heuristic algorithms are able to produce near-optimal solutions in short computational time. 相似文献
5.
针对置换流水车间调度问题(PFSP),提出了一种混合鸟群算法(HBSA)以更加有效地最小化最大完工时间。首先,为了改善初始种群的质量和多样性,结合一种基于NEH(Nawaz-Enscore-Ham)的启发式算法和混沌映射提出了一种新的种群初始化方法;其次,为了使算法能够处理离散的调度问题,采用最大排序值(LRV)规则将连续的位置值转换为离散的工件排序;最后,为了强化算法对解空间的探索能力,借鉴变邻域搜索(VNS)和迭代贪婪(IG)算法的思想针对个体最佳工件排序和种群最佳工件排序分别提出了局部搜索方法。针对广泛使用的Rec标准测试集进行了仿真测试,并与目前有效的元启发式算法——刘等提出的混合差分进化算法(L-HDE)、混合共生生物搜索算法(HSOS)、离散狼群算法(DWPA)、多班级教学优化算法(MCTLBO)相比较,结果表明,HBSA取得的最佳相对误差(BRE)、平均相对误差(ARE)的平均值比上述四种算法至少下降了73.3%、76.8%,从而证明HBSA具有更强的寻优能力和更好的稳定性。尤其是针对测试算例Rec25和Rec27,仅HBSA的求解结果达到了目前已知最优解,进一步证明了其优越性。 相似文献
6.
7.
A simulated annealing with multiple‐search paths and parallel computation for a comprehensive flowshop scheduling problem
下载免费PDF全文
![点击此处可从《International Transactions in Operational Research》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Fantahun M. Defersha 《International Transactions in Operational Research》2015,22(4):669-691
Recent studies have demonstrated that the performance of a simulated annealing algorithm can be improved by following multiple‐search paths and parallel computation. In this paper, we use these strategies to solve a comprehensive mathematical model for a flexible flowshop lot streaming problem. In the flexible flowshop environment, a number of jobs will be processed in several consecutive production stages, and each stage may involve a certain number of parallel machines that may not be identical. Each job has to be split into several unequal sublots by following the concept of lot streaming. The sublots are to be processed in the order of the stages, and sublots of certain products may skip some stages. This complex problem also incorporates sequence‐dependent setup times, the anticipatory or nonanticipatory nature of setups, release dates for machines, and machine eligibility. Numerical examples are presented to demonstrate the effectiveness of lot streaming in hybrid flowshops, the performance of the proposed simulated annealing algorithm, and the improvements achieved using parallel computation. 相似文献
8.
TSP问题是典型的NP-hard组合优化问题,遗传算法是求解此类问题的一种方法,但它存在如何较快地找到全局最优解,并防止“早熟”收敛的问题。针对上述问题并结合TSP问题的特点,提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算法。为了解决群体的多样性和收敛速度的矛盾,采用了部分近邻法来生成初始种群,生成的初始种群优于随机产生初始种群。仿真实验结果证明,该算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高。 相似文献
9.
零空闲流水车间问题(NIFSP)是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。 相似文献
10.
解决车辆路径问题的混合模拟退火算法 总被引:1,自引:1,他引:1
构造了车辆路径问题的双目标数学模型,据此提出了混合模拟退火算法.该算法主要将模拟退火算法和2-opt优化算法有机地融合,从而使混合后的算法不但具有这两种算法的优点,而且还克服了他们相应的缺点.针对车辆路径问题,重点阐述了混合模拟退火算法的设计思路.实验结果表明,混合模拟退火算法不仅可以取得很好的计算结果,而且还具有收敛速度快等优点. 相似文献
11.
To minimize the makespan in permutation flowshop scheduling problems, a hybrid discrete artificial bee colony (HDABC) algorithm is presented. In the HDABC, each solution to the problem is called a food source and represented by a discrete job permutation. First, the initial population with certain quality and diversity is generated from Greedy Randomized Adaptive Search Procedure (GRASP) based on Nawaz–Enscore–Ham (NEH) heuristics. Second, the discrete operators and algorithm, such as insert, swap, path relinking and GRASP are applied to generate new solution for the employed bees, onlookers and scouts. Moreover, local search is applied to the best one. The presented algorithm is tested on scheduling problem benchmarks. Experimental results show its efficiency. 相似文献
12.
Various heuristic based methods are available in literature for optimally solving job shop scheduling problems (JSSP). In this research work a novel approach is proposed which hybridizes fast simulated annealing (FSA) with quenching. The proposed algorithm uses FSA for global search and quenching for localized search in neighborhood of current solution, while tabu list is used to restrict search from revisiting previously explored solutions. FSA is started with a relatively higher temperature and as search progresses temperature is gradually reduced to a value close to zero. The overall best solution (BS) is maintained throughout execution of the algorithm. If no improvement is observed in BS for certain number of iterations then quenching cycle is invoked. During quenching cycle current temperature is reduced to nearly freezing point and iterations are increased by many folds, as a result of this change search becomes nearly greedy. The strength of the proposed algorithm is that even in quenching mode escape from local optima is possible due to use of Cauchy probability distribution and non-zero temperature. At the completion of quenching cycle previous values of search parameters are restored and FSA takes over, which moves search into another region of solution space. Effectiveness of proposed algorithm is established by solving 88 well known benchmark problems taken form published work. The proposed algorithm was able to solve 45 problems optimally to their respective best known values in reasonable time. The proposed algorithm has been compared with 18 other published works. The experimental results show that the proposed algorithm is efficient in finding solution to JSSP. 相似文献
13.
This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and renewable resources at both the stages. The resource requirements are of a 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Four heuristic algorithms using linear programming are proposed for solving this problem. Performance of the algorithms is analyzed experimentally by comparing heuristic solutions with the lower bound on the optimal makespan. Statistical comparative analysis of the developed algorithms is carried out. The results of a computational experiment show that the proposed algorithms are able to produce good quality solutions in a small amount of computation time. 相似文献
14.
《Computers & Industrial Engineering》2011,60(4):509-519
This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and renewable resources at both the stages. The resource requirements are of a 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Four heuristic algorithms using linear programming are proposed for solving this problem. Performance of the algorithms is analyzed experimentally by comparing heuristic solutions with the lower bound on the optimal makespan. Statistical comparative analysis of the developed algorithms is carried out. The results of a computational experiment show that the proposed algorithms are able to produce good quality solutions in a small amount of computation time. 相似文献
15.
针对以最小化项目工期为目标的资源受限项目调度问题(RCPSP),提出将模拟退火算法融合到遗传算法中,以改善遗传算法局部搜索性能,增强进化能力的遗传模拟退火算法——RCPSPGSA。在每次进化迭代过程中,下一代种群的个体需经过模拟退火算法改进,并通过在每次迭代结束前进行降温操作保证遗传算法和模拟退火算法具有相同的收敛方向和速度。算法在RCPSP标准测试问题库PSPLIB上进行数值仿真实验,并采用正交实验分析法解决参数选择问题。实验结果证明选择的参数组合具有突出的性能,RCPSPGSA是求解RCPSP的有效算法。 相似文献
16.
The Journal of Supercomputing - The central cloud facilities based on virtual machines offer many benefits to reduce the scheduling costs and improve service availability and accessibility. The... 相似文献
17.
配送和回收一体化的车辆路径问题(VRPSDP)是一种非常复杂的NP难题。针对这一问题,设计了一种改进的模拟退火遗传算法ISAGA,采用非零自然数编码机制和弱可行解到强可行解的解码机制,将3PM交叉算子和退火选择相结合,形成贪心3PM交叉算子,引进insert 、swap和2-opt分别对解进行迭代优化,并将模拟退火算法和遗传算法巧妙地结合,使得遗传算法在前期发挥着全局搜索的强大功能;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证,ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。 相似文献
18.
Natural Computing - Recently, the solution algorithm for multiobjective scheduling problems has gained more and more concerns from the community of operational research since many real-world... 相似文献
19.
The purpose of this research is to determine an optimal batch size for a product and purchasing policy of associated raw materials. Like most other practical situation, this manufacturing firm has a limited storage space and transportation fleet of known capacity. The mathematical formulation of the problem indicates that the model is a constrained nonlinear integer program. Considering the complexity of solving such model, we investigate the use of genetic algorithms (GAs) for solving this model. We develop GA code with three different penalty functions usually used for constraint optimizations. The model is also solved using an existing commercial optimization package to compare the solution. The detailed computational results are presented. 相似文献
20.
Elyn L. Solano-Charris Jairo R. Montoya-Torres Carlos D. Paternina-Arboleda 《Journal of Intelligent Manufacturing》2011,22(5):815-822
We consider the problem of scheduling jobs in a hybrid flowshop with two stages. Our objective is to minimize both the makespan
and the total completion time of jobs. This problem has been little studied in the literature. To solve the problem, we propose
an ant colony optimization procedure. Computational experiments are conducted using random-generated instances from the literature.
In comparison against other well-known heuristics from the literature, experimental results show that our algorithm outperforms
such heuristics. 相似文献