On the Complexity of Mean Flow Time Scheduling

DOI10.1287/MOOR.2.4.320MaRDI QIDQ4187560zbMATH OpenOpenAlexFDO

Authors Ravi Sethi

Publication date 1977

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.2.4.320

zbMATH Keywords

Computational ComplexityIdentical Parallel MachinesMean Flow Time SchedulingNp-CompleteSeries-Parallel Precedence ConstraintsTree- Like Precedence Constraints

Mathematics Subject Classification ID

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

Cited in

(8)

• Minimizing the makespan on two identical parallel machines with mold constraints
• Scheduling chain-structured tasks to minimize makespan and mean flow time
• NP-Complete operations research problems and approximation algorithms
• Task scheduling with precedence constraints to minimize the total completion time
• Logic-based benders decomposition for bi-objective parallel machine selection and job scheduling with release dates and resource consumption
• Parallel machine scheduling with position-dependent processing times and deteriorating maintenance activities
• Fifty years of research in scheduling -- theory and applications
• A state-of-the-art review of parallel-machine scheduling research

This page was built for publication: On the Complexity of Mean Flow Time Scheduling

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