Linear-Time Algorithms for Scheduling on Parallel Processors

DOI10.1287/OPRE.30.1.116MaRDI QIDQ3939587zbMATH OpenOpenAlexFDO

Authors Clyde l. Monma

Publication date 1982

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.30.1.116

zbMATH Keywords

linear-time algorithmsprecedence constraintsscheduling n equal-length tasks on m identical parallel processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cited in

(14)

• Minimizing the number of tardy jobs with precedence constraints and agreeable due dates
• Single machine preemptive scheduling to minimize the weighted number of late jobs with deadlines and nested release/due date intervals
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• A heuristic for parallel machine scheduling with agreeable due dates to minimize the number of late jobs
• A state-of-the-art review of parallel-machine scheduling research
• On maximizing the throughput of multiprocessor tasks.
• A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem
• Scheduling unit length jobs with parallel nested machine processing set restrictions
• Makespan minimization with OR-precedence constraints
• Single processor scheduling with job values depending on their completion times
• Parallel machine scheduling with a common server
• A backward approach in list scheduling algorithms for multi-machine tardiness problems
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Level scheduling to minimize schedule length on lots of unit-time jobs

This page was built for publication: Linear-Time Algorithms for Scheduling on Parallel Processors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3939587)