Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a scheduling problem in which there are multiple jobs available in the system each with a different holding cost and service time. This scheduling problem is studied previously for the case that holding cost is deterministic and known and the service time is stochastic but unknown. This paper tackles the case in which holding cost is unknown and service time deterministic/stochastic and known. Then based on some interesting motivating examples, an algorithm is proposed that starts with preemptive scheduling and after a while, it switches to a non-preemptive mode. The regret of the proposed algorithm for both deterministic and stochastic service time is obtained and by characterizing the lower bound, the authors show their policy is near-optimal. Last, there is one additional instance-dependent regret analysis that is useful when some additional information is known about jobs. Numerical experiments clearly demonstrate the improved performance of the proposed algorithms is compared to full preemptive of full non-preemptive alternatives. 
main_review: -- Overall, this paper tackles an interesting and novel scheduling problem. The new setting of unknown cost known service time is interesting and technically challenging as compared to the prior setting. The paper is well-written and clearly states its contribution and the technical part is polished and easy to follow. The only concern is about the significance of the results since it seems that the problem is very narrow and of less practical importance since typically cost is coming from the customer and is typically known while the service time highly depends on several unknown factors. Some comments are given below. 

-- This paper assumes that the service times of jobs are known but their cost is unknown. However, this difference from the prior work is not motivated properly. The other case, i.e., unknown $\mu$, known $c$ makes sense in practice since jobs typically belong to a few categories with similar properties, however, their service time is random. The case of interest in this paper, however, is not clear how it makes sense. Also, there are some additional assumptions in the model that makes the problem less interesting from a practical perspective, e.g., availability of all jobs at the beginning, known $T$, etc. In short, the authors should justify their model both from a practical perspective and also from the added technical challenges as compared to the prior work and in particular [4,5]. 

Other comments: The title of the paper is misleading, scheduling is an extremely broad topic with a huge number of variants, and using learning for scheduling is also an active topic of research both in systems and theory communities. The scheduling problem in this paper is also very narrow and not so practical, so, the authors could change the title to better reflect the concrete topic of this paper. 

-- It is not clear why the regret analysis for 2 jobs is given in the main body of the paper since the general case is also intuitive. 
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Proposed work is considering a stochastic scheduling problem where we are given a single server and a set of jobs with unknown cost profile. It is well known that when the cost profile is known Smith's rule is optimal. Using this as a baseline, the authors define a natural regret measure. The central result is algorithm with sublinear regret and a roughly matching upper bound. 
main_review: 
Proposed work is considering a stochastic scheduling problem where we are given a single server and a set of jobs with unknown cost profile. It is well known that when the cost profile is known Smith's rule is optimal. Using this as a baseline, the authors define a natural regret measure. The central result is algorithm with sublinear regret and a roughly matching upper bound. 

The key observation is that neither preemptive or non-preemptive approach to scheduling jobs in a given time instant works in general. Indeed, a completely preemptive approach would delay jobs and non-preemptive approach is susceptible to estimation errors made in the beginning. Combining a preemptive approach with non-preemptive approach, the authors propose a natural algorithm where jobs are scheduled preemptively in the beginning and later non-preemptively. In a sense, it seems like an interesting use of exploration vs exploitation in the context of scheduling jobs. 

In conclusion, a clean, well written paper with a concrete set of theoretical results. I vote for acceptance.
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper presents algorithms for the problem of ordering jobs on a machine so as to minimize the cumulative holding cost. The assumption is that the holding cost in each timestep follows a sub-Gaussian distribution (i.i.d. across timesteps), but the the mean values of these distributions for individuals jobs are unknown to the algorithm. The lengths of the jobs are known upfront, or in an extension considered later in the paper, are generated from geometric distributions whose mean values are known upfront to the algorithm. If holding costs and job lengths were both known, then the optimal strategy is to process jobs in decreasing order of the ratio of the holding cost and job length. One natural strategy would be to implement this same rule, but with estimated mean holding costs based on previous iterations. This has the advantage of not committing to any job upfront, and therefore, being able to adjust to estimation errors of the holding costs. But, this strategy has the downside that if the holding costs are similar, then it can process the jobs round robin thereby keeping all jobs in the queue longer and incurring a large cost. The alternative is to commit to a job that has the largest value of this (estimated) ratio, and this strategy works well when the ratios are close to each other but not when they are well-separated, since estimation errors can be costly in the latter case. The algorithm proposed in the paper is natural combination of these ideas: start with a learning/exploration phase where you use the former strategy thereby not committing to any job but learning their holding costs, and then in the exploitation phase, commit to the job with the largest (estimated) ratio and run it to completion. In addition to obtaining regret bounds for this algorithm, the paper also gives lower bounds on regret that can obtained by any algorithm, and does numerical experiments to evaluate the performance in practice. 
main_review: The technical work in this paper is quite good, but I am not convinced about the relevance of the specific problem model being studied here. What are situations where the holding costs are unknown but job lengths are known (at least the mean lengths are known)? The examples given at the beginning of the paper are about the relative importance (or urgency) of different jobs being unknown (and being fluid) in some situations, but they do not directly relate to unknown holding costs and known job lengths. For example, in a triage scenario, one should expect significant uncertainty in job lengths as well. Also, how general is the sub-Gaussian assumption on the holding costs? How about the assumption that if the job lengths are not known deterministically, then they should follow a geometric distribution? The paper does not make a convincing case that these are important scenarios to consider. Bereft of this explanation, the results obtained, while technically reasonable, have only limited significance in the research area. I also find the assumptions that all jobs arrive at the outset somewhat restrictive for the kind of applications being considered here. For instance, in data center scheduling or triage management, which are mentioned as motivating examples, the environment is clearly more dynamic and jobs actually arrive over time. The consideration of a static set of jobs is therefore a significant limitation of the paper. Finally, the connection with machine learning is also somewhat tenuous. One might argue that the algorithms are actually learning characteristics of the jobs over time and using them in the scheduling, but learning here basically means just observing samples and making simple estimates from them. This is a rather rudimentary form of learning. The relevance of the paper to machine learning, even in a broad sense, is limited.

I have read the authors' response (and appreciate the time and effort the authors spent in addressing all the points). The motivation of the paper is still the major point of concern. The applications described in the response appear retrofitted to the problem, rather than the other way around. The limitations, particularly the offline knowledge about jobs, also appear rather serious for the applications that this paper is targeted toward. For these reasons, my overall opinion about the paper remains unchanged. 
limitations_and_societal_impact: The authors do a good job of spelling out their technical limitations, namely that the bounds are not tight unless one assumes the job lengths to be (scaled) constants. But, as I described above, a lot more discussion is required about the modeling limitations, and why the problem makes sense in some scenarios even with these limitations.

No negative societal impact as far as I can tell.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem where jobs of unknown weights and durations drawn from some distribution are available and need to be scheduled so as to minimize the sum of their weighted completion time (the paper calls this holding time). It is well known that when weights and durations are known then the so-called Smith's rule is optimal and the same is also the case when the durations used in Smiths rule are the "mean values" of the corresponding distribution(s).

Consider that the jobs can be preempted, i.e., the algorithm can choose at each time slot the job which Smiths rule would pick by using the aforementioned "mean" duration and the so-far learned information on the weight. Then in the worst case, all jobs would have weights that are close to each other, which would result in a -- more or less -- round robin schedule that completes all jobs close to the end of the schedule resulting in unnecessary delays, and in turn also regret. 

On the other hand, an algorithm that non-preemptively picks a job and sticks to it, may select a job with an arbitrary weight first resulting in arbitrarily high regret. 

The authors propose an algorithm that runs the preemptive schedule for some time-period before then switching to the non-preemptive one. The idea is that although, and as just described, at the extreme cases when the preemptive period has length either 0 or infinity the regret increases substantially, one can carefully choose a length so as to have learned enough information about the job weights by the end of that preemptive phase (intuitively, if the non-preemptive phase still processes two jobs in the wrong order then they have similar weights so it is not too bad), while at the same time not running the preemptive phase for too long. This results in an algorithm with sublinear regret.
main_review: To the best of my knowledge the results presented in the paper are original, although they are in my opinion quite straightforward (which may actually be considered as an advantage since it results in a very simple algorithm). 

Although the paper is general very well written, I feel that some parts can be substantially improved. In particular:

1) the model is not adequately described and self contained,
2) to my understanding the "learning" part is completely hidden in the supplementary material and by reading only the paper itself, it is not completely clear how and how effectively the weights learned, and 
3) the sketches of the proofs although useful sometimes seem completely unrelated to the theorem statement. For example the sketch after Theorem 3.1 gives a two job example that essentially only implies that to keep regret as low as possible one needs to keep $T_s$ as low as possible (whereas the theorem statement naturally also considers the tradeoff between the opposing worst-case not mentioned in the "proof-sketch"). 

Most of these concerns are rectified though by looking into the supplementary material. Although I did not carefully go over every line in the proofs presented there, I skimmed over them and they seem to check out. 

(Almost) matching lower bounds are also given, and experimental results are presented which are not too surprising (essentially the algorithm is compared to the only preemptive and only non-preemptive one which are the building blocks and the sublinear regret is depicted as well).

To summarize, on the positive side, the paper studies an interesting problem and gives a simple algorithm for it along with (almost) matching lower bounds), and the writing is in general very good. On the negative side, the paper is not completely self-contained without the supplementary material, and the algorithm is quite simple/straightforward.
limitations_and_societal_impact: Yes they have.
review_title: null

Meta-review: The paper concerns online scheduling algorithm which aims at minimizing the expected cumulative holding costs incurred by jobs with a priori unknown parameters.

The reviewers found the problem tackled by the paper interesting and novel, and the framework of unknown costs challenging as compared to the prior settings. They liked the fact that the paper gives a simple scheduling algorithm whose performance (almost) matches lower bounds for the problem. The paper was also generally assessed as clear and well-written.

There were also some reservations raised, namely: the algorithm is rather straightforward, limited relevance of the specific problem considered (assumptions which might be too strong in practice).

However, the overall evaluation of the paper was mainly positive and thus I recommend the acceptance. I suggest that the authors incorporate the reviewers' remarks in the final version of the manuscript.
Decision: Accept (Poster)