Normal-form preemption sequences for an open problem in scheduling theory
From MaRDI portal
Publication:1702732
DOI10.1007/s10951-015-0446-9zbMath1386.90049arXiv1502.04600OpenAlexW3100513207WikidataQ59465571 ScholiaQ59465571MaRDI QIDQ1702732
Dariusz Dereniowski, Bo Chen, Edward G. jun. Coffman, Wiesław X. Kubiak
Publication date: 28 February 2018
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.04600
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time
Cites Work
- Properties of optimal schedules in preemptive shop scheduling
- Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
- An efficient algorithm for finding ideal schedules
- Rational preemptive scheduling
- Ideal preemptive schedules on two processors
- A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
- Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
- How small are shifts required in optimal preemptive schedules?
- The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays
- Minimizing total completion time for UET tasks with release time and outtree precedence constraints
- Optimal scheduling for two-processor systems
- Preemptive Scheduling of Equal Length Jobs on Two Machines to Minimize Mean Flow Time
- An Almost-Linear Algorithm for Two-Processor Scheduling
- Scheduling Tasks with Nonuniform Deadlines on Two Processors
- Two-Processor Scheduling with Start-Times and Deadlines
- Optimal Sequencing of Two Equivalent Processors
- On preemption redundancy in scheduling unit processing time jobs on two parallel machines
