NP-complete scheduling problems

1975/06/01 by Jeffrey D. Ullman, J.D. Ullman · 1,439 citations
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Computer science #Conjecture #Mathematical optimization #Mathematics #NP-complete #Operating system #Optimization and Packing Problems #Optimization and Search Problems #Parallel computing #Preemption #Schedule #Scheduling (production processes) #Scheduling and Optimization Algorithms #Time complexity

paper · pdf · doi:10.1016/s0022-0000(75)80008-0

published in Journal of Computer and System Sciences 10(3), 384-393 (Elsevier BV)

openalex publication_date 1975/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Cited by

• Worst Case Analysis of Two Scheduling Algorithms
• 2PS: High-Quality Edge Partitioning with Two-Phase Streaming
• Workflow scheduling based on asynchronous advantage actor–critic algorithm in multi-cloud environment
• Introducing Resizable Region Packing Problem in Image Generation, with a Heuristic Solution
• Batch Query Processing and Optimization for Agentic Workflows
• Co-evolutionary and Elite learning-based bi-objective Poor and Rich Optimization algorithm for scheduling multiple workflows in the cloud
• Scheduling massively parallel multigrid for multilevel Monte Carlo methods
• Energy and Time Efficient Scheduling of Tasks with Dependencies on Asymmetric Multiprocessors
• Exploring the Relation Between Two Levels of Scheduling Using a Novel Simulation Approach
• Analyzing Branch-and-Bound Algorithms for the Multiprocessor Scheduling Problem
• A GA based approach for task scheduling in multi-cloud environment
• A quest for a fair schedule: The Young Physicists' Tournament
• Exploring the Role of Machine Learning in Scientific Workflows:\n Opportunities and Challenges
• Parameterized Complexity of Partial Scheduling
• RLScheduler: An Automated HPC Batch Job Scheduler Using Reinforcement Learning
• A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience
• Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling
• Hydra: A System for Large Multi-Model Deep Learning
• Runtime vs Scheduler: Analyzing Dask's Overheads
• Adaptra: Straggler-Resilient Hybrid-Parallel Training with Pipeline Adaptation
• `` Strong '' NP-Completeness Results
• A Survey on Parallel Genetic Algorithms for Shop Scheduling Problems
• Feasibility Analysis in the Sporadic DAG Task Model
• Performance-effective and low-complexity task scheduling for heterogeneous computing
• A quest for a fair schedule: The International Young Physicists' Tournament. [europepmc]
• Cognitive assistance for action selection: Challenges and approaches. [europepmc]
• Research on computing task scheduling method for distributed heterogeneous parallel systems. [europepmc]