A state-of-the-art review of parallel-machine scheduling research. (English) Zbl 0707.90053

Cheng, T. C. E.; Sin, C. C. S.

Eur. J. Oper. Res. 47, No. 3, 271-292 (1990).

Summary: The major research results in deterministic parallel-machine scheduling theory will pass a survey. The review reveals that there exist a lot of potential areas worthy of further research.

MSC:

90B35	Deterministic scheduling theory in operations research
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Keywords:

sequencing; classification; deterministic parallel-machine scheduling; survey

References:

[1]	Achugbue, J. O.; Chin, F. Y., Bounds on schedules for independent tasks with similar execution time, Journal of ACM, 28, 81-99 (1981) · Zbl 0453.68005
[2]	Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[3]	Baker, K. R.; Merten, A. G., Scheduling with parallel processors and linear delay costs, Naval Research Logistics Quartery, 20, 793-804 (1973) · Zbl 0273.90030
[4]	Barnes, J. W.; Brennan, J. J., An improved algorithm for scheduling jobs on identical machines, AIIE Transactions, 9, 25-31 (1977)
[5]	Bellman, R.; Esogbue, A. O.; Nabeshima, I., Mathematical Aspects of Scheduling and Applications (1982), Pergamon: Pergamon Oxford · Zbl 0498.90018
[6]	Blazewicz, J.; Finke, G.; Haupt, R.; Schmidt, G., New trends in machine scheduling, European Journal of Operational Research, 37, 303-317 (1988) · Zbl 0652.90058
[7]	Brucker, P.; Garey, M. R.; Johnson, D. S., Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness, Mathematics of Operations Research, 2, 275-284 (1977) · Zbl 0397.90044
[8]	Bruno, L. J.; Coffman, E. G.; Sethi, R., Scheduling independent tasks to reduce mean finishing time, ACM Communications, 17, 382-387 (1974) · Zbl 0283.68039
[9]	Bruno, L. J.; Downey, P. J., Probabilistic bounds for dual bin packing, Acta Informatica, 22, 333-345 (1985) · Zbl 0569.68037
[10]	Chen, N. F.; Liu, C. L., On a class of scheduling algorithm for multi-processor computing systems, (Goos, G.; Hartmanis, J., Parallel Processing, Lecture Notes in Computer Science 24 (1975), Springer: Springer Berlin), 1-16 · Zbl 0317.68056
[11]	Cheng, T. C.E., A heuristic for common due-date assignment and job scheduling on parallel machines, Journal of the Operational Research Society, 40, 1129-1135 (1989) · Zbl 0699.90060
[12]	(Coffman, E. G., Computer and Job Shop Scheduling Theory (1976), Wiley: Wiley New York) · Zbl 0359.90031
[13]	Coffman, E. G., An introduction to proof techniques for bin-packing approximation algorithm, (Dempster, M. A.H.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic and Stochastic Scheduling (1982), D. Reidel Publishing Company: D. Reidel Publishing Company Dordrecht), 245-270 · Zbl 0494.68041
[14]	Coffman, E. G.; Frederickson, G. N.; Lueker, G. S., Probabilistic analysis of the LPT processor scheduling heuristic, (Dempster, M. A.H.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic and Stochastic Scheduling (1982), D. Reidel Publishing Company: D. Reidel Publishing Company Dordrecht), 319-331 · Zbl 0488.68034
[15]	Coffman, E. G.; Frederickson, G. N.; Lueker, G. S., A note on expected makespans for largest-first sequences of independent tasks on two processors, Mathematics of Operations Research, 9, 260-266 (1984) · Zbl 0538.90036
[16]	Coffman, E. G.; Garey, M. R.; Johnson, D. S., An application of bin-packing to multiprocessor scheduling, SIAM Journal of Computing, 7, 1-17 (1978) · Zbl 0374.68032
[17]	Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximate algorithm for bin packing - An updated survey, (Ausiello, G.; Lucertini, M.; Serafini, P., Algorithm Design for Computer System Design (1984), Springer-Verlag: Springer-Verlag Wien), 49-106 · Zbl 0558.68062
[18]	Coffman, E. G.; Gilbert, E. N., On the expected relative performance of list scheduling, Operations Research, 33, 548-561 (1985) · Zbl 0569.90044
[19]	Coffman, E. G.; Graham, R. L., Optimal scheduling for two-processor systems, Acta Informatica, 1, 200-213 (1972) · Zbl 0248.68023
[20]	Coffman, E. G.; Leung, J. Y.T., Combinatorial analysis of an efficient algorithm processor and storage allocation, SIAM Journal of Computing, 8, 202-217 (1979) · Zbl 0417.68022
[21]	Coffman, E. G.; Sethi, R., A generalized bound on LPT sequencing, RAIRO-Informatique, 10, 17-25 (1976) · Zbl 0333.68040
[22]	Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500
[23]	Cook, S. A., The complexity of theorem-provining procedures, (Proceedings of 3rd Annual ACM Symposium on Theory of Computing (1971)), 151-158 · Zbl 0253.68020
[24]	Davida, G. I.; Linton, D. J., A new algorithm for the scheduling of tree structured tasks, (Proceedings of 1976 Conference on Information Sciences and Systems (1976), Johns Hopkins University), 543-548
[25]	De, P.; Morton, T. E., Scheduling to minimum makespan on unequal parallel processors, Decision Science, 11, 586-602 (1980)
[26]	Dempster, M. A.H.; Lenstra, J. K.; Rinnooy Kan, A. H.G., (Deterministic and Stochastic Scheduling (1982), D. Reidel Publishing Company: D. Reidel Publishing Company Dordrecht)
[27]	Deuermeyer, B. L.; Friesen, D. K.; Langston, M. A., Maximizing the minimum processor finish in a multiprocessor system, SIAM Journal of Algorithms and Discrete Mathematics, 3, 190-196 (1982) · Zbl 0489.68031
[28]	Dileepan, P.; Sen, T., Bicriterion static scheduling research for single machine, OMEGA, 16, 53-59 (1988)
[29]	Dobson, G., Scheduling independent tasks on uniform processors, SIAM Journal of Computing, 13, 705-716 (1984) · Zbl 0548.68025
[30]	Dogramaci, A.; Surkis, J., Evaluation of a heuristic for scheduling independent jobs on parallel identical processors, Management Science, 23, 1208-1216 (1979) · Zbl 0465.90046
[31]	Dror, M.; Stern, H. I.; Lenstra, J. K., Parallel machine scheduling: Processing rates dependent on number of jobs in operation, Management Science, 33, 1001-1009 (1987) · Zbl 0636.90044
[32]	Eastman, W. L.; Even, S.; Isaacs, I. M., Bounds for the optimal scheduling of \(n\) jobs on \(m\) processors, Management Science, 11, 268-279 (1964)
[33]	Elmaghraby, S.; Park, S. H., Scheduling jobs on a number of identical machines, AIIE Transactions, 6, 1-13 (1974)
[34]	Finn, G.; Horowitz, E., A linear time approximation algorithm for multiprocessor scheduling, BIT, 19, 312-320 (1979) · Zbl 0413.68038
[35]	French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop (1982), Ellis Horwood: Ellis Horwood Chichester · Zbl 0479.90037
[36]	Frenk, J. B.G.; Rinnooy Kan, A. H.G., The rate of convergence to optimality of the LPT rule, Discrete Applied Mathematics, 14, 187-197 (1986) · Zbl 0611.90058
[37]	Frenk, J. B.G.; Rinnooy Kan, A. H.G., The asymptotic optimality of the LPT rule, Mathematics of Operations Research, 12, 241-254 (1987) · Zbl 0632.90031
[38]	Friesen, D. K., Tighter bounds for the MULTIFIT scheduling algorithm, SIAM Journal of Computing, 13, 170-181 (1984) · Zbl 0539.68024
[39]	Friesen, D. K.; Langston, M. A., Bounds for MULTIFIT scheduling on uniform processors, SIAM Journal of Computing, 12, 60-70 (1983) · Zbl 0514.68048
[40]	Friesen, D. K.; Langston, M. A., Analysis of a compound bin-packing, SIAM Journal of Computing, 18, 82-90 (1989)
[41]	Fujii, M.; Kasami, T.; Ninomiya, K., Optimal sequencing of two equivalent processors, SIAM Journal of Applied Mathematics, 17, 784-789 (1969) · Zbl 0205.48603
[42]	Fujii, M.; Kasami, T.; Ninomiya, K., Optimal sequencing of two equivalent processors - Erratum, SIAM Journal of Applied Mathematics, 20, 141 (1971) · Zbl 0222.90045
[43]	Gabow, H. N., An almost-linear algorithm for two-processor scheduling, Journal of ACM, 29, 766-780 (1982) · Zbl 0485.68034
[44]	Garey, M. R.; Johnson, D. S., Scheduling tasks with nonuniform deadlines on two processors, Journal of ACM, 23, 461-467 (1976) · Zbl 0338.68048
[45]	Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[46]	Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakais, M., Scheduling opposing forests, SIAM Journal of Algorithms and Discrete Mathematics, 4, 72-93 (1983) · Zbl 0507.68021
[47]	Gonzalez, M. J., Deterministic processor scheduling, ACM Survey, 9, 173-204 (1977) · Zbl 0357.68069
[48]	Gonzalez, T.; Johnson, D. B., A new algorithm for preemptive scheduling of trees, Journal of ACM, 27, 287-312 (1980) · Zbl 0446.68026
[49]	Goyal, D. K., Non-preemptive scheduling of unequal executive time tasks on two identical processors, (Technical Report CS-77-039 (1977), Computer Science Department, Washington State University: Computer Science Department, Washington State University Pullman, Washington, DC)
[50]	Graham, R. L., Bounds on certain multiprocessing anomalies, Bell System Technical Journal, 45, 1563-1581 (1966) · Zbl 0168.40703
[51]	Graham, R. L., Bounds on multiprocessing timing anomalies, SIAM Journal of Applied Mathematics, 17, 416-429 (1969) · Zbl 0188.23101
[52]	Graham, R. L., Bound on the performance of scheduling algorithms, (Coffman, E. G., Computer and Job Shop Scheduling Theory (1976), Wiley: Wiley New York), 165-224 · Zbl 0359.90031
[53]	Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A Survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[54]	Gupta, S. K.; Kyparisis, J., Single machine scheduling research, OMEGA, 15, 207-227 (1987)
[55]	Hochbaum, D. S.; Shmoys, D. B., Using dual approximation algorithms for scheduling problems: theoretical and practical results, Journal of ACM, 34, 144-162 (1987)
[56]	Horn, W. A., Minimizing average flow time with parallel machines, Operations Research, 21, 846-847 (1973) · Zbl 0259.90030
[57]	Horn, W. A., Some simple scheduling algorithms, Naval Research Logistics Quarterly, 21, 177-185 (1974) · Zbl 0276.90024
[58]	Horvath, E. C.; Lam, S.; Sethi, R., Algorithm for preemptive scheduling, Journal of ACM, 24, 32-43 (1977) · Zbl 0354.90044
[59]	Hu, T. C., Parallel sequencing and assembly line problems, Operations Research, 9, 841-848 (1961)
[60]	Ibarra, O. H.; Kim, C. E., On two-processor scheduling of one- or two-unit time tasks with precedence constraints, Journal of Cybernetics, 5, 87-109 (1976) · Zbl 0332.68043
[61]	Johnson, D. S., Fast allocation algorithms, (Proceedings of 13th Annual IEEE Symposium on Switching and Automata Theory (1972)), 144-154
[62]	Johnson, D. S., Near optimal bin-packing algorithm, (Ph.D. Dissertation (1973), Electrical Engineering Department, Massachusetts Institute of Technology)
[63]	Kao, T. Y.; Elsayed, E. A., Performance of the LPT algorithm in multiprocessor scheduling, (IE working paper (1988), Rutgers University: Rutgers University NJ), 88-109
[64]	Karmarkar, N.; Karp, R. M., The differencing method of set partitioning (1982), Computer Sciences Div., University of California: Computer Sciences Div., University of California Berkeley, CA
[65]	Kariv, O., An \(O(n2.5)\) algorithm for finding a maximum matching in a general graph, (Ph.D. Dissertation (1976), Weizmann Institute of Science: Weizmann Institute of Science Rehovot)
[66]	Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[67]	Karp, R. M., On the computational complexity of combinatorial problems, Networks, 5, 45-68 (1975) · Zbl 0324.05003
[68]	Karp, R. M., The fast approximate solution of hard combinatorial problems, (Proceedings of 6th South Eastern Conference on Combinations, Graph, Theory and Computing (1975), Utilitas Mathematica Publishing Co: Utilitas Mathematica Publishing Co Winnipeg), 15-34 · Zbl 0369.05049
[69]	Kaufman, M. T., An almost-optimal algorithm for the assembly line scheduling problem, IEEE Transactions on Computing, c-23, 1169-1174 (1974) · Zbl 0288.68026
[70]	Kim, Y., On the superiority of a backward approach in list scheduling algorithms for multi-machine makespan problem, International Journal of Production Research, 25, 1751-1759 (1987)
[71]	Krause, K. L.; Shen, Y. Y.; Schwetman, H. D., Analysis of several task-scheduling algorithms for a model of multi-programming computer systems, Journal of ACM, 22, 522-550 (1975) · Zbl 0329.68056
[72]	Kunde, M., Nonpreemptive LP-scheduling on homogeneous multiprocessor system, SIAM Journal of Computing, 10, 151-173 (1981) · Zbl 0454.68015
[73]	Lam, S.; Sethi, R., Worst case analysis of two scheduling algorithms, SIAM Journal of Computing, 6, 518-536 (1977) · Zbl 0374.90031
[74]	Langston, M. A., Improved LPT scheduling for identical processor systems, RAIRO Technique et Science Informatique, 1, 69-75 (1982) · Zbl 0483.68036
[75]	Lawler, E. L., On scheduling problems with deferral costs, Management Science, 11, 280-288 (1964)
[76]	Lawler, E. L.; Labetoulle, J., On preemptive scheduling on unrelated and parallel processors by linear programming, Journal of ACM, 25, 612-619 (1978) · Zbl 0388.68027
[77]	Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Recent developments in deterministic sequencing and scheduling: A survey, (Dempster, M. A.H.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic and Stochastic Scheduling (1982), D. Reidel Publishing Company: D. Reidel Publishing Company Dordrecht), 35-74 · Zbl 0482.68035
[78]	Lawler, E. L.; Moore, J. M., A functional equation and its application to resource allocation and sequencing problem, Management Science, 16, 77-84 (1969) · Zbl 0184.23303
[79]	Lenstra, J. K., Sequencing by Enumeration Methods (1977), Mathematisch Centrum: Mathematisch Centrum Amsterdam · Zbl 0407.90025
[80]	Lenstra, J. K.; Rinnooy Kan, A. H.G., Computational complexity of discrete optimization, (Lenstra, J. K.; Rinnooy Kan, A. H.G.; Van Emde Boas, P., Interfaces Between Computer Science and Operations Research, Proceedings of a Symposium held at the Mathematisch Centrum. Interfaces Between Computer Science and Operations Research, Proceedings of a Symposium held at the Mathematisch Centrum, Amsterdam (1979), Mathematisch Centrum), 64-85 · Zbl 0387.90079
[81]	Lenstra, J. K.; Rinnooy Kan, A. H.G., An introduction to multiprocessor scheduling, Consiglio Nazionale della Ricerche, 5 (1984), Roma · Zbl 0528.90047
[82]	Lenstra, J. K.; Rinnooy Kan, A. H.G., Scheduling theory since 1981: An annotated bibliography, (O’Eigertaigh, M.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Combinatorial Optimization: Annotated Bibliographies (1984), Wiley: Wiley Chichester) · Zbl 0528.90047
[83]	Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0301.90025
[84]	Leung, J. Y., On scheduling independent tasks with restricted execution times, Operations Research, 30, 163-171 (1982) · Zbl 0481.90046
[85]	Loulou, R., Tight bounds and probabilistic analysis of two heuristics for parallel processor scheduling, Mathematics of Operations Research, 9, 142-150 (1984) · Zbl 0541.90059
[86]	McHugh, J. A.M., Hu’s precedence tree scheduling algorithm: A simple proof, Naval Research Logistics Quarterly, 31, 409-411 (1984) · Zbl 0546.90046
[87]	McNaughton, R., Scheduling with deadlines and loss functions, Management Science, 6, 1-12 (1959) · Zbl 1047.90504
[88]	Merten, A. G., Some quantitative techniques for file organization, (Technical Report No. 15 (1970), University of Wisconsin Computer Centre)
[89]	Monma, C. L., Linear-time algorithms for scheduling on parallel processors, Operations Research, 30, 116-124 (1982) · Zbl 0481.90048
[90]	Muramatsu, R.; Ishii, K.; Takahashi, Some ways to increase flexibility in manufacturing systems, International Journal of Production Research, 23, 691-703 (1985)
[91]	Muntz, R. R.; Coffman, E. G., optimal preemptive scheduling on two processor systems, IEEE Transactions on Computing, 18, 1017-1020 (1969) · Zbl 0184.20504
[92]	Panwalkar, S. S.; Iskander, W., A survey of scheduling rules, Operations Research, 25, 45-61 (1977) · Zbl 0369.90054
[93]	Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithm and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[94]	Rajaraman, M. K., An algorithm for scheduling parallel processors, International Journal of Production Research, 13, 479-486 (1975)
[95]	Rajaraman, M. K., A parallel sequencing algorithm for minimizing total cost, Naval Research Logistics Quarterly, 24, 473-481 (1977) · Zbl 0371.90067
[96]	Rinnooy Kan, A. H.G., Machine Scheduling Problems: Classification, Complexity and Computations (1976), Martinus Nijhoff: Martinus Nijhoff The Hague · Zbl 0366.90092
[97]	Root, J. G., Scheduling with deadlines and loss functions on \(k\) parallel machines, Management Science, 11, 460-475 (1965) · Zbl 0128.39502
[98]	Rothkopf, M. H., Scheduling independent tasks on parallel processors, Management Science, 12, 437-447 (1966)
[99]	Sahni, S., Algorithms for scheduling independent tasks, Journal of ACM, 23, 116-127 (1976) · Zbl 0326.68024
[100]	Sahni, S., General techniques for combinatorial approximation, Operations Research, 25, 920-927 (1977)
[101]	Sahni, S., Preemptive scheduling with due dates, Operations Research, 27, 925-934 (1979) · Zbl 0424.90031
[102]	Sarin, S. C.; Ahn, S.; Bishop, A. B., An improved branching scheme for the branch and bound procedure of scheduling \(n\) jobs on \(m\) parallel machines to minimize total weighted flowtime, International Journal of Production Research, 26, 1183-1191 (1988) · Zbl 0641.90043
[103]	Sen, T.; Raiszaden, F. M.E.; Dileepan, P., A branch-an-bound approach to the bicriterion scheduling problem involving total flowtime and range of lateness, Management Science, 34, 254-260 (1988) · Zbl 0638.90056
[104]	Sethi, R., Algorithm for minimum-length schedule, (Coffman, E. G., Computer and Job Shop Scheduling Theory (1976), Wiley: Wiley New York), 51-100
[105]	Sethi, R., Scheduling graphs on two processors, SIAM Journal of Computing, 5, 73-82 (1967)
[106]	Sethi, R., On the complexity of mean flow time scheduling, Mathematics of Operations Research, 2, 320-330 (1977) · Zbl 0402.90046
[107]	Sin, C. C.S., Some topics of parallel-machine scheduling theory (1989), Department of Actuarial and Management Sciences, University of Manitoba, Unpublished M.Sc. Thesis · Zbl 0704.90043
[108]	Stinson, D. R., An Introduction to the Design and Analysis of Algorithms (1987), Charles Babbage Research Centre: Charles Babbage Research Centre Winnipeg · Zbl 0641.05009
[109]	Tarjan, R. E., Efficiency of a good but not linear set union algorithm, Journal of ACM, 22, 215-225 (1975) · Zbl 0307.68029
[110]	Ullman, J. D., NP-complete scheduling problems, Journal of Computing System Science, 10, 384-393 (1975) · Zbl 0313.68054
[111]	Ullman, J. D., Complexity of sequencing problems, (Coffman, E. G., Computer and Job Shop Scheduling Theory (1976), Wiley: Wiley New York), 139-164
[112]	Van Wassenhove, L. N.; Baker, K. R., A bicriterion approach to time/cost trade-offs in sequencing, European Journal of Operational Research, 11, 48-54 (1982) · Zbl 0482.90043
[113]	Van Wassenhove, L. N.; Gelders, L. F., Solving a bicriterion scheduling problem, European Journal of Operational Research, 4, 42-48 (1980) · Zbl 0418.90054