From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective

References

• Anderson E. J., Nash P.Linear Programming in Infinite-Dimensional Spaces (1987) (John Wiley and Sons, New York) Google Scholar
• Atkins D., Chen H. Performance evaluation of scheduling control of queueing networks: Fluid model heuristics. Queueing Systems Appl. (1995) 21:391–413Crossref, Google Scholar
• Avram F., Bertsimas D., Ricard M., Kelly F. p., Williams R. J. Fluid models of sequencing problems in open queueing networks: An optimal control approach. Stochastic Networks. Proc. Internat. Math. Assoc. (1995) 71(Springer-Verlag, New York) 199–234Crossref, Google Scholar
• Bertsimas D., Gamarnik D. Asymptotically optimal algorithms for job shop scheduling and packet routing. J. Algorithms (1999) 33(2):296–318Crossref, Google Scholar
• Bertsimas D., Sethuraman J. From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective. Math. Programming (2002) 92(1):61–102Crossref, Google Scholar
• Chen H., Yao D. Dynamic scheduling of a multiclass fluid network. Oper. Res. (1993) 41(6):1104–1115Link, Google Scholar
• Dai J. G. On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. (1995) 5:49–77Crossref, Google Scholar
• Dai J. G., Weiss G. A fluid heuristic for minimizing makespan in job shops. Oper. Res. (2002) 50(4):692–707Link, Google Scholar
• Eng D., Humphrey J., Meyn S. P. Fluid network models: Linear programs for control and performance bounds. 13th World Congress Intern. Fed. Automatic Control (1996) San Francisco, CACrossref, Google Scholar
• Hall L., Hochbaum D. Approximation algorithms for scheduling. Approximation Algorithms for Np-Hard Problems. (1997) (PWS Publishing Company, Boston, MA) Google Scholar
• Hall L., Schulz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 22(3):513–544Link, Google Scholar
• Harrison J. M., Kelly F. P., Zachary S., Ziedins I. The bigstep approach to flow management in stochastic processing networks. Stochastic Networks: Theory and Applications (1996) (Clarendon Press, Oxford, U.K.) 57–90Crossref, Google Scholar
• Hoogeveen H., Schuurman P., Woeginger G., Bixby R. E., Boyd E. A., Rios-Mercado R. Z. Non-approximability results for scheduling problems with minsum criteria. Integer Programming and Combinatorial Optimization (IPCO-VI Proceedings) (1998) 1412(Springer-Verlag, New York) 353–366Lecture Notes in Computer ScienceCrossref, Google Scholar
• Karger D., Stein C., Wein J., Atallah M. J. Scheduling algorithms. Algorithms and Theory of Computation Handbook (1999) (CRC Press, Boca Raton, FL) Google Scholar
• Luo X., Bertsimas D. A new algorithm for state-constrained separated continuous linear programs. SIAM J. Control Optim. (1999) 37(1):177–210Crossref, Google Scholar
• Maglaras C. Discrete-review policies for scheduling stochastic networks: Trajectory tracking and fluid-scale asymptotic optimality. Ann. Appl. Probab. (2000) 10(3):897–929Crossref, Google Scholar
• Meyn S. P. The policy improvement algorithm for Markov decision processes with general state space. IEEE Trans. Automatic Control (1997a) 42(12):1663–1680Crossref, Google Scholar
• Meyn S. P., Yin G. G., Zhang Q. Stability and optimization of queueing networks and their fluid models. Mathematics of Stochastic Manufacturing Systems. Lectures in Appl. Math. (1997b) 33(American Mathematical Society, Providence, RI) 175–200Google Scholar
• Pullan M. C. An algorithm for a class of continuous linear programs. SIAM J. Control Optim. (1993) 31(6):1558–1577Crossref, Google Scholar
• Queyranne M., Sviridenko M. Approximation algorithms for shop scheduling problems with minsum criteria. (1999) . Technical report, Faculty of Commerce, University of British Columbia, Vancouver, British Columbia, CanadaGoogle Scholar
• Rybko A. N., Stolyar A. L. Ergodicity of stochastic processes describing the operations of open queueing networks. Problems Inform. Transmission (1992) 28:199–220Google Scholar