An efficient algorithm for finding ideal schedules

DOI10.1007/S00236-011-0146-7MaRDI QIDQ766186zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, E. G. jun. Coffman, Wieslaw 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)

Recommendations

• Preemptive scheduling of equal length jobs with release dates on two uniform parallel machines
• scientific article; zbMATH DE number 3883931
• Ideal preemptive schedules on two processors
• scientific article; zbMATH DE number 2221458
• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
• scientific article; zbMATH DE number 1156619
• Nearly on line scheduling of preemptive independent tasks
• Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length
• Normal-form preemption sequences for an open problem in scheduling theory
• Preemptive scheduling of two uniform parallel machines to minimize total tardiness

Cites work

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

Cited in

(10)

• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• An algorithm for constructing an optimal structural schedule
• Efficient algorithms for periodic scheduling
• 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
• 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
• Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns

Describes a project that uses

Uses Software

• Algorithm 97

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q766186)