article

Free access

Scheduling Tasks with Nonuniform Deadlines on Two Processors

Authors:

D. S. JohnsonAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 3

Pages 461 - 467

https://doi.org/10.1145/321958.321967

Published: 01 July 1976 Publication History

Abstract

Given a set @@@@ = {T₁,T₂,···,T_n} of tasks, with each T_i having execution time 1 and a deadline d_i > 0, and a set of precedence constraints which restrict allowable schedules, the problem of determining whether there exists a schedule using two processors in which each task is completed before its deadline is examined. An efficient algorithm for finding such a schedule, whenever one exists, is given. The algorithm may also be used to find the shortest such schedule. In addition it is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.

References

[1]

AH0, A.V., GAREY, M.R., AND ULLMAN, J.D. The transitive reduction of a directed graph SIAM J. Comput. 1 (1972), 131-137.]]

[2]

AHO, A.V., HOPCROFT, J.E., AND ULLMAN, j.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974, Ch. 10.]]

[3]

ARLAZAROV, V.L., DINXC, E.A., KRONOD, M.A., AND FARADZEV, I.A. On economical construction of the transitive closure of an oriented graph. Dokl. Akad. Nauk SSSR 11 (1970), 1209-1210.]]

[4]

COFFMAN, E.G., AND GRAHAM, R.L. Optimal scheduling for two-processor systems Acta lnformatica 1 (1972), 2{}0-213.]]

[5]

FISCHF.R, M J, AND MEYER, A.R. Booleanmatrix multiplication and transitive closure. Twelfth Ann. Symp on Switching and Automata Theory, East Lansing, Mlch, 1971, pp. 129-131.]]

[6]

FuJII, M., KASAMI, T., AND NINOMIYA, K Optimal sequencing of two equivalent processors. SIAM J. Appl. Math. 17 (1969), 784-789.]]

[7]

FuJII, M., KASAMI, W., AND NINOMIYA, K Erratum. SIAM J. Appl. Math. ~0 (1971), 141.]]

[8]

G^REY, M.R., AND JOHNSON, D.S. Complexity results for multiprocessor scheduling under resource constraints SIAM J. Comput. ~ (1975), 397--411.]]

[9]

GRAhAm, R.L. Bounds on multiprocessing anomalies and related packing algorithms. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J., pp. 205--217.]]

[10]

KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computat,ons, R.E. Miller and J W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85--104.]]

[11]

MooRE, M.J. An n job, one-machine sequencing algorithm for minimizing the number of late jobs. Manage. Sci. 15 (1968), 102-109.]]

[12]

MURAOKA, Y. Parallelism exposure and exploitation in programs. Ph.D. Th., U. of Illinois, Urbana, Ill., 1971.]]

[13]

PURDOM, P. A transitive closure algorithm. BIT 10 (1970), 76-94.]]

[14]

SIDNEY, J.B An extension of Moore's due date algorithm. In Symposium on the Theory of Scheduling and Its Applications, S.M. Elmaghraby, Ed., Springer-Verlag, New York, 1973, pp. 393-398.]]

[15]

ULLMAN, J.D. NP-complete scheduling problems. J. Comput. Syst. Scis. i0 (1975), 384-393.]]

[16]

WARSHALL, S. A theorem on Boolean matrices. J. ACM9,1 (Jan. 1962), 11-12.]]

Cited By

Bożejko WPempera JUchroński MWodecki M(2024)Quantum annealing-driven branch and bound for the single machine total weighted number of tardy jobs scheduling problemFuture Generation Computer Systems10.1016/j.future.2024.02.016155(245-255)Online publication date: Jun-2024
https://doi.org/10.1016/j.future.2024.02.016
Liao XZhang HKoshimura MHuang RYu WLi F(2021)Modeling and Solving Scheduling in Overloaded Situations with Weighted Partial MaxSATMathematical Problems in Engineering10.1155/2021/96154632021(1-17)Online publication date: 16-Jul-2021
https://doi.org/10.1155/2021/9615463
Li HHuh WSampaio MKeng N(2021)Planning Production and Equipment Qualification under High Process FlexibilityProduction and Operations Management10.1111/poms.1343930:10(3369-3390)Online publication date: 1-Oct-2021
https://doi.org/10.1111/poms.13439
Show More Cited By

Index Terms

Scheduling Tasks with Nonuniform Deadlines on Two Processors
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. 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

Scheduling task with state-dependent deadlines
Scheduling multiprocessor UET tasks of two sizes

In this paper we study task scheduling problems on m identical parallel processors, where each task has unit execution time, and needs either a single processor, or q processors concurrently, and it has a release date and a due date. Under the ...
Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 23, Issue 3

July 1976

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321958

Issue’s Table of Contents

Copyright © 1976 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in JACM Volume 23, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

114
Total Citations
View Citations
817
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)10

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bożejko WPempera JUchroński MWodecki M(2024)Quantum annealing-driven branch and bound for the single machine total weighted number of tardy jobs scheduling problemFuture Generation Computer Systems10.1016/j.future.2024.02.016155(245-255)Online publication date: Jun-2024
https://doi.org/10.1016/j.future.2024.02.016
Liao XZhang HKoshimura MHuang RYu WLi F(2021)Modeling and Solving Scheduling in Overloaded Situations with Weighted Partial MaxSATMathematical Problems in Engineering10.1155/2021/96154632021(1-17)Online publication date: 16-Jul-2021
https://doi.org/10.1155/2021/9615463
Li HHuh WSampaio MKeng N(2021)Planning Production and Equipment Qualification under High Process FlexibilityProduction and Operations Management10.1111/poms.1343930:10(3369-3390)Online publication date: 1-Oct-2021
https://doi.org/10.1111/poms.13439
Gehlot HSundaram SUkkusuri S(2021)Control Policies for Recovery of Interdependent Systems After DisruptionsIEEE Transactions on Control of Network Systems10.1109/TCNS.2021.30947868:4(1975-1986)Online publication date: Dec-2021
https://doi.org/10.1109/TCNS.2021.3094786
Zhang YHe FSato TOki E(2020)Network Service Scheduling With Resource Sharing and PreemptionIEEE Transactions on Network and Service Management10.1109/TNSM.2019.295694917:2(764-778)Online publication date: 10-Jun-2020
https://dl.acm.org/doi/10.1109/TNSM.2019.2956949
Geng ZYuan JYuan J(2018)Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum costApplied Mathematics and Computation10.1016/j.amc.2018.03.001332(1-18)Online publication date: Sep-2018
https://doi.org/10.1016/j.amc.2018.03.001
Guo LShen H(2017)Efficient Approximation Algorithms for the Bounded Flexible Scheduling Problem in CloudsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.273184328:12(3511-3520)Online publication date: 9-Nov-2017
https://dl.acm.org/doi/10.1109/TPDS.2017.2731843
Chen BCoffman EDereniowski DKubiak W(2016)Normal-form preemption sequences for an open problem in scheduling theoryJournal of Scheduling10.1007/s10951-015-0446-919:6(701-728)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s10951-015-0446-9
Zinder YWalker S(2015)Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum latenessDiscrete Applied Mathematics10.1016/j.dam.2015.05.005196:C(28-53)Online publication date: 11-Dec-2015
https://dl.acm.org/doi/10.1016/j.dam.2015.05.005
Chang JGabow HKhuller S(2014)A Model for Minimizing Active Processor TimeAlgorithmica10.1007/s00453-013-9807-y70:3(368-405)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1007/s00453-013-9807-y
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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents