Energy efficient scheduling and routing via randomized rounding

Prelegent: dr Alexander Kononov (Instytut Sobolewa Rosyjskiej Akademii Nauk, Nowosybirsk)
Miejsce: Sala A1-33/34
Data i godzina:  16 września 2014 r., g. 12:00

Abstract: Based on configuration linear programs and randomized rounding, we propose a unifying framework for different energy optimization problems in the dynamic speed-scaling setting and apply the framework to various scheduling and routing problems in heterogeneous computing and networking environments. First, we consider the energy minimization problem of scheduling a set of jobs on a set of
parallel speed-scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Next, we show that our approach allows us to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem, where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized, improving the best known approximation ratio for this problem.

 

Scheduling problems with unreliable jobs and machines

Prelegent: prof. Alessandro Agnetis (University of Siena, Włochy)
Miejsce: Sala A1-33/34
Data i godzina:  15 listopada 2012 r., g. 12:00

Abstract: In this talk we address a relatively novel class of scheduling problems, arising in various different contexts, in which jobs are characterized by a certain revenue (if successfully carried out) and a certain chance of success. If a job fails, the corresponding machine is blocked and no further job can be executed. The problem is to allocate and sequence the jobs on m parallel, identical machines in order to maximize expected revenue. For this problem, which is strongly NP-hard, we give some approximation results for the case m=2, and discuss the special case in which machines fail according to an exponentially distributed random process.

Scheduling dependent shortening jobs

Prelegent: Stanisław Gawiejnowicz
Miejsce: Sala B1-38
Data i godzina:  3 czerwca 2008 r., g. 12:30

Abstract: We consider the problem of scheduling a set of n jobs on a single machine. The processing time of each job depends on its starting time and becomes more short linearly. The objective is to minimize the maximum completion time. We show that if precedence constraints among the jobs are in the form of a set of chains, a tree, a forest or a series-parallel digraph, the problem is solvable in O(n log n) time.

New scheduling problems

Prelegent: dr Alexander Kononov (Instytut Sobolewa Rosyjskiej Akademii Nauk, Nowosybirsk)
Miejsce: Sala B1-33/34
Data i godzina:  4 kwietnia 2006 r., g. 12:00