Xuding Zhu, "Graph Theory model for scheduling problems"

Salle 5  -  190 avenue de France  -  75013 Paris

Xuding Zhu (Zhejiang Normal University ,Jinhua, Chine), invité par l'école du 21 mai au 21 juin,  fera un exposé dans le cadre du séminaire « La question de la modélisation en sciences humaines : mathématiques et informatique » qui se tiendra la Vendredi 15 juin de 15h à 18h en salle 5.

Graph Theory model for scheduling problems

Scheduling is the process of deciding how to commit resources between a variety of possible tasks. A typical phenomenon is that there are conflicts between pairs of tasks that forbids them to share a resource. In this case, graphs provide an ideal model for the problem. Vertices represent tasks, and two vertices are connected by an edge if there are conflicts between the corresponding tasks. The scheduling problem is usually to optimize some parameters, which become optimization problems on graphs. For example, in a parallel computation model, a set of processes make computations on a set of data files. Each process accesses some data files. Two processes sharing a same data file cannot operate at the same time. The scheduling problem is to assign time units to processes so that conflicting processes do not operate at the same time, and each process operate roughly the same number of units and under these restriction, optimize the efficiency of the computation. This problem turns out to be circular coloring of graphs. In this talk, we shall explain how this graph parameter is related to various scheduling problems, its relation to other graph parameters, and survey some results on the study of this graph coloring concept.

  • le vendredi 15 juin 2012  de 15h  à 17h

Haut de page