An efficient algorithm for finding ideal schedules

DOI10.1007/s00236-011-0146-7zbMath1262.68022OpenAlexW2095614028MaRDI QIDQ766186

Dariusz Dereniowski, Edward G. jun. Coffman, Wiesław X. Kubiak

Publication date: 23 March 2012

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-011-0146-7

zbMATH Keywords

schedulingideal schedulesprocedence constraintsUET tasks

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (5)

A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows ⋮ Normal-form preemption sequences for an open problem in scheduling theory ⋮ Ideal schedules in parallel machine settings ⋮ Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time

Uses Software

• Algorithm 97

Cites Work

• Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
• Ideal preemptive schedules on two processors
• Optimal scheduling for two-processor systems
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Two-Processor Scheduling with Start-Times and Deadlines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Optimal Sequencing of Two Equivalent Processors
• A Theorem on Boolean Matrices

This page was built for publication: An efficient algorithm for finding ideal schedules