Temperature aware online algorithms for minimizing flow time. (English) Zbl 1356.68266
Summary: We consider the problem of minimizing the total flow time of a set of unit sized jobs in a discrete time model, subject to a temperature threshold. Each job has its release time and its heat contribution. At each time step the temperature of the processor is determined by its temperature at the previous time step, the job scheduled at this time step and a cooling factor. We show a number of lower bound results, including the case when the heat contributions of jobs are only marginally larger than a trivial threshold. Then we consider a form of resource augmentation by giving the online algorithm a higher temperature threshold, and show that the Hottest First algorithm can be made 1-competitive, while other common algorithms like Coolest First cannot. Finally we give some results in the offline case.
MSC:
| 68W27 | Online algorithms; streaming algorithms |
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Albers, S., Energy-efficient algorithms, Commun. ACM, 53, 5, 86-96 (2010) |
| [2] | Bampis, E.; Letsios, D.; Lucarelli, G.; Markakis, E.; Milis, I., On multiprocessor temperature-aware scheduling problems, J. Sched., 16, 5, 529-538 (2013) · Zbl 1297.68037 |
| [3] | Birks, M., Online Algorithms for Temperature Aware Job Scheduling Problems (2012), University of Leicester, PhD Thesis |
| [4] | Birks, M.; Fung, S. P.Y., Temperature aware online scheduling for throughput maximisation: the effect of the cooling factor, Sustain. Comput., Inform. Syst., 4, 3, 151-159 (2014) |
| [5] | Birks, M.; Cole, D.; Fung, S. P.Y.; Xue, H., Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints, J. Comb. Optim., 26, 2, 237-250 (2013) · Zbl 1275.90023 |
| [6] | Birks, M.; Fung, S. P.Y., Temperature aware online algorithms for scheduling equal length jobs, Theoret. Comput. Sci., 508, 54-65 (2013) · Zbl 1358.68324 |
| [7] | Chrobak, M.; Dürr, C.; Hurand, M.; Robert, J., Algorithms for temperature-aware task scheduling in microprocessor systems, Sustain. Comput., Inform. Syst., 1, 3, 241-247 (2011) |
| [8] | Dürr, C.; Milis, I.; Robert, J.; Zois, G., Approximating the throughput by coolest first scheduling, (Proc. 10th Workshop on Approximation and Online Algorithms. Proc. 10th Workshop on Approximation and Online Algorithms, LNCS, vol. 7846 (2012)), 187-200 · Zbl 1395.68069 |
| [9] | Kalyanasundaram, B.; Pruhs, K., Speed is as powerful as clairvoyance, J. ACM, 47, 4, 617-643 (2000) · Zbl 1094.68529 |
| [10] | Kellerer, H.; Tautenhahn, T.; Woeginger, G. J., Approximability and nonapproximability results for minimizing total flow time on a single machine, SIAM J. Comput., 28, 4, 1155-1166 (1999) · Zbl 0926.68014 |
| [11] | Phillips, C. A.; Stein, C.; Torng, E.; Wein, J., Optimal time-critical scheduling via resource augmentation, (Proc. 29th Annual ACM Symposium on the Theory of Computing (1997)), 140-149 · Zbl 0962.68010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
