Preemptive scheduling with variable profile, precedence constraints and due dates

DOI10.1016/0166-218X(93)E0151-NzbMath0833.90071OpenAlexW2004430504MaRDI QIDQ1805445

Eric Sanlaville, Zhen Liu

Publication date: 18 March 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0151-n

zbMATH Keywords

latenessmakespanprecedence constraintsmaximum latenessvariable profilelist scheduleearliest due datepriority schedulescheduling preemptive tasks

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Nearly on line scheduling of preemptive independent tasks ⋮ Total completion time minimization on multiple machines subject to machine availability and makespan constraints ⋮ Scheduling jobs in open shops with limited machine availability ⋮ Unnamed Item ⋮ Scheduling multiprocessor tasks on parallel processors with limited availability. ⋮ Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints ⋮ Scheduling with limited machine availability ⋮ Online scheduling on semi-related machines ⋮ Scheduling two-stage hybrid flow shop with availability constraints ⋮ Two-machine flow shops with limited machine availability ⋮ Parallel machine makespan minimization subject to machine availability and total completion time constraints ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ Scheduling multiprocessor tasks with chain constraints ⋮ Dynamic scheduling of parallel computations ⋮ Linear and quadratic algorithms for scheduling chains and opposite chains

Cites Work

• NP-complete scheduling problems
• Optimal scheduling for two-processor systems
• Scheduling with Deadlines and Loss Functions
• Scheduling precedence graphs of bounded height
• Profile Scheduling of Opposing Forests and Level Orders
• Scheduling Flat Graphs
• Scheduling Independent Tasks with Deadlines on Semi-identical Processors
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• Scheduling Opposing Forests
• Optimal Preemptive Scheduling on Two-Processor Systems
• Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
• Unnamed Item
• Unnamed Item