Abstract
In this paper we consider online scheduling problems for linear topology under various objective functions: minimizing the maximum completion time, minimizing the largest delay, and minimizing the sum of completion times. We give optimal solutions for uni-directional version of the problem for each of the objectives and show that for the two-directional versions of each problem, no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions. We also propose 2-approximation on-line algorithms for the MinMakespan and the MinSum minimization objectives. We also prove that no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions for the weighted case of uni-directional scenarios.
Original language | English (US) |
---|---|
Pages (from-to) | 777-799 |
Number of pages | 23 |
Journal | Optimization Letters |
Volume | 8 |
Issue number | 2 |
DOIs | |
State | Published - Feb 2014 |
Externally published | Yes |
Keywords
- Linear network
- Online algorithms
- Scheduling
ASJC Scopus subject areas
- Control and Optimization