article

Parallel Scheduling Algorithms

Operations Research, Volume 31, Issue 1

Pages 24 - 49

https://doi.org/10.1287/opre.31.1.24

Published: 01 February 1983 Publication History

Abstract

<P>Parallel algorithms are given for scheduling problems such as scheduling to minimize the number of tardy jobs, job sequencing with deadlines, scheduling to minimize earliness and tardiness penalties, channel assignment, and minimizing the mean finish time. The shared memory model of parallel computers is used to obtain fast algorithms.</P>

References

[1]

AGERWALA, T., AND B. LINT. 1978. Communication in Parallel Algorithms for Boolean Matrix Multiplication. Proc. 1978 Int. Conf. on Parallel Processing, IEEE, pp. 146-153.

[2]

ARJOMANDI, E. 1975. A Study of Parallelism in Graph Theory, Ph.D. thesis, Computer Science Department, University of Toronto.

Digital Library

[3]

BATCHER, K. E. 1979. MPP--A Massively Parallel Processor. Proc. 1979 Int. Conf. on Parallel Processing, IEEE, p. 249.

[4]

CSANKY, L. 1975. Fast Parallel Matrix Inversion Algorithms. Proc. 6th IEEE Symp. on Found. of Computer Science, pp. 11-12.

Digital Library

[5]

DEKEL, E., AND S. SAHNI. 1981. Binary Trees and Parallel Scheduling Algorithms. Proc. CONPAR 81, pp. 480-492. Springer-Verlag, New York.

Digital Library

[6]

ECKSTEIN, D. 1977. Parallel Graph Processing Using Depth-First Search and Breadth First Search, Ph.D. thesis, University of Iowa.

Digital Library

[7]

GERTSBAKH, I., AND H. I. STERN. 1978. Minimal Resources for Fixed and Variable Job Schedules. Opns. Res. 26, 61-85.

Digital Library

[8]

GUPTA, U. I., D. T. LEE AND J. Y. LEUNG. 1979. An Optimal Solution for the Channel-Assignment Problem. IEEE Trans. Computers C-28, 807-810.

Digital Library

[9]

HASHIMOTO, A., AND J. E. STEVENS. 1971. Wire Routing by Optimizing Channel Assignment within Large Apertures. Proc. 8th Design Automation Conference, IEEE, pp. 155-169.

Digital Library

[10]

HIRSCHBERG, D. S., A. K. CHANDRA AND D. V. SARWATE. 1979. Computing Connected Components on Parallel Computers. Commun. A.C.M. 22, 461-469.

Digital Library

[11]

HIRSCHBERG, D. S. 1978. Fast Parallel Sorting Algorithms. Commun. A.C.M. 21, 657-661.

Digital Library

[12]

HORN, W. A. 1974. Some Simple Scheduling Algorithms. Naval Res. Logist. Quart. 21, 177-185.

[13]

HOROWITZ, E., AND S. SAHNI. 1976. Exact and Approximate Algorithms for Scheduling Nonidentical Processors. J. Assoc. Comput. Mach. 23, 317-327.

Digital Library

[14]

HOROWITZ, E., AND S. SAHNI. 1978. Fundamentals of Computer Algorithms. Computer Science Press, Potomac, Md.

Digital Library

[15]

JACKSON, J. K. 1955. Scheduling a Production Line to Minimize Tardiness, Research Report 43, Management Science Research Project, University of California, Los Angeles.

[16]

KERNIGHAN, B. W., D. G. SCHWEIKERT AND G. PERSKY. 1973. An Optimum Routing Algorithm for Polycell Layouts of Integrated Circuits. Proc. 10th Design Automation Conference, IEEE, pp. 50-59.

Digital Library

[17]

LAKSHMINARAYAN, S., R. LAKSHMANAN, R. PADINEAV AND R. ROCHETTE. 1978. Optimal Single Machine Scheduling with Earliness and Tardiness Penalties. Opns. Res. 26, 1079-1082.

Digital Library

[18]

MCNAUGHTON, R. 1959. Scheduling with Deadlines and Loss Functions. Mgmt. Sci. 6, 1-12.

Digital Library

[19]

MOORE, J. M. 1968. An n job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs. Mgmt. Sci. 15, 102-109.

Digital Library

[20]

MONMA, C. L. 1982. Linear Time Algorithms for Scheduling on Parallel Processors. Opns. Res. 30, 116-124.

Digital Library

[21]

MULLER, D. E., AND F. P. PREPARATA. 1975. Bounds to Complexities of Networks for Sorting and for Switching. J. Assoc. Comput. Mach. 22, 195-201.

Digital Library

[22]

NASSIMI, D., AND S. SAHNI. 1981. Data Broadcasting in SIMD Computers. IEEE Trans. Comput. C-30, 101-107.

Digital Library

[23]

PREPARATA, F. P. 1978. New Parallel-Sorting Schemes. IEEE Trans. Comput. C-27, 669-673.

Digital Library

[24]

SAVAGE, C. 1978. Parallel Algorithms for Graph Theoretic Problems, Ph.D. thesis, University of Illinois, Urbana.

[25]

SIEGEL, H. J. 1979. A Model of SIMD Machines and a Comparison of Various Interconnection Networks. IEEE Trans. Comput. C-28, 907-917.

Digital Library

[26]

SYDNEY, J. B. 1977. Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties. Opns. Res. 25, 62-69.

Digital Library

Cited By

Aggarwal PSarangi S(2016)Lock-Free and Wait-Free Slot Scheduling AlgorithmsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.243578627:5(1387-1400)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2435786
Park EPark K(2008)An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite GraphFundamenta Informaticae10.5555/2365293.236530084:1(81-97)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/2365293.2365300
Park EPark K(2008)An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite GraphFundamenta Informaticae10.5555/1402623.140263084:1(81-97)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1402623.1402630
Show More Cited By

Parallel Scheduling Algorithms

Recommendations

Parallel job scheduling algorithms
Fast scheduling algorithms on parallel computers
Approximation algorithms for parallel machine scheduling with linear deterioration

This paper deals with a parallel machine scheduling problem. Different from fixed processing time assumption in the classical scheduling, a job's processing time is a simple linear increasing function of its starting time. The aim is makespan ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 31, Issue 1

February 1983

204 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 February 1983

Author Tag

584 parallel scheduling algorithms

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aggarwal PSarangi S(2016)Lock-Free and Wait-Free Slot Scheduling AlgorithmsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.243578627:5(1387-1400)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2435786
Park EPark K(2008)An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite GraphFundamenta Informaticae10.5555/2365293.236530084:1(81-97)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/2365293.2365300
Park EPark K(2008)An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite GraphFundamenta Informaticae10.5555/1402623.140263084:1(81-97)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1402623.1402630
Honma HMasuyama S(2008)An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc GraphIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1093/ietfec/e91-a.1.383E91-A:1(383-391)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1093/ietfec/e91-a.1.383
Horng STsai HPan YSeitzer J(2002)Optimal Algorithms for the Channel-Assignment Problem on a Reconfigurable Array of Processors with Wider Bus NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2002.105809613:11(1124-1138)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1109/TPDS.2002.1058096
Olariu SZomaya A(1996)A Time- and Cost-Optimal Algorithm for Interlocking Sets-With ApplicationsIEEE Transactions on Parallel and Distributed Systems10.1109/71.5397337:10(1009-1025)Online publication date: 1-Oct-1996
https://dl.acm.org/doi/10.1109/71.539733
Olariu SSchwing JZhang J(1992)Optimal Parallel Algorithms for Problems Modeled by a Family of IntervalsIEEE Transactions on Parallel and Distributed Systems10.1109/71.1392093:3(364-374)Online publication date: 1-May-1992
https://dl.acm.org/doi/10.1109/71.139209
Hornick SSarrafzadeh M(1987)On problem transformability in VLSIAlgorithmica10.1007/BF018403522:1-4(97-111)Online publication date: 1-Nov-1987
https://dl.acm.org/doi/10.1007/BF01840352
Dekel ESahni S(1983)Binary Trees and Parallel Scheduling AlgorithmsIEEE Transactions on Computers10.1109/TC.1983.167622332:3(307-315)Online publication date: 1-Mar-1983
https://dl.acm.org/doi/10.1109/TC.1983.1676223

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents