A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring

DOI10.1134/s000511792302008xzbMath1521.90073OpenAlexW4385844240MaRDI QIDQ6047981

Yuri N. Sotskov

Publication date: 13 September 2023

Published in: Automation and Remote Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s000511792302008x

zbMATH Keywords

schedulemixed graphpreemptionoptimal coloringmakespan optimality

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using mixed graph coloring to minimize total completion time in job shop scheduling
• A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
• Computational complexity of some scheduling problems with multiprocessor tasks
• Scheduling multiprocessor UET tasks of two sizes
• Scheduling multiprocessor tasks -- An overview
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• Mixed graph colorings
• A note on scheduling multiprocessor tasks with identical processing times.
• Shop scheduling problems with multiprocessor tasks on dedicated processors
• Scheduling Problems and Mixed Graph Colorings
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring