Energy-Efficient Scheduling with Predictions

Summary

This paper studies an energy-efficient scheduling problem under the setting of prediction. In this problem, each job has a release time and processing time. The job arrives online and the algorithm can determine the speed of the machine. The higher speed means a higher energy cost. The total energy cost integrates the speed cost over all time points. Besides the energy cost, the objective contains a job cost function that relies on the schedule. In this paper, the authors assume this cost function is subadditive to capture more applications. The schedule is defined as the speed of the machine each time. The goal is to find a feasible schedule with the minimum total cost. This paper considers the above problem under the setting of prediction, where their prediction is the release time and processing time of each job. The main contribution of this work is a learning-augmented algorithm that achieves (1+\epsilon) consistency and bounded robustness. The authors also give the ratio function depending on the prediction error. Finally, the authors verify the performance of the proposed algorithm in some real datasets.

Strengths

The submission is carefully written and structured, so reads well given the technicality of the material. Especially, the authors provide sufficient intuitions to help understand the algorithm. The proposed learning-augmented algorithm can be applied to several problems. Although one still needs to utilize the classical online and offline algorithms for each specific problem, the proposed framework provides some intuitions to show how to combine these two algorithms.

Weaknesses

I am one of the reviewers of the previous version of this paper. My previous major concerns are: (1) the authors didn’t provide a comparison of the proposed framework and the existing works, thus it is unclear how good this framework is if we apply it to some specific problem; (2) the considered problem is too general and may not admit a polynomial time algorithm. In this version, the author addresses these two points appropriately. For the first point, the authors added Table 1 to discuss four related special cases. For the second point, the authors considered the approximation ratio in the proof of Theorem 3.4.

Questions

I would appreciate it if the authors add a discussion about how to compute the error function given two instances.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This is a theoretical paper, there is no potential negative societal impact.

Summary

The authors study energy-efficient scheduling with predictions. There are already previous works on minimizing energy consumption in a setting with deadlines. The authors provide a unified way to address both the scheduling with deadlines as well as (weighted) flow time plus energy cost. It was already known that no algorithm can be both 1-consistent and robust and therefore one has to aim for a trade-off between consistency and robustness. They provide consistency and robustness trade-offs which scale roughly with (1/lambda), where lambda is the trade-off parameter. They also show a lower bound on robustness scaling with sqrt(1+1/lambda), i.e., there is still a space for improvement. They also discuss deterioration of their bounds between consistency and robustness as a function of a prediction error defined in a natural way, especially with their extension to approximately correct predictions. I did not notice any lower bounds on the dependence on prediction error, also the formula stating the dependence is not easy to understand (maybe a plot would help?). But overall, I find the contribution of this paper solid and I will be happy to see it accepted.

Strengths

they provide an unified framework for a broad range of problems in energy efficient scheduling

Weaknesses

* resulting bounds for the Deadline setting are weaker than in previous works * results not tight yet

Questions

* you could elaborate a bit on how does your competitive ratio behave as a dependency on prediction error, if possible to give a clean answer.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

* Authors stated their theoretical results formally, including all assumptions made

Summary

The paper considers speed scaling scheduling with learning augmented predictions. In contrast to previous works that considered the deadline-based version of the problem, the current paper studies a more general model that allows for different quality of service objectives to be optimised alongside the energy consumption of the schedule. These include for example the well studied total flow time objective. Similarly to other results in the learning augmented algorithms literature, the employed approach is that of combining at runtime an offline and an online algorithm for the problem. Finally, experimental results over real and sytnthetic datasets are provided.

Strengths

The biggest strength of the paper is the generality of the considered model and how it implies algorithms with predictions for a number of different speed-scaling settings. Other strengths include that the paper is well written, and obtains a clean and general framework.

Weaknesses

The prediction error is quite unnatural in my personal opinion. But going for it is that it generalizes the prediction error considered in [7]. The major weakness is that jobs are considered to be predicted correctly if the prediction for the job is 100% accurate. This is a bit unnatural and it could be argued that if the predicted parameters of every job are very close to the real ones then the predictions are adequate and should be useful. This is tackled in Section 4 (and mainly Appendix C) but to my understanding it only allows for small errors per job -- which is a weakness compared to other papers in the area in general and specifically previous papers on speed scaling with predictions. The technique employed in the paper is quite standard and I couldn't identify any really new idea. Nevertheless the results are not obvious and had to be worked out.

Questions

I am wondering if there is a way to simplify the competitive ratio formula in Theorem 3.4 -- even perhaps at a slight loss of the proven guarantee? I did check the discussion in the appendix which is helpful but still does not give a very clear picture of the obtained result.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

No conceivable limitations or potential negative societal impact.

Summary

This paper adds to the literature on energy efficient scheduling by defining an algorithm that extends the problems of "energy minimization with deadlines" and "energy plus flow time minimization" to the case where predictions about future jobs are available. The paper assumes an existing algorithm for online and offline energy efficient scheduling (wrt to a particular objective function) as well as an algorithm that makes predictions. In this case they give consistency - how far cost of the with-predictions variant deviates from the without-predictions variant - and robustness - how bad things can get when predictions are very wrong - bounds for their algorithm and compare them to existing results in the literature. They explore several other properties of these algorithms and give an extension of the algorithm to small deviations - i.e. the case where predictions don't have to be exactly correct to be considered "good". Experiments are done on two synthetic and one real (SNAP College Message) dataset.

Strengths

The paper tackles an important problem, where improved algorithms will have a positive environmental impact. The paper contributes a new bound on a problem that hasn't been studied yet. It also adds insight into previously studied variants of the problem. Relevant claims seem to be justified with proofs - although I was unable to fully check everything, but what I did check was consistent.

Weaknesses

This paper is abstract and jargon / notation heavy and will be difficult for someone without deep familiarity with the problem domain to read. On place that I had trouble were understanding how speed is assigned to a job. The variable lambda is prominently used, but is not given an intuitive definition until line 195. I would like to see a definition of this "confidence level" variable nearby where the intuitive definition of alpha is given. Around line 196, I would like to see examples or citation of what some of these ONLINE and OFFLINE algorithms are, as well as an example of or reference to an algorithm for prediction. Line 29: Replacing: "is equal to speed to some power" with "is equal to speed *raised* to some power" would make this easier to understand. It does make sense as-is, but the added clarification would have helped me. Line 174: Using eta as a function and a numeric variable is confusing.

Questions

I don't understand on line 162, prediction error is defined with an alpha-norm, but perhaps reading the relevant citation more carefully could help there. I'm wondering about the assumption that the speed of the machine is equal to the sum of the speeds of all jobs currently executing. Is overhead from context switching / cache misses negligible in real life, or is this just a simplification for theoretical analysis? Have the authors considered codifying their proofs in proof assistant software (e.g. Lean, Coq)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The discussion is sufficient.