Bounds on Multiprocessing Timing Anomalies

Abstract

Previous article Next article Bounds on Multiprocessing Timing AnomaliesR. L. GrahamR. L. Grahamhttps://doi.org/10.1137/0117039PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] E. F. Codd, Multiprogram scheduling. I, II. Introduction and theory, Comm. ACM, 3 (1960), 347–350 10.1145/367297.367317 MR0130079 0102.34202 CrossrefISIGoogle Scholar[2] R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Tech. J., 45 (1966), 1563–1581 0168.40703 CrossrefISIGoogle Scholar[3] J. Heller, Sequencing aspects of multiprogramming, J. Assoc. Comput. Mach., 8 (1961), 426–439 MR0159443 CrossrefGoogle Scholar[4] John L. Kelley, General topology, D. Van Nostrand Company, Inc., Toronto-New York-London, 1955xiv+298 MR0070144 0066.16604 Google Scholar[5] B. Liebesman, The use of a special algebra in schedule analysis, to appear Google Scholar[6] G. K. Manacher, Production and stabilization of real-time task schedules, J. Assoc. Comput. Mach., 14 (1967), 439–465 CrossrefISIGoogle Scholar[7] B. P. Ochsner, Controlling a multiprocessor system, Record, 44, Bell Laboratories, 1966, pp. 59–62 Google Scholar[8] P. Richards, Parallel programming, Rep., TD-B60-27, Technical Operations Inc., 1960 Google Scholar[9] M. Rothkopf, Scheduling independent tasks on one or more processors, Interim Tech. Rep., 2, Operations Research Center, M.I.T., Cambridge, 1964 Google Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails DAG Scheduling and Analysis on Multi-Core Systems by Modelling Parallelism and DependencyIEEE Transactions on Parallel and Distributed Systems, Vol. 33, No. 12 | 1 Dec 2022 Cross Ref The BH-mixed scheduling algorithm for DAG tasks with constrained deadlinesJournal of Systems Architecture, Vol. 131 | 1 Oct 2022 Cross Ref Streaming algorithms for multitasking scheduling with shared processingDiscrete Applied Mathematics, Vol. 320 | 1 Oct 2022 Cross Ref Checkpointing Workflows à la Young/Daly Is Not Good EnoughACM Transactions on Parallel Computing, Vol. 25 | 2 September 2022 Cross Ref Parallel Machine Scheduling Under Uncertainty: Models and Exact AlgorithmsINFORMS Journal on Computing, Vol. 68 | 17 August 2022 Cross Ref EasyFL: A Low-Code Federated Learning Platform for DummiesIEEE Internet of Things Journal, Vol. 9, No. 15 | 1 Aug 2022 Cross Ref Demand-Aware Network Design With Minimal Congestion and Route LengthsIEEE/ACM Transactions on Networking, Vol. 30, No. 4 | 1 Aug 2022 Cross Ref Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterionJournal of Global Optimization, Vol. 83, No. 3 | 26 November 2021 Cross Ref An Efficient Parallel Algorithm for Detecting Packet Filter ConflictsAlgorithms, Vol. 15, No. 7 | 7 July 2022 Cross Ref A two-stage genetic programming framework for Stochastic Resource Constrained Multi-Project Scheduling Problem under New Project InsertionsApplied Soft Computing, Vol. 124 | 1 Jul 2022 Cross Ref Minimizing makespan on parallel batch processing machines with two-dimensional rectangular jobsComputers & Industrial Engineering, Vol. 169 | 1 Jul 2022 Cross Ref Joinable Parallel Balanced Binary TreesACM Transactions on Parallel Computing, Vol. 9, No. 2 | 30 Jun 2022 Cross Ref Work-conserving disciplines are asymptotic optimal in completion time minimizationIISE Transactions, Vol. 43 | 30 June 2022 Cross Ref Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobsJournal of Scheduling, Vol. 1 | 28 June 2022 Cross Ref A novel genetic algorithm based system for the scheduling of medical treatmentsExpert Systems with Applications, Vol. 195 | 1 Jun 2022 Cross Ref Bounding the execution time of parallel applications on unrelated multiprocessorsReal-Time Systems, Vol. 58, No. 2 | 21 October 2021 Cross Ref Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion timeEuropean Journal of Operational Researc