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.