Scheduling the construction of value and discount weighted trees for maximum net present value. (March 2020)

• Record Type: Journal Article
• Authors: Grossman, P.A.; Brazil, M.; Rubinstein, J.H.; Thomas, D.A.
• Is Part Of: Computers & operations research. Volume 115(2020)
• Publication Date: 2020-03
• Subjects: Scheduling -- Combinatorial optimization -- Networks -- OR in natural resources; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.10.018
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: An algorithm is sought for visiting the nodes of a binary tree to maximise NPV. Each edge of the tree has an associated value and discount factor. The problem arises in optimising the development of an underground mine. Key properties of the solution are obtained and an algorithm is presented. Abstract: Given a binary rooted tree in which each edge has an associated value and an associated discount factor, the problem addressed here is to determine which nodes should be visited and in what order so as to maximise the net present value calculated from the values and discount factors of the traversed edges. A process for determining which nodes to exclude is identified, some key properties of the solution are established, and an algorithm for generating an optimal sequence of nodes is presented. A key concept is the priority of a sequence of nodes, which is a certain function of the values and discount factors that determines whether the order of adjacent nodes in the sequence should be swapped. The problem was motivated by the need to determine an optimal sequence in which the network of access tunnels in an underground mine should be developed and the resources extracted when there is a limit on the equipment available.