Skip to main content
SpringerLink
Log in

Fast Computational Procedure for Solving Multi-Item Single-Machine Lot Scheduling Optimization Problems

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

In this paper, we deal with the numerical solution of the optimal scheduling problem in a multi-item single machine. We develop a method of discretization and a computational procedure which allows us to compute the solution in a short time and with a precision of order k, where k is the discretization size. In our method, the nodes of the triangulation mesh are joined by segments of trajectories of the original system. This special feature allows us to obtain precision of order k, which is in general impossible to achieve by usual methods. Also, we develop a highly efficient algorithm which converges in a finite number of steps.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Gonzalez, R. L. V., Muramatsu, K., and Rofman, E., Quasi-Variational Inequality Approach to Multi-Item Single-Machine Lot Scheduling Problems, Rapport de Recherche 2057, INRIA, Rocquencourt, France, 1993.

    Google Scholar 

  2. Capuzzo Dolcetta, I., and Evans, L. C., Optimal Switching for Ordinary Differential Equations, SIAM Journal on Control and Optimization, Vol. 22, pp. 143–161, 1984

    Google Scholar 

  3. Gonzalez, R. L. V., and Rofman, E., Sur des Solutions non Bornées de l'Equation de Bellman Associée aux Problèmes de Commutation Optimale avec Contraints sur l'Etât, Comptes Rendus de l'Académie des Sciences de Paris, Serie I, Vol. 316, pp. 1193–1198, 1993.

    Google Scholar 

  4. Gonzalez, R. L. V., and Rofman, E., On Unbounded Solutions of Bellman's Equation Associated to Optimal Switching Control Problems with State Constraints, Journal of Applied Mathematics and Optimization, Vol. 31, pp. 1–17, 1995,.

    Google Scholar 

  5. Gonzalez, R. L. V., Muramatsu, K., and Rofman, E., Quasi-Variational Inequality Approach to Multi-Item Single-Machine Lot Scheduling Problems, Lecture Notes in Control and Information Sciences, Springer Verlag, New York, New York, Vol. 280, pp. 885–893, 1992.

    Google Scholar 

  6. Fleming, W. H., and Rishel, R. W., Deterministic and Stochastic Optimal Control, Springer Verlag, New York, New York, 1975.

    Google Scholar 

  7. Capuzzo Dolcetta, I., and Lions, P. L., Hamilton-Jacobi Equations with State Constraints, Transactions of the American Mathematical Society, Vol. 318, pp. 643–683, 1990

    Google Scholar 

  8. Soner, H. M., Optimal Control Problems with State Space Constraint, I, SIAM Journal on Control and Optimization, Vol. 24, pp. 551–561, 1987.

    Google Scholar 

  9. Friedman, A., Differential Games, Wiley-Interscience, New York, New York, 1971.

    Google Scholar 

  10. Capuzzo Dolcetta, I., and Ishii, H., Approximate Solution of the Bellman Equation of Deterministic Control Theory, Journal of Applied Mathematics and Optimization, Vol. 11, pp. 161–181, 1984

    Google Scholar 

  11. Kushner, H. J., and Dupuis, F., Numerical Methods for Stochastic Control Problems in Continuous Time, Springer Verlag, New York, New York, 1992.

    Google Scholar 

  12. Hanouzet, B., and Joly, J. L., Convergence Uniforme des Iterés Definissant la Solution d'une Inéquation Quasi-Variationelle Abstracte, Comptes Rendus de l'Académie des Sciences de Paris, Serie A, Vol. 286, pp. 735–738, 1978.

    Google Scholar 

  13. Gonzalez, R. L. V., and Rofman, E., On Deterministic Control Problems: An Approximation Procedure for the Optimal Cost, Parts 1–2, SIAM Journal on Control and Optimization, Vol 23, pp. 242–285, 1985.

    Google Scholar 

  14. Gonzalez, R. L. V., and Tidball, M. M., Sur l'Ordre de Convergence des Solutions Discrétisées en Temps et en Espace de l'Equation de Hamilton-Jacobi, Comptes Rendus de l'Académie des Sciences de Paris, Serie I, Vol. 314, pp. 479–482, 1992.

    Google Scholar 

  15. Menaldi, J. L., Some Estimates for Finite Difference Approximations, SIAM Journal on Control and Optimization, Vol. 27, pp. 579–607, 1989.

    Google Scholar 

  16. Souganidis, P. E., Approximation Schemes for Viscosity Solutions of Hamilton-Jacobi Equations, Journal of Differential Equations, Vol. 59, pp. 1–43, 1985.

    Google Scholar 

  17. Ciarlet, P. G., Discrete Maximum Principle for Finite-Difference Operators, Aequationes Mathematicae, Vol. 4, pp. 338–352, 1970.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemática, Facultad de Ciencias Exactas, Ingeniería y Agrimensura, Universidad Nacional de Rosario, Rosario, Argentina

    L. S. Aragone

  2. Deparamento de Matemática, Facultad de Ciencias Exactas, Ingeniería y Agrimensura, Universidad Nacional de Rosario, Rosario, Argentina

    R. L. V. Gonzalez

Authors
  1. L. S. Aragone
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. L. V. Gonzalez
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aragone, L.S., Gonzalez, R.L.V. Fast Computational Procedure for Solving Multi-Item Single-Machine Lot Scheduling Optimization Problems. Journal of Optimization Theory and Applications 93, 491–515 (1997). https://doi.org/10.1023/A:1022682711077

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022682711077

Search

Navigation