Mixed graph colouring as scheduling multi-processor tasks with equal processing times

Publication date: 22 January 2025

Published in: Zhurnal Belorusskogo Gosudarstvennogo Universiteta. Matematika. Informatika (Search for Journal in Brave)

Recommendations

A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring
Scheduling Problems and Mixed Graph Colorings
scientific article; zbMATH DE number 1594564
scientific article; zbMATH DE number 1731177
Using mixed graph coloring to minimize total completion time in job shop scheduling

zbMATH Keywords

optimisation mixed graph makespan vertex colouring unit-time scheduling

Mathematics Subject Classification ID

Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Complexity of optimal scheduling problems with three jobs
Complexity of scheduling multiprocessor tasks with prespecified processors allocations
Computational Complexity of Discrete Optimization Problems
Heuristics for generalized shop scheduling problems based on decomposition
Mixed graph colorings
Mixed multigraph approach to scheduling jobs on machines of different types^∗
NP-hardness of shop-scheduling problems with three jobs
On a multiconstrained model for chromatic scheduling
On the complexity of two machine job-shop scheduling with regular objective functions
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Parameterized mixed graph coloring
Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
Reducibility among combinatorial problems
Restricted coloring models for timetabling
Scheduling Problems and Mixed Graph Colorings
Scheduling two jobs with fixed and nonfixed routes
Shop scheduling problems with multiprocessor tasks on dedicated processors
Shop-scheduling problems with fixed and non-fixed machine orders of the jobs
The complexity of shop-scheduling problems with two or three jobs
Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs
Unit Execution Time Shop Problems
Using mixed graph coloring to minimize total completion time in job shop scheduling

This page was built for publication: Mixed graph colouring as scheduling multi-processor tasks with equal processing times

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