Yumei Huo
Abstract
We consider the problem of scheduling a set of n unit-execution-time (UET) tasks, with precedence constraints, on m ≥ 1 parallel and identical processors so as to minimize the mean flow time. For two processors, the Coffman--Graham algorithm gives a schedule that simultaneously minimizes the mean flow time and the makespan. The problem becomes strongly NP-hard for an arbitrary number of processors, although the complexity is not known for each fixed m ≥ 3. For arbitrary precedence constraints, we show that the Coffman--Graham algorithm gives a schedule with a worst-case bound no more than 2, and we give examples showing that the bound is tight. For intrees, the problem can be solved in polynomial time for each fixed m ≥ 1, although the complexity is not known for an arbitrary number of processors. We show that Hu's algorithm (which is optimal for the makespan objective) yields a schedule with a worst-case bound no more than 1.5, and we give examples showing that the ratio can approach 1.308999.
- Baptiste, Ph., Brucker, P., Knust, S., and Timkovsky, V. G. 2002. Fourteen notes on equal-processing-time scheduling. OSM Reihe P, Heft 246.Google Scholar
- Brucker, P., Hurink, J., and Knust, S. 2003. A polynomial algorithm for P|pj = 1, rj, outtree| ∑Cj. Math. Meth. Oper. Res. 56, 407--412.Google Scholar
- Coffman, E. G., and Graham, R. L. 1972. Optimal scheduling for two-processor systems. Acta Inf. 1, 200--213.Google Scholar
- Coffman, E. G., Sethuraman, J., and Timkovsky, V. G. 2003. Ideal preemptive schedules on two processors. Acta Inf. 39, 597--612.Google Scholar
- Du, J., Leung, J. Y.-T., and Young, G. H. 1991. Scheduling chain-structured tasks to minimize makespan and mean flow time. Inf. Comput. 92, 219--236. Google Scholar
- Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, CA. Google Scholar
- 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. Disc. Math. 5, 287--326.Google Scholar
- Horn, W. A. 1972. Single-machine job sequencing with treelike precedence ordering and linear delay penalties. SIAM J. Appl. Math. 23, 189--202.Google Scholar
- Hu, T. C. 1961. Parallel sequencing and assembly line problems. Oper. Res. 9, 841--848.Google Scholar
- Lam, S., and Sethi, R. 1977. Worst case analysis of two scheduling algorithms. SIAM J. Comput. 6, 3, 518--536.Google Scholar
- Lawler, E. L. 1978. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Disc. Math. 2, 75--90.Google Scholar
- McNaughton, R. 1959. Scheduling with deadlines and loss functions. Manage. Sci. 6, 1--12.Google Scholar
Index Terms
- Minimizing mean flow time for UET tasks
Recommendations
Online Scheduling of Precedence Constrained Tasks
A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on $m \ge 1$ identical and parallel processors so as to minimize the makespan (schedule length). In the past, research has focused on the ...
Minimizing total completion time on uniform machines with deadline constraints
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 ...
Comments