Sujet de thèse: Graph algorithms to handle job scheduling problems


Directeurs de thèse :M. Montassier, A. Pêcher (HDR) , A. Raspaud




Équipe: combinatoire et algorithmique


Description synthétique du sujet (en anglais)


A breakthrough was recently achieved by Fekete and Schepers (2004) to model multi-dimensional placements: instead of defining the absolute position of items, they formulated the problem in terms of the relative positions of items. Two items have non overlapping positions if they are on each others side along at least one dimension. This is modeled by defining a non-edge in a graph associated to that dimension: thus this graph is the complement of an interval graph. This model is very efficient as any symmetric placement gives rise to the same graph representation.

The aim is to develop efficient algorithms to handle periodic scheduling problems, as cyclic orthogonal packings can be used to handle periodic scheduling problems: in the cyclic orthogonal packing problem, boundaries of the container are identified two-by-two. Hence using the similar approach gives now the complement of a circular arc graph for each dimension, which are not perfect anymore. Thus Fekete and Schepers' approach stops short...

Hence specific graph colorings algorithms are needed: circular colorings are well-known to be relevant when periodic solutions are required. Two new kinds of graph colorings, called adapted coloring (introduced by Hell and Zhu) and adapted list coloring (introduced by Kostochka and Zhu) are also suitable to handle scheduling problems. The aim is to better understand these new colorings, and their relationships with scheduling problems.

The research will be conducted within LaBRI's subteam "Graphs and applications" and within INRIA team RealOpt


Description détaillée du sujet (en anglais):


Many combinatorial optimization problems can be modeled as the search for a specific structure in a graph: for example ensuring connectivity in a network amounts to building a tree that spans all the nodes; inquiring about its resistance to failure amounts to searching for a minimum cardininality cut that partitions the graph; selecting disjoint pairs of objects is represented by a so called matching; disjunctive choices can be modeled by edges in a so called conflict graph where one searches for stable sets; in particular, in time tabling problems, the conflict graph is a so called interval graph (recognizing this special property leads to an easy solution).


The relationships between both mathematical programming and graph theory have allowed several famous research advances such as perfect graph theory and its implications in semidefinite programming [7], Goemans-Williamson Max Cut algorithm [6], Edmond’s work on the matching polytope [5], paving the way for efficients algorithm to compute the weighted stability number of claw-free graphs ... Let us develop one such example, which lies at the heart of this subject.


Fekete and Schepers [4] managed a recent breakthrough in solving multi-dimensional orthogonal placement problems. by using an efficient representation of all geometrically symmetric solutions by a so called packing class involving one interval graph (whose complement admits a transitive orientation: each such orientation of the edges corresponds to a specific placement of the forms) for each dimension. Though Fekete & Schepers’ framework is very efficient, we have however identified several weaknesses in their algorithms: the most obvious one is that they do not take advantage of the sophisticated data structures (called MPQ trees) which were introduced to design linear time recognition algorithms of interval graphs. They use instead a very basic characterization of interval graphs. Thus we think that significative improvments on this problems are possible. This will be the first goal.


Another goal will be to apply the same approach to handle scheduling problems: Fekete and Schepers’ reformulation in this setting would involve circular-arc graphs. In contrary to interval graphs, these graphs are not perfect and relevant algorithms are to be designed. This is one topic of the subject. Some of the other topics rely on variations of chromatic number, able to capture more precisely the specificity of some subproblems of packing problems. The concept of adapted colouring of graph was introduced by Hell and Zhu [9], and has connections with matrix partition of graphs, graph homomorphisms, and full constraint satisfaction problems
[1, 2, 3, 8]. Adapted list colouring of graphs and hypergraphs was introduced by Kostochka and Zhu in [10]. Let us explain in a few word why adapted list colouring, for instance, is suitable to modelize scheduling problems. Compared to the original list colouring model, the adapted list colouring allows different constraints for different colours. For example, suppose there is a set of football games needed to be scheduled into a set of time slots. The time slots are the colours. The constraints are whether two games can be assigned to the same time slot. For external reasons, it may happen that two games a and b cannot be both assigned to time slot i, however, they can be both assigned to time slot j. Adapted list coloring allows to take into account this kind of constraints.

Channel assignment is another well-known application area of graph colorings. The channel assignment problem in radio or cellular phone networks is the following : we need to assign radio frequency bands to transmitters (each station gets one channel which corresponds to an integer). In order to avoid interference, if two stations are very close, then the separation of the channels assigned to them has to be large enough. Moreover, if two stations are close (but not very close), then they must also receive channels that are sufficiently far apart. Such a problem may be modelled by L(p, q)-labellings of a graph G. The vertices of this graph correspond to the transmitters and two vertices are linked by an edge if they are very close. Two vertices are then considered close if they are at distance 2 in the graph. Let dist(u,v) denote the distance between the two vertices u and v. An L(p, q)-labelling of G is an integer assignment f to the vertex set V (G) such that:
• |f (u) − f (v)| ≥ p, if dist(u,v) = 1;
• |f (u) − f (v)| ≥ q, if dist(u,v) = 2.


As the separation between channels assigned to vertices at distance 2 cannot be smaller than the separation between channels assigned to vertices at distance 1, it is often assumed that p ≥ q. The span of f is the difference between the largest and the smallest labels of f plus one. The λ - number of G is the minimum span over all L(p, q)-labellings of G. Moreover, very often, because of technical reasons or dynamicity, the set of channels available varies from transmitter to transmitter. Therefore one has to consider the list version of L(p, q)-labellings. A k-list-assignment L of a graph is a function which assigns to each vertex v of the graph a list L(v) of k prescribed integers. Given a graph G, the list λ -number, denoted λl(G) is the smallest integer k such that, for every k-list-assignment L of G, there exists an L(p, q)-labelling f such that f (v) ∈ L(v) for every vertex v. Surprisingly, list L(p, q)-labellings have been studied only very little explicitely and seems to appear only very recently in the literature. However, some of the proofs for L(p, q)- labellings also work for list L(p, q)-labellings. Generalisations of L(p, q)-labellings in which for each i ≥ 1, a minimum gap of pi is required for channels assigned to vertices at distance i, have also been studied [11, 12]. In this PhD, these new trends of graph colorings w.r.t. channel assignment will be studied.


  Hence there are basically two main aims: the first one is to improve Fekete & Schepers’ framework for the orthogonal multidimensional knapsack problem, as depicted in Goals 1 & 2 below; the second one is to extend Fekete & Scheper’s framework to handle job scheduling problems, and more generally investigate variations of graph colorings to handle problems from discrete optimization, such as frequency assignment problems.


• Goal 1: improve Fekete & Schepers’ algorithm to decide whether a set of items fits together in a container, by using more powerful characterizations of interval graphs such as PQ trees. 

Task 1: give efficient combinatorial algorithms with the help of graph algorithms related to interval graphs

·       Task 2: give new linear-programming formulations and evaluate the associate bounds

·       Task 3: improve every algorithms/formulations by breaking symmetry issues

·       Task 4: evaluate every algorithms/formulations from Tasks 1,2 (+3) against public benchmarks

• Goal 2: comparison to other enumeration schemes for the orthogonal knapsack problem.

·       Task 5: implement enumeration scheme of Fekete & Schepers (2004)

·       Task 6: implement reduction scheme of Clautiaux & al (2005)

·       Task 7: improve algorithms from Task 5 and 6 by breaking symmetry issues

• Goal 3: obtain new relevant results in graph colorings related to the job scheduling problem, frequency assignment and network design.

·       Task 8 (periodic scheduling): exhibit suitable structural properties of circular-arc graphs in order to design an analogous framework to Fekete & Schepers’ for the periodic scheduling problem. Investigate circular-coloring and adapted coloring for the periodic scheduling problem.

Task 9 (frequency assignment): study new trends of graph colorings such as list L(p, q)-labellings to handle frequency assignment problems


[1] T. Feder and P. Hell. Full constraint satisfaction problems. SIAM J. Comput., 36:230–246, 2006.
[2] T. Feder, P. Hell, S. Klein, and R. Motwani. Complexity of list partitions. SIAM J. Discrete Math.,
16:449–478, 2003.
[3] T. Feder, P. Hell, D. Kral, and J. Sgall. Two algorithms for list matrix partition. Proc. 16th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA) 870–876, 2005.
[4] S.P. Fekete and J. Schepers. A combinatorial characterization of higher-dimensional orthogonal
packing. Mathematics of Operations Research, 29:353–368, 2004.
[5] J.E. Edmonds Maximum Matching and a Polyhedron with (0,1) Vertices J. Res. Nat. Bur. Stan-
dards, 69:125–130, 1965
[6] M.X. Goemans and D.P. Williamson Improved approximation algorithms for Maximum Cut and
Satisfiability problems using semidefinite programming Journal of the ACM, 42:1115–1145, 1995
[7] M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization.
Springer Verlag, 1988.
[8] P. Hell and J. Nesetril. Graphs and homomorphisms. Oxford University Press, 2004.
[9] P. Hell and X. Zhu. Adaptable chromatic number of graphs. European J. Combinatorics, to appear.
[10] A. Kostochka and X.Zhu. Adapted list coloring of graphs and hypergraphs. SIAM J. Discrete
Math., to appear.
[11] D. Kral Channel assignment problem with variable weights. SIAM J. Discrete Math. 20:690–704,
[12] D. D.-F. Liu and X. Zhu. Multilevel distance labelings for paths and cycles. SIAM J. Discrete Math.
19:610–621, 2005.