The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays

DOI10.1007/s10951-016-0507-8zbMath1376.90023OpenAlexW2588837743MaRDI QIDQ2400440

Aurélien Carlier, Claire Hanen, Alix Munier Kordon

Publication date: 1 September 2017

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://hal.sorbonne-universite.fr/hal-01472060/file/Carlier_2017_The_equivalence_of.pdf

zbMATH Keywords

approximation algorithmslist scheduling algorithmspolynomial subproblems

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 (2)

Normal-form preemption sequences for an open problem in scheduling theory ⋮ Two deadline reduction algorithms for scheduling dependent tasks on parallel processors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-complete scheduling problems
• Complexity results for single-machine problems with positive finish-start time-lags
• The worst-case analysis of the Garey-Johnson algorithm
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Scheduling an interval ordered precedence graph with communication delays and a limited number of processors
• Performance of Garey-Johnson algorithm for pipelined typed tasks systems
• Postpass Code Optimization of Pipeline Constraints
• Two-Processor Scheduling with Start-Times and Deadlines
• Some simple scheduling algorithms

This page was built for publication: The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays