Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
From MaRDI portal
Publication:1278299
DOI10.1016/0377-2217(96)00131-2zbMath0949.68507OpenAlexW2051116751MaRDI QIDQ1278299
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
edge coloringmakespanNP-completenesspolynomial algorithmprecedence constraintstotal completion timebiprocessor task
Related Items
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
