On-line Chain Partitioning as a Model for Real-time Scheduling
Przemysław Broniek · Electronic Notes in Theoretical Computer Science · 2005
We consider on-line chain partitioning of a poset as a theoretical model for some variant of tasks scheduling. Restricting ourselves to interval orders given by its representation the problem is equivalent to the coloring problem of interval graphs. We prove that up-growing variant of on-line chain partitioning of interval orders given by its representation has an optimal solution (Nearest-Fit algorithm). We also consider on-line chain partitioning of interval orders without representation and prove the lower bound for the up-growing version (3w/2). Moreover we show that there is no on-line algorithm constructing the representation of interval orders and graphs.