Dynamic Programming Solutions for Precedence Constrained Routing and Scheduling Problems: A Survey

In the department of control systems, precedence-constrained routing problems are studied since the early 2000s. The preferred exact method is a variety of the dynamic programming method developed by A.G. Chentsov and his co-authors (Chentsov, 2008); this method allows to dispense with infeasible task sets thereby increasing the performance and reducing the space requirements. Several methods that bear certain similarity to this one (although neither of them provided for Clustered/Generalized/International TSP or TSP with dependence of costs on the set of pending tasks) were developed in the end of 1970s: (Schrage, Baker, 1978) and (Lawler, 1979).
The talk is devoted to comparison of those three algorithms. One of the reasons for comparative analysis is the probability of applying some of time and space complexity estimates developed the Lawler and Schrage–Baker methods (Steiner, 1990) to the one presently used in our department. Space estimates seem especially important due to dynamic programming implementations being mostly limited by space and not by time.
References:
(Chentsov, 2008) Ченцов, А. Г. (2008). Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва–Ижевск: РХД. [A.G. Chentsov, Extremal routing and scheduling: A Theoretical Treatment]
(Schrage, Baker, 1978) Schrage, Linus, and Kenneth R. Baker. "Dynamic programming solution of sequencing problems with precedence constraints." Operations research 26.3 (1978): 444-449.
(Lawler, 1979) Lawler, E.L. Preemptive scheduling of uniform parallel machines to minimize the weighted number of late jobs : (preprint) 1979 - Stichting Mathematisch Centrum. Mathematische Besliskunde, BW 105/79, p.1–20 [ Technical report ]; see http://oai.cwi.nl/oai/asset/9664/9664A.pdf
(Steiner, 1990) Steiner, George. "On the complexity of dynamic programming for sequencing problems with precedence constraints." Annals of Operations Research 26.1 (1990): 103-123.