Chromatic scheduling

doi:10.1017/CBO9781139519793.015

12 - Chromatic scheduling

Published online by Cambridge University Press: 05 May 2015

Dominique de Werra and

Alain Hertz

Edited by

Lowell W. Beineke and

Robin J. Wilson

Show author details

Dominique de Werra: Affiliation:
Ecole Polytechnique Fédérale de Lausanne in Switzerland
Alain Hertz: Affiliation:
École Polytechnique Fédérale de Lausanne in Switzerland
Lowell W. Beineke: Affiliation:
Purdue University, Indiana
Robin J. Wilson: Affiliation:
The Open University, Milton Keynes

Book contents

Get access

Summary

Variations and extensions of the basic vertex-colouring and edge-colouring models have been developed to deal with increasingly complex scheduling problems. We present and illustrate them in specific situations where additional requirements are imposed. We include list-colouring, mixed graph colouring, co-colouring, colouring with preferences and bandwidth colouring, and we present applications of edge-colourings to open shop, school timetabling and sports scheduling problems. We also discuss balancing and compactness constraints which often appear in practical situations.

Introduction

We show here how graph colouring models may provide a natural tool for dealing with a variety of scheduling problems. Starting from the basic vertex-colouring model, we will introduce some variations and extensions that are motivated by their applications to some scheduling issues. In each case we give references for further results and for extensions of the various models presented. For algorithms, see Chapter 13.

In chromatic scheduling problems we have a collection V of items, such as operations of jobs to be performed. In V there are some pairs v, w that are subject to an incompatibility condition and we call E the set of such incompatibility pairs. These data are represented by the graph G = (V, E) in which the items are associated with the vertices and the incompatible pairs v,w with the edges vw between the corresponding vertices.

We also have a set C = {1, 2, …, k} of time periods (of unit duration). Assuming that each item (considered as an operation) has unit completion time, we may ask whether we can find a schedule taking the incompatibilities into account and using at most k periods of time. This is precisely the vertex k-colouring problem: there exists a feasible schedule if and only if the set V of vertices can be partitioned into subsets S1, S2, …, Sk, where each Si contains no two incompatible items.

In some instances, we may try to find the smallest set C of periods (that is, the smallest k) for which a schedule in time k = |C| exists.

Type: Chapter
Information: Topics in Chromatic Graph Theory , pp. 255 - 276

DOI: https://doi.org/10.1017/CBO9781139519793.015 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. S., Altinakar, G., Caporossi and A., Hertz, On compact k-edge colorings: a polynomial time reduction from linear to cyclic, Discrete Optimization 8 (2011), 502–512.Google Scholar

2. C., Archetti, N., Bianchessi and A., Hertz, A branch-and-price algorithm for the robust graph coloring problem, Les Cahiers du Gerad, G-2011-75, Montréal, 2011.Google Scholar

3. M., Bouchard, M., Čangalovič and A., Hertz, About equivalent interval colorings of weighted graphs, Discrete Appl. Math. 157 (2009), 3615–3624.Google Scholar

4. M., Bouchard, A., Hertz and G., Desaulniers, Lower bounds and a tabu search algorithm for the minimum deficiency problem, J. Combin. Optimization 17 (2009), 168–191.Google Scholar

5. D., Brélaz, Y., Nicolier and D., de Werra, Compactness and balancing in scheduling, Zeitschrift für Operations Research 21 (1977), 65–73.Google Scholar

6. E. K., Burke, D., de Werra and J., Kingston, Applications to timetabling, Handbook of Graph Theory (eds. J. L., Gross and J., Yellen), CRC Press (2004), 445–174.Google Scholar

7. D., Cartwright and F., Harary, Structural balance: a generalization of Heider's theory, Psychological Review 63 (1956), 277–293.Google Scholar

8. D., de Werra, A note on graph coloring, RAIRO, Revue Française d'Automatique, d'Informatique et de Recherche Opérationnelle R-1 (1974), 49–53.Google Scholar

9. D., de Werra, A few remarks on chromatic scheduling, Combinatorial programming, Methods and Applications (ed. B., Roy), D. Reidel (1975), 337–342.Google Scholar

10. D., de Werra, Some models of graphs for scheduling sports competitions, Discrete Appl. Math. 21 (1988), 47–65.Google Scholar

11. D., de Werra, Graph theoretical models for preemptive scheduling, Advances in Project Scheduling (eds. R., Slowinski and J., Weglarz), Elsevier (1989), 171–185.Google Scholar

12. D., de Werra and Y., Gay, Chromatic scheduling and frequency assignment, Discrete Appl. Math. 49 (1994), 165–174.Google Scholar

13. D., de Werra, A., Hertz, D., Kobler and N. V. R., Mahadev, Feasible edge colorings of trees with cardinality constraints, Discrete Math. 222 (2000), 61–72.Google Scholar

14. D., de Werra and Ph., Solot, Compact cylindrical chromatic scheduling, SIAM J. Discrete Math. 4 (1991), 528–534.Google Scholar

15. M., Demange, D., de Werra, J., Monnot and V., Paschos, Time slot scheduling of compatible jobs, J. Scheduling 10 (2007), 111–127.Google Scholar

16. M., Demange, T., Ekim and D., de Werra, On the approximation of min split coloring and min cocoloring, J. Graph Algorithms and Appl. 10 (2006), 297–315.Google Scholar

17. M., Demange, T., Ekim and D., de Werra, A tutorial on the use of graph coloring for some problems in robotics, Europ. J. Oper. Res. 192 (2009), 41–55.Google Scholar

18. T., Ekim and D., de Werra, On split-coloring problems, J. Combin. Optimization 10 (2005), 211–225.Google Scholar

19. P., Erdős, A. L., Rubin and H., Taylor, Choosability in graphs, Congr. Numer. 26 (1979), 125–157.Google Scholar

20. S., Even, A., Itai and A., Shamir, On the complexity of timetable and multicommodity flow problems, SIAM J. Comput. 5 (1976), 691–703.Google Scholar

21. M. R., Garey and D. S., Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.Google Scholar

22. K., Giaro, The complexity of consecutive Δ-coloring of bipartite graphs: 4 is easy, 5 is hard, Ars Combin. 47 (1997), 287–298.Google Scholar

23. K., Giaro, M., Kubale and M., Malafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001), 131–143.Google Scholar

24. J., Gimbel, D., Kratsch and L., Stewart, On cocolourings and cochromatic numbers of graphs, Discrete Appl. Math. 48 (1994), 111–127.Google Scholar

25. T., Gonzales and S., Sahni, Open shop scheduling to minimize finish time, J. ACM 23 (1976), 665–679.Google Scholar

26. S., Gutner, The complexity of planar graph choosability, Discrete Math. 159 (1996), 119–130.Google Scholar

27. A., Hajnal and E., Szemerédi, Proof of a conjecture of P. Erdős, Combinatorial Theory and its Applications, Balatonfured (eds. P., Erdős, A., Rényi and V. T., Sős), North-Holland (1970), 601–623.Google Scholar

28. M. M., Halldórsson and G., Kortsarz, Multicoloring: problems and techniques, Math. Foundations of Computer Science,LNCS 3153 (2004), 25–41.Google Scholar

29. P., Hansen, J., Kuplinski and D., de Werra, Mixed graph coloring, Math. Methods of Operations Research 45 (1997), 145–160.Google Scholar

30. A., Hertz and B., Ries, On r-equitable colorings of trees and forests, Les Cahiers du Gerad, G-2011-40, Montreal, 2011.Google Scholar

31. G., Kendall, S., Knust, C. C., Ribeiro and S., Urrutia, Scheduling in sports: an annotated bibliography, Computers Oper. Res. 37 (2010), 1–19.Google Scholar

32. H. A., Kierstead and A. V., Kostochka, A short proof of the Hajnal-Szemerédi theorem on equitable coloring, Combin. Probab. Comput. 17 (2008), 265–270.Google Scholar

33. S., Prestwich, Constrained bandwidth multicoloration neighborhoods, Proc. Computational Symp. on Graph Coloring and its Generalizations, Ithaca(eds. D. S., Johnson, A., Mehrotra and M., Trick), (2002), 126–133.Google Scholar

34. R. V., Rassmussen and M. A., Trick, The timetable constrained distance minimization problem, Annals of Operations Research 171 (2006), 167–181.Google Scholar

35. B., Ries, Coloring some classes of mixed graph, Discrete Appl. Math. 155 (2007), 1–6.Google Scholar

36. B., Ries and D., de Werra, On two coloring problems in mixed graphs, Europ. J. Combin. 29 (2008), 712–725.Google Scholar

37. B., Robillard, Vérification Formelle et Optimisation de l'Allocation de Registres, Ph.D. Thesis, CNAM, Paris, 2010.Google Scholar

38. B., Roy, Nombre chromatique etplus longs chemins d'un graphe, RAIRO, Revue Française d'Automatique, d'Informatique et de Recherche Opérationnelle 1 (1967), 129–132.Google Scholar

39. A., Schwartz, The deficiency of a regular graph, Discrete Math. 306 (2006), 1947–1954.Google Scholar

40. Y. N., Sotskov, A., Dolgui and F., Werner, Mixed graph coloring for unit-time job-shop scheduling, Internat. J. Math. Algorithms 4 (2001), 289–323.Google Scholar

41. M., ČangaloviČ and J. A. M., Schreuder, Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths, Europ. J. Operational Research 51 (1991), 248–258.Google Scholar

42. M., Voigt, List colourings of planar graphs, Discrete Math. 120 (1993), 215–219.Google Scholar

43. J., Yánez and J., Ramírez, The robust coloring problem, Europ. J. Operational Research 148 (2003), 546–558.Google Scholar

Book contents

12 - Chromatic scheduling

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive