A Branch and Bound Algorithm for Project Scheduling Problem with Spatial Resource Constraints

Shicheng Hu, Song Wang, Yonggui Kao, Takao Ito and Xuedong Sun

Mathematical Problems in Engineering, 2015, vol. 2015, 1-9

Abstract:

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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2015/628259.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2015/628259.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:628259

DOI: 10.1155/2015/628259

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().