Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
From MaRDI portal
Publication:1399579
DOI10.1016/S0377-2217(02)00767-1zbMath1030.90027OpenAlexW1964198588MaRDI QIDQ1399579
Publication date: 30 July 2003
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0377-2217(02)00767-1
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (12)
Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ On minimizing the weighted number of late jobs in unit execution time open-shops. ⋮ Integer preemptive scheduling on parallel machines ⋮ A complete 4-parametric complexity classification of short shop scheduling problems ⋮ Scheduling results applicable to decision-theoretic troubleshooting ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ A metric approach for scheduling problems with minimizing the maximum penalty ⋮ On preemption redundancy in scheduling unit processing time jobs on two parallel machines ⋮ Polyhedral results for position-based scheduling of chains on a single machine ⋮ Open-shop scheduling for unit jobs under precedence constraints ⋮ Integrality Property in Preemptive Parallel Machine Scheduling
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimizing mean flow time with release time constraint
- A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
- On the complexity of preemptive open-shop scheduling problems
- Some no-wait shops scheduling problems: Complexity aspect
- Openshop and flowshop scheduling to minimize sum of completion times
- Computing the bump number with techniques from two-processor scheduling
- Complexity results for scheduling chains on a single machine
- NP-complete scheduling problems
- Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
- Total completion time minimization in two-machine job shops with unit-time operations
- A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness
- A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}\) open shop problem]
- Minimizing the total completion time in a unit-time open shop with release times
- A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
- Is a unit-job shop not easier than identical parallel machines?
- On minimizing the weighted number of late jobs in unit execution time open-shops.
- Scheduling equal-length jobs on identical parallel machines
- A polynomial algorithm for an open shop problem with unit processing times and tree constraints
- Scheduling chain-structured tasks to minimize makespan and mean flow time
- An efficient algorithm for a job shop problem
- On the complexity of minimizing the number of late jobs in unit time open shop
- Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
- Complexity results for single-machine problems with positive finish-start time-lags
- Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems
- Optimal scheduling for two-processor systems
- Scheduling with Deadlines and Loss Functions
- A Note On The Complexity Of Openshop Scheduling Problems
- Minimizing Total Tardiness on One Machine is NP-Hard
- Scheduling identical jobs on uniform parallel machines
- On Some Variants of the Bandwidth Minimization Problem
- Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines
- Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates
- Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs
- Deterministic Scheduling with Pipelined Processors
- A New Algorithm for Preemptive Scheduling of Trees
- Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
- Linear-Time Algorithms for Scheduling on Parallel Processors
- Minimizing Maximum Lateness in a Two-Machine Open Shop
- Minimizing Total Tardiness on a Single Machine with Precedence Constraints
- Open shop problems with unit time operations
- Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops
- Open Shop Scheduling to Minimize Finish Time
- A Level Algorithm for Preemptive Scheduling
- Two-Processor Scheduling with Start-Times and Deadlines
- Complexity of Scheduling under Precedence Constraints
- Flowshop and Jobshop Schedules: Complexity and Approximation
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
- Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
- Computational Complexity of Discrete Optimization Problems
- Some simple scheduling algorithms
- A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
- Scheduling independent tasks to reduce mean finishing time
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
- On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs
- Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
- On preemption redundancy in scheduling unit processing time jobs on two parallel machines
This page was built for publication: Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
