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

DOI10.1016/0020-0190(87)90176-1MaRDI QIDQ1107984zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3857145 (Why is no real title available?)
• scientific article; zbMATH DE number 3918395 (Why is no real title available?)
• scientific article; zbMATH DE number 9845 (Why is no real title available?)
• Linear algorithms for edge-coloring trees and unicyclic graphs
• On Edge Coloring Bipartite Graphs
• On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
• Scheduling independent 2-processor tasks to minimize schedule length
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• The NP-Completeness of Edge-Coloring

Cited in

(24)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107984)