Skip to main content
SpringerLink
Log in

Hybrid algorithm for sequencing with bicriteria

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

Abstract

This paper presents a solution algorithm for a single machine scheduling problem with two criteria: total tardiness and total flow time. Theoretical results of precedence properties which are respected by all nondominated schedules are first derived. These precedence properties are then incorporated into a multiple-criteria dynamic programming framework to improve the computational efficiency. Results of the computational experiment and the average behavior (computation time and efficiency) of the algorithm are reported.

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. Baker, K. R.,Introduction to Sequencing and Scheduling, John Wiley and Sons, New York, New York, 1974.

    Google Scholar 

  2. Baker, K. R., andSchrage, L. E.,Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks, Operations Research, Vol. 26, No. 1, 1978.

  3. Conway, R. W., Maxwell, W. L., andMiller, L. W.,Theory of Scheduling, Addison-Wesley Publishing Company, Reading, Massachusetts, 1967.

    Google Scholar 

  4. Emmons, H.,One-Machine Sequencing to Minimize Certain Functions of Job Tardiness, Operations Research, Vol. 17, No. 4, 1969.

  5. Sen, T. T., andAustin, L. M.,An Efficient Algorithm for Minimizing Total Tardiness in the N-Job, One-Machine Sequencing Problem, Texas Tech University, College of Business Administration, Working Paper, 1980.

  6. Srinivasan, V.,A Hybrid Algorithm for the One-Machine Sequencing Problem to Minimize Total Tardiness, Naval Research Logistic Quarterly, Vol. 18, No. 3, 1971.

  7. Yu, P. L., andZeleny, M.,The Set of All Nondominated Solutions in Linear Case and a Multiple Criteria Simplex Method, Journal of Mathematical Analysis and Applications, Vol. 49, No. 2, 1975.

  8. Yu, P. L.,Cone Convexity, Cone Extreme Points, and Nondominated Solutions in Decision Problems with Multiobjectives, Journal of Optimization Theory and Applications, Vol. 14, No. 3, 1974.

  9. Steuer, R. E.,ADBASE: An Adjacent Efficient Basis Algorithm for Solving Vector-Maximum and Interval Weighted-Sums Linear Programming Problem, Journal of Marketing Research, Vol. 12, pp. 454–455, 1975.

    Google Scholar 

  10. Ziont, S., andWallenius, J.,An Interactive Programming Method for Solving the Multiple Criteria Problem, Management Science, Vol. 22, No. 6, 1976.

  11. Zeleny, M.,Linear Multiobjective Programming, Springer-Verlag, New York, New York, 1974.

    Google Scholar 

  12. Lawler, E. L.,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, New York, 1976.

    Google Scholar 

  13. Garey, M. R., andJohnson, D. S.,Computers and Intractability, Freeman, San Francisco, California, 1979.

    Google Scholar 

  14. Held, M., andKarp, R. M.,A Dynamic Programming Approach to Sequencing Problems, SIAM Journal on Applied Mathematics, Vol. 10, No. 1, 1962.

  15. Schrage, L., andBaker, K. R.,Dynamic Programming Solution of Sequencing Problems with Precedence Constraints, Operations Research, Vol. 26, No. 3, 1978.

  16. Lawler, E. L.,On Scheduling Problems with Deferral Costs, Management Science, Vol. 11, pp. 280–288, 1964.

    Google Scholar 

  17. Schild, A., andFredman, I. J.,Scheduling Tasks with Deadlines and Nonlinear Loss Functions, Management Science, Vol. 9, pp. 73–81, 1962.

    Google Scholar 

  18. Krajewski, L., andBradford, J. W.,Resolving Multiple Objectives in Master Production Scheduling, Proceeding of the 9th Annual Conference of American Institute of Decision Sciences, Chicago, Illinois, 1977.

  19. Bergstresser, K., Charnes, A., andYu, P. L.,Generalization of Domination Structures and Nondominated Solutions in Multicriteria Decision Making, Journal of Optimization Theory and Applications, Vol. 18, No. 1, 1976.

  20. Yu, P. L.,Dynamic Programming in Finite-Stage Multicriteria Decision Problems, University of Kansas, School of Business, Working Paper Series, No. 118, 1978.

  21. Yu, P. L., andSeiford, L.,Multistage Decision Problems with Multicriteria, Multiple Criteria Analysis: Operational Methods, Edited by P. Nijkamp and J. Spronk, Gower Publishing Company, London, England, 1981.

    Google Scholar 

  22. Baker, K. R., andMartin, J. B.,An Experimental Comparison of Solution Algorithms for the Simple Machine Tardiness Problem, Naval Research Logistic Quarterly, Vol. 21, No. 1, 1974.

Download references

Author information

Author notes

  1. K. S. Lin (Assistant Professor)

    Present address: Bell Laboratories, Piscataway, New Jersey

Authors and Affiliations

  1. School of Business, University of Kansas, Lawrence, Kansas

    K. S. Lin (Assistant Professor)

Authors
  1. K. S. Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by P. L. Yu

This investigation was supported in part by University of Kansas General Research Allocation No. 3470-20-0038 and the University of Kansas School of Business Research Fund provided by the Fourth National Bank and Trust Company, Wichita. The ideas and opinions expressed herein are solely those of the author. The author especially wants to thank Professor P. L. Yu for valuable comments on an earlier draft of this paper.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lin, K.S. Hybrid algorithm for sequencing with bicriteria. J Optim Theory Appl 39, 105–124 (1983). https://doi.org/10.1007/BF00934608

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00934608

Key Words

Search

Navigation