This paper presents a metaheuristic algorithm for resource-constrained project scheduling problem (RCPSP) in PERT networks. A PERT-type project, where activities require resources of various types with random duration...
详细信息
This paper presents a metaheuristic algorithm for resource-constrained project scheduling problem (RCPSP) in PERT networks. A PERT-type project, where activities require resources of various types with random duration, is considered. The problem is to minimize the regular criterion namely project's make-span. The resource project scheduling model is an NP-hard, therefore to obtain a precise solution, a metaheuristic algorithm is suggested namely hybrid scatter search (HSS). The path relinking algorithm and two operators like crossover and prominent permutation-based are applied to solve the problem. The problem has to be solved at each decision point, when at least more than one activity is ready to be operated but the available amount of resources is limited. The metaheuristic model is illustrated by a numerical example. In order to validate the performance of new hybrid metaheuristic algorithm, solutions are compared with "optimal solution" for small networks. Also the efficiency of the proposed algorithm, for real world problems, in terms of solution quality, is compared with well-reported benchmark test problems available on the PSPLIB. The computational results reveal that the proposed algorithm has appropriate results for small networks and real world problems. (C) 2010 Elsevier Ltd. All rights reserved.
Particle Swarm Optimization (PSO) belongs to a class of algorithms inspired by natural social intelligent behaviors, called Swarm Intelligence (SI). PSO has been successfully applied to solve continuous optimization p...
详细信息
ISBN:
(纸本)9781424481262
Particle Swarm Optimization (PSO) belongs to a class of algorithms inspired by natural social intelligent behaviors, called Swarm Intelligence (SI). PSO has been successfully applied to solve continuous optimization problems, however, its potential in discrete problems has not been sufficiently explored. Recent works have proposed hybridization of PSO using local search and path relinking algorithms with promising results. This paper aims to present a hybrid PSO algorithm that uses local search and pathrelinking too, but differently to the previous approaches, this works maintains the main PSO concept for the update of the velocity of the particle. The paper describes the proposed algorithm and a set of experiments with the Traveling Salesman Problem (TSP). The results are compared to other Particle Swarm Optimization algorithms presented previously for the same problem. The results are encouraging and reinforce the idea that PSO algorithms can also provide good results when dealing with discrete problems.
This paper considers a multi-skilled project scheduling problem that is a newly developed extension of the Resource-Constrained Project Scheduling Problem (RCPSP). The main difference in such problems, compared with c...
详细信息
This paper considers a multi-skilled project scheduling problem that is a newly developed extension of the Resource-Constrained Project Scheduling Problem (RCPSP). The main difference in such problems, compared with classic scheduling problems, is associated with the given resources, which are only dependent on human type. Additionally, the net present value of a given project is considered by its cash in and out flow to guarantee project success. To solve the given problem, an enhanced two-phase method is proposed using genetic and path relinking algorithms, whose parameters are tuned by the Taguchi method to provide robust comparisons. Furthermore, the potential changes in the project execution method are considered for some of the mostly used payment methods. Finally, some different-sized instances are tested to check the performance and efficiency of the proposed method. (C) 2014 Sharif University of Technology. All rights reserved.
Scheduling is the process of determining where and when to perform manufacturing measures, which is required to conduct activities in a timely, efficient, and cost-effective manner. In this paper, an algorithm is prop...
详细信息
Scheduling is the process of determining where and when to perform manufacturing measures, which is required to conduct activities in a timely, efficient, and cost-effective manner. In this paper, an algorithm is proposed as a solution to the flow shop scheduling problem which holds an important place in the scheduling literature. The path relinking algorithm and data mining are used to solve the flow shop scheduling problem studied here. While DM is used for globally searching the solution space, pathrelinking is used for local search. Data mining is a method for extracting the embedded information in a cluster that includes implicit information. pathrelinking is an algorithm that advances by making binary displacements in order to convert the initial solution to the guiding solution and it is repeated by assigning the best obtained solution within this process to the starting point. The efficiency of the model for Taillard's flow shop scheduling problems was tested. Consequently, it is possible to solve the large-size problem without considerable mathematical background. The obtained results showed that the proposed method comparatively performed as good as other metaheuristic methods. (C) 2021 Sharif University of Technology. All rights reserved.
暂无评论