Surface light-induced changes in thin polymer films
Andrew Skumanich
SPIE Optics Quebec 1993
We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O(k)-competitive for k weight classes. This implies an O(log W)-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O(log n + log P)-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + ε)-speed, (1 +1/ε)-competitive online algorithm.
Andrew Skumanich
SPIE Optics Quebec 1993
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989
Heng Cao, Haifeng Xi, et al.
WSC 2003