This paper introduces a new practical schedulingproblem called the resource-constrained project scheduling problem under multiple time constraints, which involves a duration constraint of activity, temporal constrain...
详细信息
This paper introduces a new practical schedulingproblem called the resource-constrained project scheduling problem under multiple time constraints, which involves a duration constraint of activity, temporal constraint, and resource calendar constraint. The duration constraint of the activity exists widely in real-life projects, and it is first proposed as a resource-constrained project scheduling problem in this paper. We prove the defects of the traditional temporal constraint and improve it. The new problem combines three types of time constraints for the first time, which makes it closer to the actual schedulingproblem. We developed a constraint programming optimization model for the new problem and used the IBM ILOG CPLEX-CP version 12.9.0 optimizer to solve it. Computational experiments are carried out to show that the CP optimizer is fast and provides a near-optimum solution to the new problem for projects with hundreds of activities within minutes compared to other metaheuristic methods. The results reported in this paper can be used as a benchmark for other researchers to compare and improve. The new problem contributes to developing a practical decision support system for resolving real-life constraints in projects.
The resource-constrained project scheduling problem is one of the most intractable problems in the field of operation research and management science. It is important for both academic research and engineering applica...
详细信息
The resource-constrained project scheduling problem is one of the most intractable problems in the field of operation research and management science. It is important for both academic research and engineering applications to develop effective solution algorithms for schedulingproblems. In this paper, the activity back-shift response model is introduced for schedulingproblems, based on which a resource-constrainedscheduling model is built, and a two-phase decomposition algorithm is proposed to address the projectresource-constraint and timing optimization. The first stage is resource optimization, where the conflicted activities are resolved by a genetic algorithm. In this case, if parallel activities are scrambling resources during resource optimization, the activity priority, determined by comparing the activity back-shift response time, is applied to dissolve the resource conflict. The second stage is timing optimization. After obtaining the progress plan with optimized resource constraints, activities are adjusted to move forward as much as possible. The validity of the proposed algorithm is verified by a real project case. The computational results reveal that the proposed model and algorithm obtain appropriate results and have the potential to be applied to other similar problems.
In this paper, an improved particle swarm optimization (PSO) algorithm is proposed for the resource-constrained project scheduling problem (RCPSP) which is widely applied in advanced manufacturing, production planning...
详细信息
In this paper, an improved particle swarm optimization (PSO) algorithm is proposed for the resource-constrained project scheduling problem (RCPSP) which is widely applied in advanced manufacturing, production planning, and project management. The algorithm treats the solutions of RCPSP as particle swarms and employs a double justification skill and a move operator for the particles, in association with rank-priority-based representation, greedy random search, and serial scheduling scheme, to execute the intelligent updating process of the swarms to search for better solutions. The integration combines and overhauls the characteristics of both PSO and RCPSP, resulting in enhanced performance. The computational experiments are subsequently conducted to set the adequate parameters and compare the proposed algorithm with other approaches. The results suggest that the proposed PSO algorithm augments the performance by 9.26, 16.17, and 10.45 % for the J30, J60, and J120 instances against the best lower bound-based PSO currently available, respectively. Moreover, the proposed algorithms demonstrate obvious advantage over other proposals in exploring solutions for large-scale RCPSP problems such as the J60 and J120 instances.
The resource-constrained project scheduling problem (RCPSP) is an important and challenging problem in the field of construction management. This paper presents a genetic algorithm (GA) for the RCPSP. The proposed alg...
详细信息
The resource-constrained project scheduling problem (RCPSP) is an important and challenging problem in the field of construction management. This paper presents a genetic algorithm (GA) for the RCPSP. The proposed algorithm introduces several changes in the genetic algorithm paradigm, such as a new selection operator to select parents to recombine;a modified two-point crossover operator with a specific crossover order;and a linearly decreasing probability-based mutation operator. The proposed algorithm was tested using standard benchmark problems of size J30, J60, and J120 from projectschedulingproblem Library (PSPLIB) and compared with 19 state-of-the-art metaheuristics in the literature. The computational results validate that the proposed algorithm is a competitive algorithm for solving the RCPSP.
A branch and bound algorithm is presented for the resource-constrained project scheduling problem (RCPSP). Given are n activities which have to be processed without preemptions. During the processing period of an acti...
详细信息
A branch and bound algorithm is presented for the resource-constrained project scheduling problem (RCPSP). Given are n activities which have to be processed without preemptions. During the processing period of an activity constant amounts of renewable resources are needed where the available capacity of each resource type is limited. Furthermore, finish-start precedence relations between the activities are given. The objective is to determine a schedule with minimal makespan. The branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (induced by the resource constraints). Then it either introduces disjunctive constraints between pairs of activities or places these activities in parallel. Concepts of immediate selection are developed in connection with this branching scheme. Immediate Selection allows to add conjunctions as well as further disjunctions and parallelity relations. Computational results based on the test data of Kolisch ct al. (Kolisch, R., Sprecher, A., Drexl. A., 1995. Management Science 41, 1693-1703.) and Kolisch and Sprecher (Kolisch, R., Sprecher, A., 1997. PSPLIB - A projectschedulingproblem library, EJOR 96, pp. 205-216.) are reported. (C) 1998 Elsevier Science B.V. All rights reserved.
This article considers a resource-constrained project scheduling problem with a single shared resource. In this model, multiple processors are required to complete jobs with a certain amount of shared resource. The su...
详细信息
This article considers a resource-constrained project scheduling problem with a single shared resource. In this model, multiple processors are required to complete jobs with a certain amount of shared resource. The supply of the resource is limited and must be shared between processors. A column-generation-based algorithm with some enhancement techniques, including stabilization, a mechanism to update the solution pool, and an approximate solution technique, is proposed. Finally, extensive computational experiments are conducted to evaluate the performance of the proposed method by comparing it with Lagrangian relaxation, CPLEX and a self-adapting genetic algorithm. The results prove the proposed method has an advantage in terms of the objective and CPU time. Numerical experiments are also conducted to verify the effectiveness of the proposed enhancements.
We consider the resource-constrained project scheduling problem with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource c...
详细信息
We consider the resource-constrained project scheduling problem with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. We propose a genetic algorithm with two versions of crossovers based on the idea of most rational use of constrainedresources. The crossovers uses a heuristic that takes into account the degree of criticality for the resources, which is derived from the solution of a relaxed problem with a constraint on accumulative resources. A numerical experiment with examples from the PCPLIB library has shown that the proposed algorithm has competitive quality. For some examples from the j120 test series the best known solutions were improved and for j60 (50 000 and 500 000 iterations) and for j120 (500 000 iterations) we have obtain the best average deviations of the solutions from the critical path value.
In this paper, we study the resource-constrained project scheduling problem and introduce an annealing-like search heuristic which simulates the cooling process of a gas into a highly-ordered crystal. To achieve this,...
详细信息
In this paper, we study the resource-constrained project scheduling problem and introduce an annealing-like search heuristic which simulates the cooling process of a gas into a highly-ordered crystal. To achieve this, we develop diversification procedures that simulate the motion of high energy molecules as well as a local refinement procedure that simulates the motion of low energy molecules. We further improve the heuristic by incorporating a genetic algorithm framework. The meta-heuristic algorithms are applied to Kolisch's PSPLIB J30, J60 and J120 RCPSP instances. Experimental results show that they are effective and are among the best performing algorithms for the RCPSP.
The studied resource-constrained project scheduling problem (RCPSP) is a classical well-known problem which involves resource, precedence, and temporal constraints and has been applied to many applications. However, t...
详细信息
The studied resource-constrained project scheduling problem (RCPSP) is a classical well-known problem which involves resource, precedence, and temporal constraints and has been applied to many applications. However, the RCPSP is confirmed to be an NP-hard combinatorial problem. Restated, it is hard to be solved in a reasonable time. Therefore, there are many metaheuristics-based schemes for finding near optima of RCPSP were proposed. The particle swarm optimization (PSO) is one of the metaheuristics, and has been verified being an efficient nature-inspired algorithm for many optimization problems. For enhancing the PSO efficiency in solving RCPSP, an effective scheme is suggested. The justification technique is combined with PSO as the proposed justification particle swarm optimization (JPSO), which includes other designed mechanisms. The justification technique adjusts the start time of each activity of the yielded schedule to further shorten the makespan. Moreover, schedules are generated by both forward scheduling particle swarm and backward scheduling particle swarm in this work. Additionally, a mapping scheme and a modified communication mechanism among particles with a designed gbest ratio (GR) are also proposed to further improve the efficiency of the proposed JPSO. Simulation results demonstrate that the proposed JPSO provides an effective and efficient approach for solving RCPSP. (C) 2010 Elsevier Ltd. All rights reserved.
An Improved Discrete Cuckoo Search (IDCS) is proposed in this paper to solve resource-constrained project scheduling problems (RCPSPs). The original Cuckoo Search (CS) was inspired by the breeding behaviour of some cu...
详细信息
An Improved Discrete Cuckoo Search (IDCS) is proposed in this paper to solve resource-constrained project scheduling problems (RCPSPs). The original Cuckoo Search (CS) was inspired by the breeding behaviour of some cuckoo species and was designed specifically for application in continuous optimisation problems, in which the algorithm had been demonstrated to be effective. The proposed IDCS aims to improve the original CS for solving discrete schedulingproblems by reinterpreting its key elements: solution representation scheme, Levy flight and solution improvement operators. An event list solution representation scheme has been used to present projects and a novel event movement and an event recombination operator has been developed to ensure better quality of received results and improve the efficiency of the algorithm. Numerical results have demonstrated that the proposed IDCS can achieve a competitive level of performance compared to other state-of-the-art metaheuristics in solving a set of benchmark instances from a well-known PSPLIB library, especially in solving complex benchmark instances. Crown Copyright (C) 2018 Published by Elsevier B.V. All rights reserved.
暂无评论