We describe a time-oriented branch-and-bound algorithm for the resource-constrained project scheduling problem which explores the set of active schedules by enumerating possible activity start times, The algorithm use...
详细信息
We describe a time-oriented branch-and-bound algorithm for the resource-constrained project scheduling problem which explores the set of active schedules by enumerating possible activity start times, The algorithm uses constraint-propagation techniques that exploit the temporal and resource constraints of the problem in order to reduce the search space. Computational experiments with large, systematically generated benchmark test sets, ranging in size from thirty to one hundred and twenty activities per problem instance, show that the algorithm scales well and is competitive with other exact solution approaches. The computational results show that the most difficult problems occur when scarce resource supply and the structure of the resource demand cause a problem to be highly disjunctive.
We consider a resource-constrained project scheduling problem originating in particle therapy for cancer treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear programmi...
详细信息
We consider a resource-constrained project scheduling problem originating in particle therapy for cancer treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear programming techniques such as time-indexed formulations or discrete-event formulations are known to have severe limitations in such cases, that is, growing too fast or having weak linear programming relaxations. We suggest a relaxation based on partitioning time into so-called time-buckets. This relaxation is iteratively solved and serves as basis for deriving feasible solutions using heuristics. Based on these primal and dual solutions and bounds, the time-buckets are successively refined. Combining these parts, we obtain an algorithm that provides good approximate solutions soon and eventually converges to an optimal solution. Diverse strategies for performing the time-bucket refinement are investigated. The approach shows excellent performance in comparison to the traditional formulations and a metaheuristic.
This paper reports on results for the well-known resource-constrained project scheduling problem. A branch-and-bound procedure is developed that takes into account all best performing components from literature, varyi...
详细信息
This paper reports on results for the well-known resource-constrained project scheduling problem. A branch-and-bound procedure is developed that takes into account all best performing components from literature, varying branching schemes and search strategies, using the best performing dominance rules and assembling these components into a unified search algorithm. A composite lower bound strategy that statically and dynamically selects the best performing bounds from literature is used to find optimal solutions within reasonable times. An extensive computational experiment is set up to determine the best combination of the various components used in the procedure, in order to benchmark the current existing knowledge on four different datasets from the literature. By varying the network topology, resource scarceness and the size of the projects, the computational experiments are carried out on a diverse set of projects. The procedure was able to find some new lower bounds and optimal solutions for the PSPLIB instances. Moreover, new best known results are reported for other, more diverse datasets that can be used in future research studies. The experiments revealed that even project instances with 30 activities cannot be solved to optimality when the topological structure is varied. (C) 2018 Elsevier Ltd. All rights reserved.
For non-preemptive scheduling, time-indexed zero-one linear programming formulations have been deeply analyzed. This note clarifies the current knowledge about the strength of these formulations and shows that some fo...
详细信息
For non-preemptive scheduling, time-indexed zero-one linear programming formulations have been deeply analyzed. This note clarifies the current knowledge about the strength of these formulations and shows that some formulations that have been proposed "new" in the literature are in fact weaker or equivalent to those already known. Much of the arguments used follow from a Ph.D. thesis by Sousa, which has been largely overlooked in the literature. (C) 2017 Elsevier B.V. All rights reserved.
The key question addressed by the resource-constrained project scheduling problem (RCPSP) is to determine the start times for each activity such that precedence and resource constraints are satisfied while achieving s...
详细信息
The key question addressed by the resource-constrained project scheduling problem (RCPSP) is to determine the start times for each activity such that precedence and resource constraints are satisfied while achieving some objective. Priority rule-based heuristics are widely used for large problems. Rollout and justification can be integrated with priority rule heuristics to solve the RCPSP. We develop several such procedures and examine the resulting solution quality and computational cost. We present empirical evidence that these procedures are competitive with the best solution procedures described in the literature. (C) 2007 Elsevier Ltd. All rights reserved.
Most of the real life scheduling problems include several constraints in addition to the precedence and resource constraints considered in the resource-constrained project scheduling problem (RCPSP). In this paper, we...
详细信息
Most of the real life scheduling problems include several constraints in addition to the precedence and resource constraints considered in the resource-constrained project scheduling problem (RCPSP). In this paper, we define a generalization of the (RCPSP) with a wide class of additional constraints, including (but not limited to): a pair of activities must be separated by at least a given duration;a subset of activities cannot be processed simultaneously;an activity cannot start before a particular period;an activity cannot be scheduled in a particular time window;there are resource constraints with varying required and available quantities. We show that for this generalization the activity list and the activity set list representations can be used as efficiently as in the (RCPSP) and that by using these representations the optimal Solution can always be reached. This allows most of the known solution procedures for (RCPSP) based on these representations to be extended for the generalized (RCPSP) by simply replacing the classical decoding procedure used for the (RCPSP) with the generalized version introduced here. (C) 2008 Elsevier B.V. All rights reserved.
A new multiple decision-maker model using bi-level programming is proposed for a resource-constrained project scheduling problem in a fuzzy random environment. In the model, activity duration is assumed to be a fuzzy ...
详细信息
A new multiple decision-maker model using bi-level programming is proposed for a resource-constrained project scheduling problem in a fuzzy random environment. In the model, activity duration is assumed to be a fuzzy random variable because of the complex uncertainties in projectscheduling problems. The project owner, who is the upper-level decision maker, seeks to maximize profits whereas the lower-level contractor attempts to minimize cost. A global-local-neighbor particle swarm optimization with a fuzzy random simulation is then proposed to solve the advanced model. Finally, a sub-project of Nuozhadu Hydropower Station Construction project in China is used to illustrate an application of the developed model. A comparison with other approaches is made and the generated results validate the viability and effectiveness of the proposed model and method.
This paper addresses an extension of the resource-constrained project scheduling problem that takes into account storage resources which may be produced or consumed by activities. To solve this problem, we propose the...
详细信息
This paper addresses an extension of the resource-constrained project scheduling problem that takes into account storage resources which may be produced or consumed by activities. To solve this problem, we propose the generalization of two existing mixed integer linear programming models for the classical resource-constrained project scheduling problem, as well as one novel formulation based on the concept of event. Computational results are reported to compare these formulations with each other, as well as with a reference method from the literature. Conclusions are drawn on the merits and drawbacks of each model according to the instance characteristics.
In this paper strategies for the A-Team with Reinforcement Learning (RL) for solving the resourceconstrainedprojectscheduling Problem (RCPSP) are proposed and experimentally validated. The RCPSP belongs to the NP-h...
详细信息
In this paper strategies for the A-Team with Reinforcement Learning (RL) for solving the resourceconstrainedprojectscheduling Problem (RCPSP) are proposed and experimentally validated. The RCPSP belongs to the NP-hard problem class. To solve this problem a team of asynchronous agents (A-Team) has been implemented using the JABAT multiagent system. An A-Team is the set of objects including multiple agents and the common memory which through interactions produce solutions of optimization problems. These interactions are usually managed by a static strategy. In this paper the dynamic learning strategies are suggested. The proposed strategies based on reinforcement learning supervising interactions between optimization agents and the common memory. To validate the approach and compare strategies computational experiment has been carried out. (C) 2014 Elsevier B.V. All rights reserved.
A common problem which arises in project management is the fact that the planned schedule is often disrupted by several uncontrollable factors like additional time that might be required for rework and correction of d...
详细信息
A common problem which arises in project management is the fact that the planned schedule is often disrupted by several uncontrollable factors like additional time that might be required for rework and correction of detected defects. As a result, project managers are often unable to meet the promised completion dates. It is therefore vital to take into account such possible disruptions and their potential negative consequences at the project schedule design stage. In this paper, we address the issue of designing a project schedule which is not only short in time, but also less vulnerable to disruptions due to reworks and other undesirable conditions. To that aim, we introduce the concept of schedule robustness and we develop a bi-objective resource-constrained project scheduling model. We consider the objectives of robustness maximization along with makespan minimization. We develop a tabu search algorithm in order to generate an approximate set of efficient solutions. Several variants of the algorithm are tested and compared on a large set of benchmark problems. (c) 2004 Elsevier B.V. All rights reserved.
暂无评论