Minimizing total completion time on uniform machines with deadline constraints

ABSTRACT

Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time ∑C_j. In the classical α | β | γ scheduling notation, this problem is referred to as Qm | prmt, &dmacr;_j | ∑C_j. It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.

REFERENCES

• 1: Baker, K. R. 1974. Introduction to Sequencing and Scheduling, Wiley, New York.
• 2: Sartaj Sahni , Yookun Cho, Scheduling Independent Tasks with Due Times on a Uniform Processor System, Journal of the ACM (JACM), v.27 n.3, p.550-563, July 1980 [doi>10.1145/322203.322214]
• 3: Jianzhong Du , Joseph Y.-T. Leung, Minimizing mean flow time with release time and deadline constraints, Journal of Algorithms, v.14 n.1, p.45-68, Jan. 1993 [doi>10.1006/jagm.1993.1003]
• 4: J. Du , J. Y.-I. Leung , G. H. Young, Minimizing mean flow time with release time constraint, Theoretical Computer Science, v.75 n.3, p.347-355, Oct. 1990 [doi>10.1016/0304-3975(90)90100-V]
• 5: A Federgruen , H Groenevelt, Preemptive scheduling of uniform machines by ordinary network flow techniques, Management Science, v.32 n.3, p.341-349, March 1986 [doi>10.1287/mnsc.32.3.341]
• 6: Gonzalez, T. F. 1978. Minimizing the mean and maximum finishing time on uniform processors. Tech. Rep. CS-78-22. Dept. Comput. Sci. The Pennsylvania State University, University Park, PA.
• 7: Teofilo Gonzalez , Sartaj Sahni, Preemptive Scheduling of Uniform Processor Systems, Journal of the ACM (JACM), v.25 n.1, p.92-101, Jan. 1978 [doi>10.1145/322047.322055]
• 8: Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5, 287--326.
• 9: Horvath, E. C., Lam, S., and Sethi, R. 1976. A level algorithm for preemptive scheduling. J. ACM. 23, 317--327.
• 10: Lawler, E. L. 1982. Recent results in the theory of machine scheduling. In Mathematical Programming: The State of the Art. A. Bachem, M. Grotschel, and B. Korte, Eds. Springer-Verlag, Berlin, Germany.
• 11: Lenstra, J. K. 1977. Sequencing by Enumerative Methods. Mathematical Centre Tracts 69, Mathematisch Centrum, Amsterdam, the Netherlands.
• 12: Joseph Y , .-T. Leung , Michael Pinedo, Minimizing Total Completion Time on Parallel Machines with Deadline Constraints, SIAM Journal on Computing, v.32 n.5, p.1370-1388, 2003 [doi>10.1137/S0097539702406388]
• 13: Jane W. S. Liu , Ai-Tsung Yang, Optimal scheduling of independent tasks on heterogeneous computing systems, Proceedings of the 1974 annual conference, p.38-45, January 1974 [doi>10.1145/800182.810377]
• 14: McCormick, S. T., and Pinedo, M. 1995. Scheduling n independent on m uniform machines with both flow time and makespan objectives: A parametric analysis. ORSA J. Comput. 7, 63--77.
• 15: Pinedo, M. 2002. Scheduling: Theory, Algorithms and Systems. Prentice-Hall, Englewood Cliffs, NJ.
• 16: René Sitters, Two NP-Hardness Results for Preemptive Minsum Scheduling of Unrelated Parallel Machines, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.396-405, June 13-15, 2001
• 17: Smith, W. E. 1956. Various optimizers for single-stage production. Nav. Res. Log. Quart. 3, 59--66.

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
Mean flow time, deadline constraints, polynomial-time algorithms, uniform machines