Title: Improved algorithm using generalised flows for an optimisation problem in a cash flow network

Authors: Akira Nakayama; Pan Li Gang

Addresses: Graduate School of Symbiotic Systems Science, Fukushima University, Fukushima City, 960-1296, Japan ' Manufacturing Enhancement Centre, China Manufacturing Division, Panasonic Corporation of China, Hang Seng Bank Tower, 1000 Lujiazui Ring Road, Pudong New Aear, Shanghai 200120, China

Abstract: We consider a cash-flow optimisation problem for the cash management method proposed by Golden et al. One of the important objectives of a company is to maximise the total cash at the final term in the network, with the constraints that the total cash supply meets the total demand and some money is invested at each term j = 1, 2,...,n, where n is the number of terms run by the company. Golden et al. formulated this as a flow problem with gains or losses in a cash flow network, and they gave an algorithm for finding the optimal flow in the network. This algorithm is not necessarily efficient from a computational complexity point of view. The three main results of this paper are as follows: 1) we propose an efficient algorithm for this optimisation problem; 2) we point out close relations between the optimisation of cash flow and the generalised flow problem with gains or losses; 3) we improve an algorithm that we developed in an earlier study. Our proposed algorithm runs in O(n(min{n, i*})²) time where i* > 0 is an integer calculated from a given instance. The complexity is strongly polynomial, which implies that the computation time depends on only the structure of the underlying graph of the cash flow network. Our algorithm can be directly applied to the cash flow management of a real industry, such as an agricultural business.

Keywords: cash management; cash flow networks; generalised maximum flow; polynomial time algorithm; cash flow optimisation; generalised flows.

DOI: 10.1504/AJMSA.2013.056008

Asian Journal of Management Science and Applications, 2013 Vol.1 No.1, pp.67 - 95

Received: 15 Mar 2013
Accepted: 15 Mar 2013

Published online: 18 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article