Restrictions and preassignments in preemptive open shop scheduling
| Autor: | N. V. R. Mahadev, Uri N. Peled, D. de Werra, Alan J. Hoffman |
|---|---|
| Rok vydání: | 1996 |
| Předmět: |
Discrete mathematics
Open-shop scheduling Open shop scheduling Applied Mathematics Multigraph ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION Production Flow shop scheduling Complete coloring Greedy coloring Combinatorics Edge coloring Bipartite graph Discrete Mathematics and Combinatorics Chromatic scheduling Fractional coloring Computer Science::Databases Edgecoloring Timetabling MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Applied Mathematics. 68:169-188 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/0166-218x(95)00055-v |
| Popis: | Preemptive open shop scheduling can be viewed as an edge coloring problem in a bipartite multigraph. In some applications, restrictions of colors (in particular preassignments) are made for some edges. We give characterizations of graphs where some special preassignments can be embedded in a minimum coloring (number of colors = maximum degree). The case of restricted colorings of trees is shown to be solvable in polynomial time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect