Approximately optimal control of fluid networks

ABSTRACT

We give an approximation algorithm for the optimal control problem in fluid networks. Such problems arise as fluid relaxations of multiclass queueing networks, and are used to find approximate solutions to complex job shop scheduling problems. In a network with linear flow costs and linear, per-unit-time holding costs, our algorithm finds a drainage of the network, that for given constants ε > 0 and δ > 0 has total cost (1 + ε)OPT + δ, where OPT is the cost of the minimum cost drainage. The complexity of our algorithm is polynomial in the size of the input network, 1/ε and log 1/δ. The fluid relaxation is a continuous problem. While the problem is known to have a piecewise constant solution, it is not known to have a polynomially-sized solution. We introduce a natural discretization of polynomial size and prove that this discretization produces a solution with low cost. This is the first polynomial time algorithm with a provable approximation guarantee for fluid relaxations.

REFERENCES

• 1: E. J. Anderson. A continuous model for job-shop scheduling. PhD thesis, University of Cambridge, 1978.
• 2: E. J. Anderson and P. Nash. Linear Programming in Infinite-Dimensional Spaces. John Wiley & Sons, New York, 1987.
• 3: E. J. Anderson, P. Nash, and A. F. Perold. Some properties of a class of continuous linear programs. SIAM J. Control and Optimization, 21:758--765, 1983.
• 4: F. Avram, D. Bertsimas, and M. Ricard. Fluid models of sequencing problems in open queueing networks: an optimal control approach. In F. P. Kelly and R. J. Williams, editors, Stochastic Networks, volume 71 of Proceedings of the International Mathematics Association, pages 199--234. Springer-Verlag, New York, 1995.
• 5: F. Avram, D. Bertsimas, and J. Sethuraman. Optimal control of fluid tandem networks. Manuscript in preparation, 2002.
• 6: N. Bauerle. Asymptotic optimality of tracking policies in stochastic networks. Annals of Applied Probability, 10(4): 1065--1083, 2000.
• 7: R. Bellman. Bottleneck problem and dynamic programming. Proc. Nat. Acad. Sci., 39:947--951, 1953.
• 8: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 9: Dimitris Bertsimas , David Gamarnik , Jay Sethuraman, From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective, Operations Research, v.51 n.5, p.798-813, September 2003 [doi>10.1287/opre.51.5.798.16748]
• 10: D. Bertsimas and J. Sethuraman. From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective. Mathematical Programming, 92(1):61--102, 2002.
• 11: Hong Chen , Avi Mandelbaum, Discrete flow networks: bottleneck analysis and fluid approximations, Mathematics of Operations Research, v.16 n.2, p.408-446, May 1991
• 12: H. Chen and A. Mandelbaum. Hierarchical modeling of stochastic networks, part i: fluid models. In D. D. Yao, editor, Stochastic Modeling and Analysis of Manufacturing Systems, pages 47--105, New York, NY, 1994. Springer-Verlag.
• 13: H. Chen and D. D. Yao. Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer-Verlag, New York, 2001.
• 14: J. G. Dai , Gideon Weiss, A Fluid Heuristic for Minimizing Makespan in Job Shops, Operations Research, v.50 n.4, p.692-707, July 2002 [doi>10.1287/opre.50.4.692.2860]
• 15: J. Filipiak. Modelling and Control of Dynamic Flows in Communication Networks. Springer Verlag, Berlin, 1988.
• 16: Lisa K. Fleischer, Faster Algorithms for the Quickest Transshipment Problem, SIAM Journal on Optimization, v.12 n.1, p.18-35, 2001 [doi>10.1137/S1052623497327295]
• 17: Lisa Fleischer , Martin Skutella, The Quickest Multicommodity Flow Problem, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.36-53, May 27-29, 2002
• 18: M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169--197, 1981.
• 19: B. Hajek and R. G. Ogier. Optimal dynamic routing in communication networks with continuous traffic. Networks, 14:457--487, 1984.
• 20: J. M. Harrison. Brownian motion and stochastic flow systems. John Wiley & Sons, 1985.
• 21: J. M. Harrison. Brownian models of queueing networks with heterogenous customer populations. In W. Fleming and P. L. Lions, editors, Stochastic Differential Systems, Stochastic Control Theory and Applications, Proceedings of the International Mathematics Association, pages 147--186. Springer-Verlag, 1988.
• 22: J. M. Harrison. The bigstep approach to flow management in stochastic processing networks. In E. P. Kelly, S. Zachary, and I. Ziedins, editors, Stochastic Networks: Theory and Applications, pages 57--90. Oxford University Press, 1996.
• 23: Bruce Hoppe , Éva Tardos, Polynomial time algorithms for some evacuation problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.433-441, January 23-25, 1994, Arlington, Virginia, United States
• 24: Xiaodong Luo , Dimitris Bertsimas, A New Algorithm for State-Constrained Separated Continuous Linear Programs, SIAM Journal on Control and Optimization, v.37 n.1, p.177-210, Jan. 1999 [doi>10.1137/S0363012995292664]
• 25: C. Maglaras. Dynamic Control of Stochastic Processing Networks: A Fluid Model Approach. PhD thesis, Stanford University, August 1998.
• 26: C. Maglaras. Discrete-review policies for scheduling stochas- tic networks: Trajectory tracking and fluid-scale asymptotic optimality. Annals of Applied Probability, 10(3):897--929, 2000.
• 27: S. P. Meyn. Stability and optimization of queueing networks and their fluid models. In G. G. Yin and Q. Zhang, editors, Mathematics of Stochastic Manufacturing Systems, volume 33 of Lectures in Applied Mathematics, pages 175--200. American Mathematical Society, 1997.
• 28: A. B. Philpott and M. Craddock. An adaptive discretization algorithm for a class of continuous network programs. Networks, 26:1--11, 1995.
• 29: Malcolm C. Pullan, An algorithm for a class of continuous linear programs, SIAM Journal on Control and Optimization, v.31 n.6, p.1558-1577, Nov. 1993 [doi>10.1137/0331073]
• 30: Edward J. Anderson , Andrew B. Philpott, On the Solutions of a Class of Continuous Linear Programs, SIAM Journal on Control and Optimization, v.32 n.5, p.1289-1296, Sept. 1994 [doi>10.1137/S0363012992227216]
• 31: Malcolm C. Pullan, Forms of Optimal Solutions for Separated Continuous Linear Programs, SIAM Journal on Control and Optimization, v.33 n.6, p.1952-1977, Nov. 1995 [doi>10.1137/S0363012993247858]
• 32: Malcolm C. Pullan, A Duality Theory for Separated Continuous Linear Programs, SIAM Journal on Control and Optimization, v.34 n.3, p.931-965, May 1996 [doi>10.1137/S0363012993257507]
• 33: Jayachandran Sethuraman , Dimitris J. Bertsimas, Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations, 1999

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory