检索结果-内蒙古大学图书馆

A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem

引用

INFORMATION SCIENCES 2014年 277卷 680-693页

作者： Koulinas, Georgios Kotsikas, Lazaros Anagnostopoulos, Konstantinos Democritus Univ Thrace Dept Prod & Management Engn GR-67100 Xanthi Greece

In this paper, we propose a particle swarm optimization (PSO) based hyper-heuristic algorithm for solving the resource constrained project scheduling problem (RCPSP). To the best of our knowledge, this is the first attempt to develop a PSO hyper-heuristic and apply to the classic RCPSP. The hyper-heuristic works as an upper-level algorithm that controls several low-level heuristics which operate to the solution space. The solution representation is based on random keys. Active schedules are constructed by the serial scheduling generation scheme using the priorities of the activities which are modified by the low-level heuristics of the algorithm. Also, the double justification operator, i.e. a forward-backward improvement procedure, is applied to all solutions. The proposed approach was tested on a set of standard problem instances of the well-known library PSPLIB and compared with other approaches from the literature. The promising computational results validate the effectiveness of the proposed approach. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Particle swarm optimization Hyper-heuristics project scheduling resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

引用

JOURNAL OF HEURISTICS 2011年第5期17卷 467-486页

作者： Goncalves, Jose Fernando Resende, Mauricio G. C. Mendes, Jorge J. M. AT&T Labs Res Algorithms & Optimizat Res Dept Florham Pk NJ 07932 USA Univ Porto Fac Econ Porto LIAAD P-4200464 Oporto Portugal Inst Politecn Porto Inst Super Engn Porto P-4200072 Oporto Portugal

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

关键词： project management scheduling Genetic algorithms Random keys Forward-backward improvement resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Solving the resource constrained project scheduling problem using the parallel Tabu Search designed for the CUDA platform

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 77卷 58-68页

作者： Bukata, Libor Sucha, Premysl Hanzalek, Zdenek Czech Tech Univ Dept Control Engn Prague 12135 2 Czech Republic

The resource constrained project scheduling problem, which is considered to be difficult to tackle even for small instances, is a well-known scheduling problem in the operations research domain. To solve the problem we have proposed a parallel Tabu Search algorithm to find high quality solutions in a reasonable time. We show that our parallel Tabu Search algorithm for graphics cards (GPUs) outperforms other existing Tabu Search approaches in terms of quality of solutions and the number of evaluated schedules per second. Moreover, the algorithm for graphics cards is about 10.5/42.7 times faster (J90 benchmark instances) than the optimized parallel/sequential algorithm for the Central Processing Unit (CPU). The same quality of solutions is achieved up to 5.4/22 times faster in comparison to the parallel/sequential CPU algorithm respectively. The advantages of the GPU version arise from the sophisticated data-structures and their suitable placement in the device memory, tailor-made methods, and last but not least the effective communication scheme. (C) 2014 Elsevier Inc. All rights reserved.

关键词： resource constrained project scheduling problem Parallel Tabu Search CUDA Homogeneous model GPU

来源：评论

学校读者我要写书评

暂无评论

Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第5期39卷 1187-1194页

作者： Haouari, Mohamed Kooli, Anis Neron, Emmanuel Ecole Polytech Tunisie Combinatorial Optimizat Res Grp ROI La Marsa 2078 Tunisia Ozyegin Univ Fac Engn Dept Ind Engn Istanbul Turkey King Saud Univ Coll Engn AMT Riyadh 11451 Saudi Arabia Univ Tours Ecole Polytech Lab Informat EA2101 F-37200 Tours France

We present new and effective lower bounds for the resource constrained project scheduling problem. This problem is widely known to be notoriously difficult to solve due to the lack of lower bounds that are both tight and fast. In this paper, we propose several new lower bounds that are based on the concept of energetic reasoning. A major contribution of this work is to investigate several enhanced new feasibility tests that prove useful for deriving new lower bounds that consistently outperform the classical energetic reasoning-based lower bound. In particular, we present the results of a comprehensive computational study, carried out on 1560 benchmark instances, that provides strong evidence that a deceptively simple dual feasible function-based lower bound is highly competitive with a state-of-the-art lower bound while being extremely fast. Furthermore, we found that an effective shaving procedure enables to derive an excellent lower bound that often outperforms the best bound from the literature while being significantly simpler. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： resource constrained project scheduling problem Lower bounds Energetic reasoning Dual feasible functions

来源：评论

学校读者我要写书评

暂无评论

A preemptive bound for the resource constrained project scheduling problem

引用

JOURNAL OF scheduling 2014年第3期17卷 237-248页

作者： Haouari, Mohamed Kooli, Anis Neron, Emmanuel Carlier, Jacques Qatar Univ Coll Engn Dept Mech & Ind Engn Doha Qatar Univ Tunis Ecole Super Sci Econ & Commerciales Tunis Montfleury 1089 Tunisia Univ Tours Equipe Ordonnancement & Conduite Lab Informat EA 2101ERL CNRS 6305 F-37200 Tours France Univ Technol Compiegne Lab HeuDiaSyC CNRS UMR 7253 F-60205 Compiegne France

The resource constrained project scheduling problem is one of the most intensively investigated scheduling problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging -hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances.

关键词： resource constrained project scheduling problem Destructive lower bounds Preemptive relaxation Linear programming

来源：评论

学校读者我要写书评

暂无评论

A multi-agent optimization algorithm for resource constrained project scheduling problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2015年第15-16期42卷 6039-6049页

作者： Zheng, Xiao-long Wang, Ling Tsinghua Univ Dept Automat Tsinghua Natl Lab Informat Sci & Technol TNList Beijing 100084 Peoples R China

In this paper, a multi-agent optimization algorithm (MAOA) is proposed for solving the resource-constrained project scheduling problem (RCPSP). In the MAOA, multiple agents work in a grouped environment where each agent represents a feasible solution. The evolution of agents is achieved by using four main elements in the MAOA, including social behavior, autonomous behavior, self-learning, and environment adjustment. The social behavior includes the global one and the local one for performing exploration. Through the global social behavior, the leader agent in every group is guided by the global best leader. Through the local social behavior, each agent is guided by its own leader agent. Through the autonomous behavior, each agent exploits its own neighborhood. Through the self-learning, the best agent performs an intensified search to further exploit the promising region. Meanwhile, some agents perform migration among groups to adjust the environment dynamically for information sharing. The implementation of the MAOA for solving the RCPSP is presented in detail, and the effect of key parameters of the MAOA is investigated based on the Taguchi method of design of experiment. Numerical testing results are provided by using three sets of benchmarking instances. The comparisons to the existing algorithms demonstrate the effectiveness of the proposed MAOA for solving the RCPSP. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： resource constrained project scheduling problem Multi-agent system Optimization algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing redundant resources for the resource constrained project scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第3期176卷 1452-1463页

作者： Carlier, Jacques Neron, Emmanuel Univ Technol Compiegne CNRS UMR 6599 Ctr Rech Royallieu F-60205 Compiegne France Univ Tours Ecole Polytech Lab Informat Dept Informat F-37200 Tours France

Several efficient lower bounds and time-bound adjustment methods for the resource constrained project scheduling problem (RCPSP) have recently been proposed. Some of them are based on redundant resources. In this paper we define redundant functions which are very useful for computing redundant resources. We also describe an algorithm for computing all maximal redundant functions. Once all these redundant functions have been determined, we have to identify those that are useful for bounding. Surprisingly, their number is reasonable even for large resource capacities, so a representative subset of them can be tabulated to be used efficiently. Computational results on classical RCPSP instances confirm their usefulness. (c) 2005 Elsevier B.V. All rights reserved.

关键词： resource constrained project scheduling problem lower bounds redundant functions

来源：评论

学校读者我要写书评

暂无评论

A hybrid metaheuristic method for solving resource constrained project scheduling problem

引用

EVOLUTIONARY INTELLIGENCE 2023年第2期16卷 519-537页

作者： Shuvo, Ohiduzzaman Golder, Swajan Islam, Md Rafiqul Khulna Univ Comp Sci & Engn Discipline Khulna 9208 Bangladesh

resource constrained project scheduling problem (RCPSP) is a renowned variant of the scheduling problem. RCPSP is very important in production and management but computationally hard. It is widely used in many fields like job shop scheduling, flow shop scheduling, transactional planning, wireless communication etc. The objective of solving RCPSP is to obtain minimum makespan maintaining all constraints. There are some exact, approximate, heuristic and metaheuristic algorithms which were proposed to solve this problem. RCPSP is an NP-hard problem. Chemical reaction optimization (CRO) is a population based metaheuristic method to solve such problems and it shows better performance comparing with some other existing algorithms. CRO explores the large search space both locally and globally using its four operators. Genetic algorithm (GA) is also a nature inspired algorithm which is used to solve various optimization problems. In this paper, we are proposing a hybrid metaheuristic approach that integrates chemical reaction optimization (CRO) and genetic algorithm (GA) named CRO-GA to solve RCPSP. We have redesigned the basic operators of CRO and GA to find out the solutions. An additional operator called priority based selection operator is used in CRO to adjust with GA. Our proposed method is compared with other related approaches such as adaptive particle swarm optimization (A-PSO), multi agent optimization algorithm (MAOA), artificial bee colony (ABC), genetic algorithm (GA) which are state of the art for the RCPSP. The experimental results show that our proposed methodology gives better results than other existing algorithms to solve RCPSP with less computational time.

关键词： Chemical reaction optimization NP-hard resource constrained project scheduling problem Makespan

来源：评论

学校读者我要写书评

暂无评论

Solving the resource constrained project scheduling problem with quantum annealing

引用

SCIENTIFIC REPORTS 2024年第1期14卷 1-23页

作者： Armas, Luis Fernando Perez Creemers, Stefan Deleplanque, Samuel Univ Lille IESEG Sch Management CNRS UMR 9221 LEM Lille Econ Management 3 Rue Digue F-59000 Lille Nord France Univ Lille CNRS Cent Lille Univ Polytech Hauts FranceJuniaUMR 8520IEMN 41 Bd Vauban F-59000 Lille France ORSTAT KU Leuven Naamsestr 69 B-3000 Leuven Belgium Catholic Univ Louvain Ctr Operat Res & Econometr CORE Voie Roman Pays 34 B-1348 Louvain La Neuve Belgium

Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations research.

关键词： resource constrained project scheduling problem Quantum optimization Quantum annealing

来源：评论

学校读者我要写书评

暂无评论

resource constrained project scheduling problem using Genetic Algorithms

引用

Intelligent Automation and Soft Computing 1997年第3期3卷 273-286页

作者： Cheng, Runwei Gen, Mitsuo Department of Industrial and Systems Engineering Ashikaga Institute of Technology Ashikaga 326 Japan

resource constrained project scheduling problem is a well known NP-hard problem. This paper describes an implementation of a hybrid genetic algorithm to solve this problem. A new approach is taken to guide the design of genetic operators for this hybrid approach. One operator is designed to perform wide spread search to try to explore the area beyond local optima. The other is designed to perform intensive search to try to find an improved solution. The suggested approach can significantly improve the performance of genetic algorithms both in term of speed and accuracy. The proposed approach has been tested on two standard test problems. It can find the known optimum very rapidly and is superior to all existing heuristic techniques. The proposed approach can be also applied to other difficult combinatorial optimization problems. © 1997 Taylor & Francis Group, LLC.

关键词： Combinatorial optimization Genetic algorithm and hybrid approach Local search technique resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：