- 1 BLUM, M , FLOYD, R W, PgATT, V R, RIVEST, R L, AND TARJAN, R E. T~me bounds for selection J Comptr Syst Sct 7, 4 (1972), 448-461Google Scholar
- 2 COFFMAN, E G JR Computer and Job Shop Scheduhng Theory Wdey, New York, 1976Google Scholar
- 3 GONZALEZ, T, IBARRA, O.H , AND SAHNI, S Bounds for LPT schedules on uniform processors SIAM J Comptng 5, 1 (1977), 155-166Google Scholar
- 4 HoRowxTz, E. AND SAI~N~, S Fundamentals of Data Structures Computer Science Press. Woodland Hills, Cahf, 1976Google Scholar
- 5 HOROWITZ, E , AND SAHNI, S Exact and approximate algorithms for scheduhng nonident,cal processors J ACM 23, 2 (Aprd 1976), 317-327 Google Scholar
- 6 HoavaT8, E C, LAM, S, AND SETHI, R A level algorithm for preemptive scheduling.I. ACM 24, 1 (Jan 1977), 32-43 Google Scholar
- 7 KARP, R M Reduclbdlty among combinatorial problems In Complextty of Computer Computations, R E Mdler and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103.Google Scholar
- 8 LIu, J W S, AND LIu, C L Bounds on scheduhng algorithms for heterogeneous computing systems Information Processing 74, North-Holland Pub Co, Amsterdam, 1974, pp 349-353.Google Scholar
- 9 L~u, J W S, AND YANG, A Optimal scheduhng of independent tasks on heterogeneous computing systems Proc ACM Annual Conf, San Diego, Cahf, Nov 1974, pp 38-45 Google Scholar
- 10 McNAUGHTON, R Scheduhng w,th deadhnes and loss functions Manage Scl 6 (1959), 1-12Google Scholar
- 11 MUNTZ, R R, AND COFFMAr~, E.G Preemptive scheduhng of real time tasks on multtprocessor systems J ACM 17, 2 (Aprd 1970), 324-338 Google Scholar
Index Terms
- Preemptive Scheduling of Uniform Processor Systems
Recommendations
Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs
<P>Suppose that n jobs, each with a specified processing requirement and due date, are to be preemptively scheduled for processing by a number of parallel machines, with the objective of maximizing the number of jobs that are completed by their due ...
Preemptive and non-preemptive scheduling on two unrelated parallel machines
AbstractIn this paper, for the problem of minimizing the makespan on two unrelated parallel machines we compare the quality of preemptive and non-preemptive schedules. It is known that there exists an optimal preemptive schedule with at most two ...
Preemptive stochastic online scheduling on two uniform machines
This paper addresses a stochastic online scheduling problem in which a set of independent jobs are to be processed by two uniform machines whose speeds are 1 and s(s>=1). Each job has a processing time, which is a random variable with an arbitrary ...
Comments