The complexity of scheduling independent two-processor tasks on dedicated processors

DOI10.1016/0020-0190(87)90176-1zbMath0653.68015OpenAlexW2063957224MaRDI QIDQ1107984

Marek Kubale

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90176-1

zbMATH Keywords

computational complexityedge coloringNP-completenesstwo-processor task scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)

Related Items (24)

An approximation result for the interval coloring problem on claw-free chordal graphs ⋮ An approximation result for a duo-processor task scheduling problem ⋮ Complexity of scheduling multiprocessor tasks with prespecified processors allocations ⋮ Scheduling: agreement graph vs resource constraints ⋮ An approximation algorithm for scheduling on three dedicated machines ⋮ Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion ⋮ Efficiency and effectiveness of normal schedules on three dedicated processors ⋮ Scheduling independent tasks with multiple modes ⋮ Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors ⋮ Deadline scheduling of multiprocessor tasks ⋮ On the complexity of adjacent resource scheduling ⋮ Compact cyclic edge-colorings of graphs ⋮ Complexity and approximation results for scheduling multiprocessor tasks on a ring. ⋮ Consecutive edge-coloring of the generalized \(\theta \)-graph ⋮ Scheduling multiprocessor tasks on three dedicated processors ⋮ A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints ⋮ Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness ⋮ Comparability graph augmentation for some multiprocessor scheduling problems ⋮ Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness ⋮ Scheduling multiprocessor tasks -- An overview ⋮ Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors ⋮ Interval vertex-coloring of a graph with forbidden colors ⋮ Lower bound algorithms for multiprocessor task scheduling with ready times ⋮ Scheduling multiprocessor tasks on two parallel processors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear algorithms for edge-coloring trees and unicyclic graphs
• Scheduling independent 2-processor tasks to minimize schedule length
• On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• The NP-Completeness of Edge-Coloring
• On Edge Coloring Bipartite Graphs

This page was built for publication: The complexity of scheduling independent two-processor tasks on dedicated processors