A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract). (English) Zbl 1345.68027
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 418-427 (1999).
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68W25 | Approximation algorithms |
Citations:
Zbl 0831.68006References:
| [1] | A. K. AMOURA, E. BAMPIS, C. KENYON, AND Y. MANOUSSAKIS, Scheduling independent multiprocessor tasks, Proc. 5th Ann. European Symposium on Algorithms, Lecture Notes in Computer Science 1 8Z, (1997), pp. 1-12. · Zbl 1477.68043 |
| [2] | S. ARORA, C. LUND, R. MOTWANI, M. SUDAN, AND M. SZEGEDY, Proof verification and the hardness of approximation problems, Journal of A CM g 5, (1998), pp. 501-555. 10.1145/278298.278306 · Zbl 1065.68570 |
| [3] | L. BIANCO, J. BLAZEWICZ, P. DELL’OLMO, AND M. DROZDOWSKI, Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors, Annals of Operations Research 58, (1995), pp. 493-517. · Zbl 0836.90092 |
| [4] | J. BLAZEWICZ, P. DELL’OLMO, M. DROZ- DOWSKI, AND M. SPERANZA, Scheduling multiprocessor tasks on the three dedicated processors, Information Processing Letters 1, (1992), pp. 275- 280. 10.1016/0020-0190(92)90172-R · Zbl 0776.68023 |
| [5] | J. BLAZEWICZ, P. DELL’OLMO, M. D tOZ- DOWSKI, AND M. SPERANZA, Corrigendum to “Scheduling multiprocessor tasks on the three dedicated processors, Information Processing Letters Jl, (1992), pp. 275-280.” Information Processing Letters 49, (1994), pp. 269-270. 10.1016/0020-0190(92)90172-R · Zbl 0788.68011 |
| [6] | J. BLAZEWICZ, M. DROZDOWSKI, AND J. W .CLA tZ, Scheduling multiprocessor tasks to minimize scheduling length, IEEE 2 ansactions on Computers 35, (1986), pp. 389-393. 10.1109/TC.1986.1676781 · Zbl 0604.68040 |
| [7] | J. BLAZEWICZ, W. DROZDOWSKI, AND J. WECL^gZ, Scheduling multiprocessor tasks - a survey, International Journal of Microcomputer Applications 13, (1994), pp. 89-97. |
| [8] | L. COMTST, Advanced Combinatorics, Ordrecht, Netherlands, Reidel, 1974. · Zbl 0283.05001 |
| [9] | J. CHr AND C.-Y. L ;, General multiprocessot tasks scheduling, Naval Research Logistics 46, (1999), pp. 57-74. · Zbl 0922.90085 |
| [10] | P. DELL’OLMO, M. C,. SPERANZA, ZS. TUZA, Efficiency and effectiveness of normal schedules on three dedicated processors, Discrete Mathematics 164, (1997), pp. 67-79. 10.1016/S0012-365X(97)84781-4 · Zbl 0871.90045 |
| [11] | G. DOBSON AND U. KARMARKAR, Simultaneous resource scheduling to minimize weighted flow times, Operations Research 37, (1989), pp. 592-600. · Zbl 0675.90043 |
| [12] | J. Du AND J. Y.-T. LEUNG, Complexity of scheduling parallel task systems, SIAM J. Disc. Math. , (1989), pp. 473-487. 10.1137/0402042 · Zbl 0676.90029 |
| [13] | M. R. GAa .Y A D D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP- Completeness, Freeman, San Francisco, 1979. · Zbl 0411.68039 |
| [14] | M. X. GOEMANS, An approximation algorithm for scheduling on three dedicated machines, Discrete Applied Mathematics 61, (1995), pp. 49-59. 10.1016/0166-218X(94)00160-F · Zbl 0831.68006 |
| [15] | R. L. GRAHAM, Bounds for certain multiprocessing anomalies, Bell System Technical Journal (5, (1966), pp. 1563-1581. · Zbl 0168.40703 |
| [16] | R. L. GRAHAM, D. E. K UV , AND O. PATASH- NIK, Concrete Mathematics, Addison-Wesley, Reading, MA, 1994. · Zbl 0836.00001 |
| [17] | L. A. HALL, Approximation algorithms for scheduling, in D. S. HOCHBAUM, ed., Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997, pp. 1-45. |
| [18] | J. A. HOOGEVEEN, S. L. VAN DE VELDE, AND B. VELTMAN, Complexity of scheduling multiprocessor tasks with prespecified processor allocations, Discrete Applied Mathematics 55, (1994), pp. 259- 272. 10.1016/0166-218X(94)90012-4 · Zbl 0938.68671 |
| [19] | O. H. IBARRA AND C. F’,. KIM, Fast approximation algorithms for the Knapsack and sum of subset problems, J. Assoc. Comput. Mach. , (1975), pp. 463-468. 10.1145/321906.321909 · Zbl 0345.90049 |
| [20] | K. JANSEN ANO L. PORKOLAB, Linear-time approximation schemes for scheduling malleabel parallel tasks, Proc. lOth A CM-SIAM Symp. on Discrete Algorithms, (1999). · Zbl 0944.90028 |
| [21] | K. JANSEN AND L. PORKOLAB, private communication, (1999). |
| [22] | H. KRAWCZYK AND M. KUBALE, An approximation algorithm for diagnostic test scheduling in multicomputer systems, IEEE Transactions on Computers 3j, (1985), pp. 869-872. 10.1109/TC.1985.1676647 |
| [23] | C.-Y. LEt A D X. CAI, Scheduling multiprocessor tasks without prespecified processor allocations, Manuscript, (1996). |
| [24] | C.-Y. L .E, L. Lrl, /t l) M. PINEDO, Current trends in deterministic scheduling, Annals of Operations Research 70, (1997), pp. 1-42. |
| [25] | A. MIRANDA, Approximation algorithms in multiprocessor task scheduling, Ph.D. thesis, Dept. Computer Science, Texas A&M University, 1998. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
