Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The following job sequencing problems are studied: (i) single processor job sequencing with deadlines, (ii) job sequencing on m-identical processors to minimize finish time and related problems, (iii) job sequencing on 2-identical processors to minimize weighted mean flow time. Dynamic programming type algorithms are presented to obtain optimal solutions to these problems, and three general techniques are presented to obtain approximate solutions for optimization problems solvable in this way. The techniques are applied to the problems above to obtain polynomial time algorithms that generate “good” approximate solutions.

REFERENCES

• 1: J. Bruno , E. G. Coffman, Jr. , R. Sethi, Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, v.17 n.7, p.382-387, July 1974 [doi>10.1145/361011.361064]
• 2: BRUNO, J., COVFMAN, E.G JR, AND SETHX, R. Algorithms for mimmizing mean flow time. Proc IFIP Cong. 1974, North-Holland Pub. Co., Amsterdam, pp 504-510.
• 3: COFFMAN, E.G., AND SETHI, R. Algorithms minimizing mean flow time: Schedule length properties. Comput. Sci. Dep., Pennsylvania State U., University Park, Pa., 1974.
• 4: CoNwAY, R.W, MAXWELL, W.L., AND MILLER, L.W Theory of Scheduling. Addison-Wesley, Reading, Mass, 1967.
• 5: FISHER, M.L. Optimal solution of scheduhng problems using Lagrangian multipliers (revised). Center for Mathematical Studies in Business and Economics Rep, U. of Chicago, Chicago, ill., March 1972
• 6: FISHER, M L OpUmal solution of scheduhng problems using Lagranglan multlphers. Pt. Ii. Presented at the Scheduling Symposium, North Carolina State U , Raleigh, N C., May 15-17, 1972.
• 7: GRAHAM, R.L. Bounds on multlprocessing timing anomahes. SIAM J. Appl. Math. 17, 2 (March 1969), 416-429.
• 8: Ellis Horowitz , Sartaj Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM (JACM), v.21 n.2, p.277-292, April 1974 [doi>10.1145/321812.321823]
• 9: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 10: JACKSON, J R. Scheduling a production line to minimize maximum tardiness Rep No. 43, Manag. Sci. Res Project, U of California, Los Angeles, Callf, July 1955
• 11: jOHNSON, D Approximation algorithms for combinatorial problems J Comput. Syst. Sc~ 9, 3 (Dec. 1974), 256-278
• 12: KARP, R M. Reduclbdity among combinatorial problems. In Complexity of Computer Computations, R.E Miller and J.W. Thatcher, Eds , Plenum Press, New York, 1972, pp. 85-103.
• 13: LAWLV.R, E L, AND MOOSE, J M A functmnal equation and ~ts application to resource allocation and sequenclng problems Manag Sci 16, 1 (Sept. 1969), 77-84
• 14: S~,HNt, S. Some subexpoaentially recognizable NP-complete languages. Computer Scmnce Tech Rep //74-14, U. of Minnesota, Mmneapohs, Minn., 1974.
• 15: SAHNI, S. Computationally related problems SIAM J. Com~ut $, 4 (Dec. 1974), 262-279
• 16: Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]
• 17: SAHNI, S, AND GONZaLr.Z, T. P-Complete problems and apprommate solutions Proc. IEEE 15th Annual Symposium on Switching and Automata Theory, Oct. 1974, 28-32.
• 18: ULLMAN, J.D Polynomial complete scheduling algorithms, j. Comput. Syst. Sc~. 10, ~ (Jan. 1975), 384-393.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Performance, Theory, Verification