Minimizing total completion time for UET tasks with release time and outtree precedence constraints

DOI10.1007/S00186-005-0009-5MaRDI QIDQ2433242zbMATH OpenOpenAlexFDO

Authors Yumei Huo, Joseph Y.-T. Leung

Publication date 27 October 2006

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00186-005-0009-5

zbMATH Keywords

nonpreemptive schedulingouttreeparallel and identical machinespreemptive schedulingschedulingtotal completion time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
• Scheduling UET-UCT outforests to minimize maximum lateness
• Minimizing mean flow time for UET tasks
• Minimizing the total completion time in a unit-time open shop with release times
• Scheduling UET-UCT tasks: Branch-and-bound search in the priority space

Cites work

• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
• Ideal preemptive schedules on two processors
• Minimizing total completion time for UET tasks with release time and outtree precedence constraints
• Optimal scheduling for two-processor systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

Cited in

(7)

• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Normal-form preemption sequences for an open problem in scheduling theory
• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
• Ideal schedules in parallel machine settings
• Minimizing total completion time for UET tasks with release time and outtree precedence constraints
• A new polynomial algorithm for a parallel identical scheduling problem
• The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders

This page was built for publication: Minimizing total completion time for UET tasks with release time and outtree precedence constraints

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