Non-Serial Dynamic Programming — A Survey

Abstract

Interest in non-serial dynamic programming is deeply rooted in real life applications. Since the initial efforts in the early 1960's, however, a number of scattered treatments of this interesting field of dynamic programming has emerged. This paper traces the development of non-serial dynamic programming from the basic theory underlying dynamic programming to the latest applications of non-serial dynamic programming. The works of such major contributors as Nemhauser, Wilde, Beightler, Bertele and Brioschi are critically examined and recent relevant computational advances are discussed. The paper is concluded with a few examples of various applications of non-serial dynamic programming together with some crystal ball gazing into future applications. An extensive list of references is also included.