A branch and bound algorithm for project scheduling problem with spatial resource constraints
type: Item
instance of: scholarly article
title: A branch and bound algorithm for project scheduling problem with spatial resource constraints
zbMATH Open document ID: 1394.90276
DOI: 10.1155/2015/628259
author: Shicheng Hu
author: Takao Ito
author: Xuedong Sun
author: Song Wang
author: Yonggui Kao
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: With respect to the block assembly schedule in a shipbuilding enterprise, a spatial resource constrained project scheduling problem (SRCPSP) is proposed, which aims to minimize the makespan of a project under the constraints of the availability of a two-dimensional spatial resource and the precedence relationship between tasks. In order to solve SRCPSP to the optimum, a branch and bound algorithm (BB) is developed. For the BB-SRCPSP, first, an implicitly enumerative branch scheme is presented. Secondly, a precedence based lower bound, as well as an effective dominance rule, is employed for pruning. Next, a heuristic based algorithm is used to decide the order of a node to be selected for expansion such that the efficiency of the algorithm is further improved. In addition, a maximal space based arrangement is applied to the configuration of the areas required each day in an available area. Finally, the simulation experiment is conducted to illustrate the effectiveness of the BB-SRCPSP.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90B30
zbMATH DE Number: 6926843
Wikidata QID: Q59119167
describes a project that uses: PSPLIB
describes a project that uses: PROGRESS
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/628259
OpenAlex ID: W2113831660
cites work: A survey of variants and extensions of the resource-constrained project scheduling problem
cites work: A linear programming and constraint propagation-based lower bound for the RCPSP
cites work: Simulated annealing and tabu search for multi-mode project payment scheduling
cites work: Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times
cites work: A self-adapting genetic algorithm for project scheduling under resource constraints
cites work: A neurogenetic approach for the resource-constrained project scheduling problem
cites work: A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling
cites work: PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem
cites work: Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers
cites work: Scheduling projects with stochastic activity duration to maximize expected net present value
cites work: Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints
cites work: Discrete-continuous project scheduling with discounted cash flows - a tabu search approach
cites work: Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties
cites work: Some scheduling problems with general position-dependent and time-dependent learning effects
cites work: The Bin Packing Problem with Precedence Constraints
cites work: PSPLIB -- a project scheduling problem library
description: scientific article; zbMATH DE number 6926843