Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors

DOI10.1016/0377-2217(96)00131-2zbMath0949.68507OpenAlexW2051116751MaRDI QIDQ1278299

Marek Kubale

Publication date: 22 April 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(96)00131-2

zbMATH Keywords

edge coloringmakespanNP-completenesspolynomial algorithmprecedence constraintstotal completion timebiprocessor task

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (10)

Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications ⋮ Algorithms for data migration ⋮ Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion ⋮ Min Sum Edge Coloring in Multigraphs Via Configuration LP ⋮ Multicoloring trees. ⋮ A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints ⋮ Minimum sum multicoloring on the edges of trees ⋮ On Multi-product Lot-Sizing and Scheduling with Multi-machine Technologies ⋮ Scheduling multiprocessor tasks -- An overview ⋮ Minimizing total completion time in multiprocessor job systems with energy constraint

Cites Work

• Scheduling subject to resource constraints: Classification and complexity
• The complexity of scheduling independent two-processor tasks on dedicated processors
• Interval edge coloring of a graph with forbidden colors
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• A linear time algorithm for edge coloring of binomial trees
• Integer Programming with a Fixed Number of Variables
• Scheduling File Transfers
• The NP-Completeness of Edge-Coloring
• Open Shop Scheduling to Minimize Finish Time
• Two Results Concerning Multicoloring
• Scheduling preemptive multiprocessor tasks on dedicated processors
• NP completeness of finding the chromatic index of regular graphs

This page was built for publication: Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors