The complexity of mean flow time scheduling problems with release times
From MaRDI portal
Publication:880590
DOI10.1007/s10951-006-0006-4zbMath1154.90407OpenAlexW1964568645MaRDI QIDQ880590
Christoph Dürr, Svetlana A. Kravchenko, Philippe Baptiste, Francis Sourd, Peter Brucker, Marek Chrobak
Publication date: 15 May 2007
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-006-0006-4
Related Items (14)
Minimizing the stretch when scheduling flows of divisible requests ⋮ Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time ⋮ Preemptive scheduling of equal-length jobs in polynomial time ⋮ A new polynomial algorithm for a parallel identical scheduling problem ⋮ Parallel machine problems with equal processing times: a survey ⋮ Minimizing total tardiness on parallel machines with preemptions ⋮ A decomposition scheme for single stage scheduling problems ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Minimizing Average Flow Time on Unrelated Machines ⋮ Ideal schedules in parallel machine settings ⋮ Preemptive scheduling on uniform machines to minimize mean flow time ⋮ Preemptive scheduling of equal length jobs with release dates on two uniform parallel machines ⋮ New complexity results for parallel identical machine scheduling problems with preemption, release dates and regular criteria ⋮ A note on \({\mathbb {NP}}\)-hardness of preemptive mean flow-time scheduling for parallel machines
Cites Work
- Properties of optimal schedules in preemptive shop scheduling
- Preemptive scheduling to minimize mean weighted flow time
- Minimizing mean flow time with release time constraint
- Minimizing the total completion time in a unit-time open shop with release times
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the complexity of minimizing the number of late jobs in unit time open shop
- Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Preemptive Scheduling of Equal Length Jobs on Two Machines to Minimize Mean Flow Time
- Open shop problems with unit time operations
This page was built for publication: The complexity of mean flow time scheduling problems with release times
