Article

Free access

The two-processor scheduling problem is in R-NC

Authors:

V V VaziraniAuthors Info & Claims

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

Pages 11 - 21

https://doi.org/10.1145/22145.22147

Published: 01 December 1985 Publication History

Abstract

The two-processor scheduling problem is perhaps the most basic problem in scheduling theory, and several efficient algorithms have been discovered for it. However, these algorithms are inherently sequential in nature. We give a fast parallel (R-NC) algorithm for this problem. Interestingly enough, our algorithm for this purely combinatoric-looking problem draws on some powerful algebraic methods.

References

[1]

Borodin, A., yon zur Gathen, J., and Hopcroft, J.E. "Fast Parallel Matrix and GCD Computations," FOC$ (1982) 65-71.

[2]

Coffman, E.G., Jr., and Graham, R.L. Optimol Sckeduli?zg for Twoprocessor Systems, Academic Press (~geo).

[3]

Fujii, Y., Kasami, T., and Ninamiya K. "Optimal Sequencing of Two Equivalent Processors," SIAM J. of Corr~putir~g 1 ? (1969), 784-789.

[4]

Gabow, H.N. "An Almost-linear Algorithm for Two-Processor Scheduling," JACM 29, 3 (1982), 766-780.

Digital Library

[5]

Gilmore, P.C., and Hoffman, A.J. "A Characterization of Comparability Graphs and of Interval Graphs," Canad. J. Matk. 16 (1964), 539-548.

[6]

Garey, M.R., and Johnson, D.S. "Scheduling Tasks with Nonuniform Deadlines on Two Processors," JACM 23 (1976), 461-467.

Digital Library

[7]

Garey, M.R., and Johnson D.J. Cop~zters and Intractability, A OtLide to the Theory of NP-Compteteness, W.H. Freeman and Company, San Francisco (1979).

Digital Library

[8]

Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G. "Optimization and Approximation in Deterministic Sequencing and Scheduling' a Survey," Ann. l)iscrete Math. (1978).

[9]

Gabow, H.N., and Tarjan, R.E. "A Linear-time Algorithm for Special Case of Disjoint Set Union," STOC (1983), a4 6- Za 1.

Digital Library

[10]

Karloff, H. "A Randomized Parallel Algorithm for the Odd Set Cover Problem,'' to appear.

[11]

Kowalewski~ G. "Einfuhrung in die Determinanten Theorie," Leipzig Vetlag yon Veit & Corr~p. (1909), 144.

[12]

Karp, R.M., Upfal, E., and Wigderson, A. "Finding a Maximum Matching is in R-NC," this proceeding.

[13]

Kozen, D., Vazirani, U.V., and Vazirani, V.V. "Fast Parallel Algorithms for Comparability and Interval Graphs," to appear.

[14]

Papadimitrious, C.H, and Yannakakis, M. "Scheduling Interval-Ordered Tasks," Report No. TR-11-78, Center for Research in Computing Technology, Harvard University, Cambridge, Massachusetts (1978b).

[15]

Rabin, M.O., and Vazirani, V.V. "Maximum Matchings in General Graphs through Randomization," Report No. TR-15-84, Center for Research in Computing Technology, Harvard University, Cambridge, Massachusetts (1984).

[16]

Schwartz, J.T. "Fast Probabilistic Algorithms for Verification of Polynomial Identities," JACM 27, 4 (1980), 701-717.

Digital Library

[17]

Tutte, W.T. "The Factorization of Linear Graphs," J. London Math. Soc. 22 (1974), 107-111.

[18]

Ullman, J.D. "NP-complete Scheduling Problems," J. Complzt. System Sci. 10 (1975), 384-393.

Digital Library

Cited By

Southwell RChen XHuang J(2014)Quality of Service Games for Spectrum SharingIEEE Journal on Selected Areas in Communications10.1109/JSAC.2014.140300832:3(589-600)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1109/JSAC.2014.1403008
Andrei SCheng ARinard MOsborne L(2010)Optimal Scheduling of Urgent Preemptive TasksProceedings of the 2010 IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2010.20(377-386)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.1109/RTCSA.2010.20
Helmbold DMayr E(2005)Applications of parallel scheduling to perfect graphsGraph-Theoretic Concepts in Computer Science10.1007/3-540-17218-1_59(188-203)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-17218-1_59
Show More Cited By

Index Terms

The two-processor scheduling problem is in R-NC
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
      2. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

A two-machine flowshop makespan scheduling problem with deteriorating jobs

In traditional scheduling problems, the job processing times are assumed to be known and fixed from the first job to be processed to the last job to be completed. However, in many realistic situations, a job will consume more time than it would have ...
Competitive Two-Agent Scheduling and Its Applications

We consider a scheduling environment with m (m ≥ 1) identical machines in parallel and two agents. Agent A is responsible for n₁ jobs and has a given objective function with regard to these jobs; agent B is responsible for n₂ jobs and has an objective ...
Optimal Preemptive Scheduling on Two-Processor Systems

One of the important potentials of multiprocessor systems is the ability to speed the completion of a computation by concurrently processing independent portions of the job. In this paper we consider the static scheduling of computations for a system ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

December 1985

484 pages

ISBN:0897911512

DOI:10.1145/22145

Chairman:
Robert Sedgewick

Copyright © 1985 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC85

Sponsor:

SIGACT

STOC85: Annual ACM Conference on Theory of Computing

May 6 - 8, 1985

Rhode Island, Providence, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
336
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)8

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Southwell RChen XHuang J(2014)Quality of Service Games for Spectrum SharingIEEE Journal on Selected Areas in Communications10.1109/JSAC.2014.140300832:3(589-600)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1109/JSAC.2014.1403008
Andrei SCheng ARinard MOsborne L(2010)Optimal Scheduling of Urgent Preemptive TasksProceedings of the 2010 IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2010.20(377-386)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.1109/RTCSA.2010.20
Helmbold DMayr E(2005)Applications of parallel scheduling to perfect graphsGraph-Theoretic Concepts in Computer Science10.1007/3-540-17218-1_59(188-203)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-17218-1_59
Helmbold DMayr E(2005)Two processor scheduling is in NCVLSI Algorithms and Architectures10.1007/3-540-16766-8_2(12-25)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-16766-8_2
Kozen DVazirani UVazirani V(2005)NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matchingFoundations of Software Technology and Theoretical Computer Science10.1007/3-540-16042-6_28(496-503)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-16042-6_28
Cheriyan JReif JSnyder L(1993)Parallel and output sensitive algorithms for combinatorial and linear algebra problemsProceedings of the fifth annual ACM symposium on Parallel Algorithms and Architectures10.1145/165231.165238(50-56)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/165231.165238
Coffman EGarey MKoutsougeras CVitter J(1991)Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor schedulingProceedings of the twenty-third annual ACM symposium on Theory of Computing10.1145/103418.103447(241-248)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/103418.103447
Helmbold DMayr E(1990)Applications of Parallel Scheduling Algorithms to Families of Perfect GraphsComputational Graph Theory10.1007/978-3-7091-9076-0_5(93-107)Online publication date: 1990
https://doi.org/10.1007/978-3-7091-9076-0_5
Papadimitriou CWolfe D(1988)The complexity of facets resolvedJournal of Computer and System Sciences10.1016/0022-0000(88)90042-637:1(2-13)Online publication date: 1-Aug-1988
https://dl.acm.org/doi/10.1016/0022-0000%2888%2990042-6
Mulmuley KVazirani UVazirani V(1987)Matching is as easy as matrix inversionProceedings of the nineteenth annual ACM symposium on Theory of computing10.1145/28395.383347(345-354)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/28395.383347
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents