Teofilo F. Gonzalez
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 ΣCj. In the classical α | β | γ scheduling notation, this problem is referred to as Qm | prmt, d¯j | ΣCj. It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.
- Baker, K. R. 1974. Introduction to Sequencing and Scheduling, Wiley, New York.]]Google Scholar
- Cho, Y., and Sahni, S. 1980. Scheduling independent tasks with due times on a uniform processor system. J. ACM. 20, 550--563.]] Google ScholarDigital Library
- Du, J., and Leung, J. Y.-T. 1993. Minimizing mean flow time with release time and deadline constraints. J. Algor. 14, 45--68.]] Google ScholarDigital Library
- Du, J., Leung, J. Y.-T., and Young, G. H. 1990. Minimizing mean flow time with release time constraint. Theoret. Comput. Sci. 75, 347--355.]] Google ScholarDigital Library
- Federgruen, A., and Groenevelt, H. 1986. Preemptive scheduling of uniform machines by ordinary network flow techniques. Manage. Sci. 32, 341--349.]]Google ScholarDigital Library
- 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.]]Google Scholar
- Gonzalez, T. F., and Sahni, S. 1978. Preemptive scheduling of uniform processor systems. J. ACM. 25, 92--101.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- Horvath, E. C., Lam, S., and Sethi, R. 1976. A level algorithm for preemptive scheduling. J. ACM. 23, 317--327.]]Google Scholar
- 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.]]Google Scholar
- Lenstra, J. K. 1977. Sequencing by Enumerative Methods. Mathematical Centre Tracts 69, Mathematisch Centrum, Amsterdam, the Netherlands.]]Google Scholar
- Leung, J. Y.-T., and Pinedo, M. 2003. Minimizing total completion time with parallel machines with deadline constraints. SIAM J. Comput. 32, 5, 1370--1388.]] Google ScholarDigital Library
- Liu, J. W. S., and Yang, A. 1974. Optimal scheduling of independent tasks on heterogeneous computing systems. In Proceedings of the ACM Annual Conference (San Diego, CA, Nov.). ACM, New York, pp. 38--45.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- Pinedo, M. 2002. Scheduling: Theory, Algorithms and Systems. Prentice-Hall, Englewood Cliffs, NJ.]]Google Scholar
- Sitters, R. A. 2001. Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines. In Proceedings of the 8th International IPCO Conference, Lecture Notes in Computer Science, vol. 2081. Springer-Verlag, New York, pp. 396--405.]] Google ScholarDigital Library
- Smith, W. E. 1956. Various optimizers for single-stage production. Nav. Res. Log. Quart. 3, 59--66.]]Google ScholarCross Ref
Index Terms
- Minimizing total completion time on uniform machines with deadline constraints
Recommendations
Minimizing Total Completion Time on Parallel Machines with Deadline Constraints
Consider n independent jobs and m identical machines in parallel. Job j has a processing time pj and a deadline $\bar{d}_j$. It must complete its processing before or at its deadline. All jobs are available for processing at time t=0 and preemptions are ...
Minimizing Makespan and Preemption Costs on a System of Uniform Machines
It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms, whereas for non-preemptive scheduling there are probably no such algorithms. However, it is not clear how many preemptions (in total, or ...
Total absolute deviation of job completion times on uniform and unrelated machines
Unlike other measures of variation of job completion times considered in scheduling literature, the measure of minimizing total absolute deviation of job completiontimes (TADC) was shown to have a polynomial time solution on a single machine. It was ...
Comments