Scheduling jobs with stochastic holding costs
Authors: Dabeen Lee
Milan Vojnovic
Venue: NeurIPS 2021 Poster (2021)
Keywords: scheduling
stochastic holding costs
scheduling while learning
$c\mu$ rule
empirical $c\mu$ rule

Abstract: This paper proposes a learning and scheduling algorithm to minimize the expected cumulative holding cost incurred by jobs, where statistical parameters defining their individual holding costs are unknown a priori. In each time slot, the server can process a job while receiving the realized random holding costs of the jobs remaining in the system. Our algorithm is a learning-based variant of the $c\mu$ rule for scheduling: it starts with a preemption period of fixed length which serves as a learning phase, and after accumulating enough data about individual jobs, it switches to nonpreemptive scheduling mode. The algorithm is designed to handle instances with large or small gaps in jobs' parameters and achieves near-optimal performance guarantees. The performance of our algorithm is captured by its regret, where the benchmark is the minimum possible cost attained when the statistical parameters of jobs are fully known.  We prove upper bounds on the regret of our algorithm, and we derive a regret lower bound that is almost matching the proposed upper bounds. Our numerical results demonstrate the effectiveness of our algorithm and show that our theoretical regret analysis is nearly tight.

Scheduling jobs with stochastic holding costs
Dabeen Lee Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon, South Korea dabeenl@ibs. re. kr
Milan Vojnovic
Department of Statistics London School of Economics London, United Kingdom wow.oviillsse.e..oooo ac uk
Abstract
This paper proposes a learning and scheduling algorithm to minimize the expected cumulative holding cost incurred by jobs, where statistical parameters defining their individual holding costs are unknown a priori. In each time slot, the server can process a job while receiving the realized random holding costs of the jobs remaining in the system. Our algorithm is a learning-based variant of the cy rule for scheduling: starts with a preemption period fixed length which serves as learning phase, and after accumulating enough data about individual jobs, it switches to nonpreemptive scheduling mode. The algorithm is designed to handle instances with large or small gaps in jobs' parameters and achieves near-optimal performance guarantees. The performance our algorithm is captured by its regret, where the benchmark is the minimum possible cost attained when the statistical parameters of jobs are fully known. We prove upper bounds on the regret of our algorithm, and we derive regret lower bound that is almost matching the proposed upper bounds. Our numerical results demonstrate the effectiveness of our algorithm and show that our theoretical regret analysis is nearly tight.
Introduction
We consider the following algorithmic question: given a list of jobs, each of which requires a certain number of time steps be completed while incurring a random cost in every time step until finished, learn the relative priorities of jobs and make scheduling decisions of which job to process in each time step, with the objective of minimizing the expected total cumulative cost. Here, we need an algorithm that seamlessly integrates learning and scheduling.
This question is motivated by several applications. Online social media platforms moderate content items, and here, jobs correspond to reviewing content items while the jobs have random costs driven by the number of accumulated views views of harmful content items represent community- -interrgtty cost. Then the content review jobs are prioritized based on popularity of content items (18). More generally, modern data processing platforms handle complex jobs whose characteristics are often unknown in advance [TO. but as a system learns more about the jobs' features, it may flexibly adjust scheduling decisions serve jobs with high priority first. Another application consumption of servers in data centers, where a job waiting to be served uses energy consuminng resources [3] 77. In emergency medical departments, patients undergo triage while being treated, and schedules for serving patients are flexibly adjusted depending on their conditions [15) Note that patients' conditions may get worse while waiting, which corresponds to holding costs our problem. For aircraft maintenance, diagnosing the conditions of parts and applying the required measures to repair them are conducted in a combined way
optimizing energy
We model and study the problem as a single-server scheduling system where job holding costs according stochastic processes with independent and identically distributed increments with unknown mean values, under the assumption that their mean service times are known. Recent works,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

e.g. [5], started investigating queuing system control policies under uncertainty about jobs' mean service time parameters. but restricting the setting where job holding costs are assumed to be deterministic (linear) functions of stochastic job waiting times. In our problem setting, job holding costs are stochastic in a different way in that job holding costs themselves are according to some stochastic processes. Under the aforementioned application scenarios, it is more natural to model a job's holding costs by a stochastic process, As the first step towards understanding the setting of stochastic job holding costs, we consider single-server scheduling with fixed list of jobs.
Since the statistical parameters quantifying the random holding costs of jobs are unknown to the decision-makes maker, the main challenge is to learn the parameters of jobs, thereby obtaining near- accurate priority ranking jobs to find a scheduling policy minimizing the total accumulated cost.
Problem formulation
We consider a discrete-time scheduling with a single server and N jobs. The jobs, labelled by i i.l,...; NN, are present the system from the beginning, and we assume no further job arrivals. Every job remaining in time slot incurs a random holding cost at the beginning of the time step, and holding costs incurred by a job are according to a sub-Gaussian distribution and i.i.d. across time slots. Bub-Gaussian distributions allow for different parametric distributions, e.g. Bernoulli and Poisson, which are suitable for modeling jobs incurring random costs incrementally. The mean holding costs of jobs are given by Ci..... CN whose values are a-priori unknown. The number of required time steps to complete job i is given deterministically by T/P4 for each where T is a scaling parameter. Note that the larger the value of T the larger the number of per-job stochastic cost observations. The larger value of T does not necessarily mean that mean job service times are large in real time. In addition to the case of deterministic job service times, we also consider the case of stochastic job service times, assumed to be according to geometric distributions, which a standard case studied in the context of queuing systems.
We analyze the performance of our scheduling policy against the minimum (expected) cumulative holding cost that can be achieved when the jobs' mean holding cost values are fully known. The famous cp rule, which sequentially processes jobs in the decreasing order of their ejt, values, is known to guarantee the minimum cumulative holding cost, so we use this as our benchmark. Assuming C1 2 02/l2 2 ... 2 CN pN, we can define the regret of a scheduling algorithm op as
R(T) = C(T) Σ SE[N]
Σ T/ps JEMI
where C(T) is the expected cumulative holding cost of s, i.e., denoting the completion time of job and the second term on the right-hand side is the minimum expected cumulative holding cost, achievable by the ep rule. Note that R(T) is a random variable, as it may depend on randomness in the algorithm şp. We will consider EE [R(T)), the expecied regret of the algorithm. When c,'s 's and μ4 's are constants, the minimum cumulative holding cost is O(NTT). Here, our goal is to construct policy whose expected regret is sublinear in T and subquadratic in N.
T.T with T.
Previous work [5] has focused on the case when the values of p1...., MN are unknown while the values of C1. c1....e CN are known. As the service time of a job is instantiated only after completing it, this work relies on assumptions that there a fixed list of classes and multiple jobs may belong the same class, which means that each μ4; can take one of few values. In contrast, our paper is focused on addressing the challenge of uncertain costs. Our framework allows jobs to differ from each other (equivalently, each job corresponds to a unique class), but to make learning distinct jobs possible, we assume that the factor the service times is large. We can think of the large T regime as the case where the jobs' features are observed frequently, as well as the setting of long job service times.
Our contributions
We develop our algorithm based on the empirical ep rule, that is, the cu rule applied with the current estimates of the mean holding costs. Since the ranking of jobs based on the cj,f values, where &,, denotes the empirical mean of job i's holding cost time slot I, may change over time, is natural to come up with two types of the empirical сμ rule, preemptive and nonpreemptive. Under the preemptive empirical ep rule, the server selects job for every single time slot. contrast, under the nonpreemptive version, once a job is selected in a certain time slot, the server has to commit to

---

serving this job until its completion, and then, it may select the next job based on the empirical en rule. The preemptive empirical eμ rule works well for instances with large gaps between the jobs' mean holding costs, whereas the nonpreemptive one is better for cases where the jobs' mean holding costs are close. However, it turns out that, under both the preemptive and nonpreemptive cases, the expected regret can grow linearly in 7 in the worst case. The preemptive case may result in undesired delays especially for jobs with similar values, while the nonpreemptive case may suffer from early commitment to job with low priority.
Our policy, the preemptive thee--hheeeee nonpreemptiee empirical qu rule, basically a combination of the preemptive and nonpreemptive empirical ey rules. This variant of empirical oji rule has a fixed length of preemption phase followed by nonpreemptive scheduling of jobs. The preemption period is long enough to separate jobs with large gaps in their mean holding costs, while it is not too long so that we can control delay costs from the preemption phase to be small, thereby avoiding undesired delays from continuous preemption and the risk of early commitment.
In Section 3 we give theoretical analysis of our algorithm for the case of deterministic service times. We prove that the expected regret of our empirical ep rule is sublinear in I' and subquadratic in N. We also show that this is near-optimal by providing a lower bound on the expected regret of any algorithm that has the same scaling in T while there is a small gap in terms of the dependence on N. Furthermore, we give instance- dependeent upper bounds that delineate how our algorithm performs depending on the gaps between Cjfl, values. In Section 4 time of each job stochastic and geometrically distributed. Our analysis reveals that the expected regret of our algorithm for the case of geometrically distributed service times is also sublinear in T and subquadratic in N. Lastly, in Section [S] we discuss results from numerical experiments that demonstrate our algorithm's 's performance and support our theoretical claims.
we consider the setting where the service
2
Related work
The scheduling problem asking to minimize the sum of weighted completion times for a given set of jobs, with weights e; and processing times 1/H,, was studied in the seminal paper by Smith [13, who showed that serving jobs in decreasing order of indices C,j4 is optimal. This policy is often referred to as the Smith's rule. This policy corresponds the weighted shortest processing time first (WSPT) policy in the literature on machine scheduling. The Smith's 's rule is also optimal for the objective of minimizing the expected sum of weighted completion times when job processing times are random with mean values 1/44. We refer the reader to [1] for a comprehensive coverage of various results.
Serving jobs by using eap; as the priority index is known to be an optimal scheduling policy for multi-class, single-server queuing systems, with arbitrary job arrivals and random independent, geometrically distributed job processing times with mean values 1/p: [2]. This policy is commonly referred to as the eu rule. A generalized cu rule is known to be asymptotically optimal for convex job holding cost functions in a heavy-traffic limit, where the generalization corresponds to using a dynamic index defined as the product of the current marginal job holding cost and the mean processing time of job [7]. This generalized ou rule is also known to be asymptotically optimal in a hravy-traffic limit for multi-server queuing systems under a certain resource polling condition [9].
The work discussed above on the performance of Smith's 's or eμ rule assumes that the values of marginal job holding costs and mean processing time parameters are known to the scheduler. Only some recent work considered the performance of these rules when some of these parameters unknown. In the line of work on scheduling with testing (6 15). marginal job holding costs and mean processing times of jobs are a-priori unknown, but their values for a job become known by testing this job. The question there is about how to allocate the single server to processing and testing, which cannot be done simultancously. The optimal policy combines testing the jobs up to certain time and serving the jobs according to the eμ rule policy. In [5), multi-class queuing system is considered under the assumption that mean job processing times are unknown to the scheduler. The authors established that using the empirical сμ rule in the single-server case guarantees a finite regret with respect to the eu rule with known parameters as a benchmark. Similar result is established for the multi-server case by using the empirical eμ rule combined with an exploration mechanism. Unlike (5) our setting, each job corresponds to a unique class, so an exploration phase is required for each job. The preemption phase in our algorithm is for exploration within each job.
3

---

Finally, our work is related to permutation or learning to rank problems, e.g. see 4 8 and the references therein, where the goal is to find linear order of items based on some observed information about individual items, or relations among them. Indeed, the objective of our problem can be seen as finding permutation π that minimizes the cost function Ei=1 iCz(s), for the special case of identical mean processing time parameter values. For example, we may interpret e; as a measure of dissimilarity between item i and reference item, and the goal is to sort items in decreasing order of these di dissimilarity indices. The precise objective is defined for a sequential learning setting where irrevocable ranking decisions for items need to be made over time and the cost in each time step is the sum of dissimilarity indices of items which are still to be ranked.
3 Algorithm and regret bounds
Before we formally describe our algorithm, consider the case of N = 2 and μ* = μ22 1 for motivation. Without loss of generality, let us assume that C1 2 cg. Then processing job 1 first and job 2 next is optimal, and the minimum expected cost is c₁ T + C2 27. Recall that the empirical cy rule selects whichever job that has a higher estimated mean holding cost while the preemptive and nonpreemptive versions differ in how frequently such selections made.
The preemptive version is more flexible in that scheduling decisions may be adjusted in every time slot as the empirical estimates of and e2 are updated. This is indeed favorable when ej is much greater than c2, in which case, the empirical estimate of 6j would get significantly larger than that of 02 soon. However, we can imagine situation where 01 and 02 so close that the empirical estimates of C1 and C2 are almost identical for the entire duration of processing the jobs. Under this scenario, the two jobs are chosen with almost equal probabilities, in which case, they are completed around the same time. For example, job stays in the system for 27 time periods, while job 2 remains for 27 time steps. Then the regret is T 02, which may be linear in T.
The issue that both jobs may remain in the system and ineur holding costs for the entire duration of service 27.. In contrast, one job leaves the system after T time steps under the optimal policy. Therefore, there is an incentive in completing one job early instead of keeping both jobs longer.
Inspired by this, we could consider the nonpreemptive version that selects a job in the beginning and commits it. However, under the nonpreemptive version, the probability job 2 being selected first is at least (1 c1 Jo2, and therefore, the expected regret of this policy is at least (1 c1 c1)c2 (cI T as (c1 ) (c) 2T + e²T)- (c, + C2 22'). When C C2 (1)... the expected regret is linear in T. Hence, the nonpreemptive version may suffer from undesired early commitment.
empirical ej rule, is combination of the above two policies. As the preemptive version, we start with preemption phase in which the server may try different jobs while learning the mean holding costs of jobs, thereby circumventing the early commitment issue. At the same time, we limit the number of preemption steps, which allows avoiding the issue of letting job stay in the system undesirably long for the case of jobs.
Our algorithm, which call the ceaemppivettee--nnnreeeepp
Algorithm 1
empirical cp rule
Require: T. is a predetermined length of the preemption period. J + [N].
(Preemption phase) For each time step E [Ta]. select and serve job in arg maxeeN1 GicMis. (Nonpreemptive phase) While J is nonempty, select and complete a job j in arg maxeJ C where t is the current time step index. Then J t J \ {i).
After the preemption period, we process jobs nonpreemptively. which means that once a job is chosen, we commit the server to the job until it is done. If a job has a significantly higher empirical estimate than the others, then we can easily choose the job. Even if not, still stick to a job regardless of whether the job turns out to be of lower cost than others later. Our algorithm's 's performance heavily depends on the length of the preemption phase, denoted T., which we will decide later in this section.
3.1 Regret upper and lower bounds
Recall that a random variable X with mean e is nab-Gaussian with parameter a if i[X xx) < exp(o²X² x²/2) for all X e R. Note that if X is sub-Gaussian with parameter o, then for any o' 2 it

---

is sub-suussuttee Gaussian also with parameter o'. Moreover, if X is sub-Gaussian with parameter a, then X/3 sub- Gaussian with parameter o/ for any 0. As the total holding cost depends linearly on C1,... ,C,, we may assume that c; E [0, and Ø; = 1 for i E [N] without loss of generality.
Special warm-up case: two jobs We start with the setting of N and μ1 = p2 1. When ei and are almost identical, Algorithm[] [ would spend almost equal numbers of time steps for the jobs during the preemption phase. This means that the job with the higher holding cost is delayed for T./2 time steps, in which case, we can argue that the (expected) regret is linear in T.. Hence, to attain a regret upper bound that sublinear T, we need set T. to be sublinear T. On the other hand, we would want to have a sufficiently long period for learning the jobs to avoid the issue of carly commitment to the job of less priority. In fact, setting
T, = K 7 2 (log T)1/3
for some constant K > minimizes the expected regret when N 2 and μ1 #2 = Theorem 3.1. The expected regret of Algorithm 1 for 2 jobs O(T, + T (VIIITTVIIITT /lo((T/T.)) When T. = O(T2//(8 3)3/),, the expected regrel is OTT2/3 (log 1)3/))
us give proof sketch here. The worst case that gives rise the regret upper bound in Theorem 3. occurs when 01 and 02 are so close that the algorithm selects job 2 after the preemption phase with nonnegligible probability, in which case, jobe is completed first. In such case, job 1 stays in the system for the entire duration of 21" time steps, while job 2 may spend up to T. + T time slots depending on how many times job 1 is chosen during the preemption phase, which results in delays for job 2. Then the corresponding regret is (c) 2T + 02 (T, + T)) - (cIT C2 22-) = c2 + (ci -c2)T. Here, C C2 is sufficiently small, for otherwise, 61,7++1 would be significantly larger than 02, with high probability.
turns out that there a matching lower bound on the expected regret of any policy (up to a log T factor), implying in turn that Algorithm with T, O(T (log (logT)) /3) is asymptotically optimal.
Theorem 3.2. There is a family of instances, under which the expected regret of any fixed (random- ized) scheduling algorithm is (2 where the expectation is taken over the random choice of an instance and the randomness in holding costs and the algorithm.
Our proof of Theorem 3.2 is similar in spirit to the standard argument for proving regret lower bounds for the stochastic multi-armed bandit (MAB) problem. Basically, when the mean holding costs of two jobs are very close, we can argue based on the Kullback-Leibler (KI.) divergence that no algorithm can tell which job has the higher mean holding cost with high probability for the first few time steps (see (12). The difference is that every job incurs a cost simultancously, unlike the MAB setting where only the arm played generates a reward, and that jobs leave after some number of time slots.
General case: arbitrary number of jobs We are interested in the setting where T large and the asymptotic regret analysis of Algorithm with respect to T. Hence, we focus the case where Mi....,, AN are fixed constants, but the following condition sufficient for our analysis.
Assumption. 14; I (T/log(NT)) 1/3 /2 for i E [N].
Up to scaling, we may also assume that j41,-.- JAN 2 1 without loss of generality. We further assume that T/Ps, for i E [N] are all integers. If T//u is not an integer for some i, one may assume that the service time of job i is [T/M]] since job needs "at least" this many time steps to be completed.
For the general case, we set the length T3 of the preemption period
T, = K (T/Mmin>> 22/ (2og( (log(N//)))))) /m (N)m)N)
for some constant > O where Muni min {M, : i e [J]]. We assume that N is small enough so that T, = o(T). Moreover, by the assumption, we may assume that T, S T T/214 for all i.
Let us briefly elaborate on why nonpreemptive scheduling makes sense after the preemption period even for the general case. We explained in the previous section that for the case of two jobs, there is an incentive to finish one job early because keeping both jobs long results in a large regret. The same idea applies when there are many jobs, so after the preemption period, we choose a job and complete it. After finishing the first job, denoted k each of the remaining N jobs would have
5

---

spent at least T/p4- T3 2 T/2pk time steps in the system, from which we would have collected "enough data" to learn the mean holding costs of the jobs. Here, what we mean by enough data is that (we will prove later that) the absolute error in the estimation of each job's mean holding cost is O(1/VT) with high probability, so the regret while serving the other N - 1 jobs scales as the rate of O(VT), which is less than 72/3_ Hence, the dependence T becomes not as critical, in contrast to the period for serving the first job. Then it is intuitive to complete one job by one as soon as possible so that we can quickly reduce the number of remaining jobs in the system. We will explain these details while analyzing the expected regret of Algorithm [
Let Pmaxx = max {1z : i E [M]].
Theorem 3.3. The expected regret of the preemptive then noneeeeoprreemiivve empirical op rule is
O (NTT/Mmi //Ti)//))// (log( ( / 1/3 + Pmaxx/ Dimax/Pminn/ (T/ 1/2 (Iog(NT) (Mmin) /2)
In partieular, when -1....y JAN are fixed constants, the expected regret is
E (R(T) = max { ( N3/2T1113)
(1)
where Ô hides additional logarithmic factors in NT.
Our argument is more involved for the general case than the case of two jobs. We argue that the preemption phase results in (NT,, regret due to job delays. Moreover, we analyze the regret due to the possibility that the algorithm finishes the jobs in a completely different order from the optimal sequence. Nevertheless, we use a technical lemma to compare the optimal cost and the cumulative cost from any sequence, and the key idea is that whenever a pair two jobs is reversed, we can argue that the mean holding costs of the two jobs are close.
turns out that this regret upper bound is near-optimal. We next provide a lower bound on the regret of any algorithm that matches the upper bound up to small gap in the dependence on N. Theorem 3.4. For any (randomized) scheduling algorithm, there a family of instances under which
E [[((T) Ω maxx/ {
1/3 mnin " 22/3T2/3 Mminl -3/2 NTT/2))
where the expectation is taken over the random choice of an instance and the randomness in holding costs and the algorithm.
By Theorem 3.4 when Pl,.... PN are constants, there exists a family of instances under which
B [[R(T) S (max { (22/312/3 NTT/1))
for any algorithm. Between and (2) there are small gaps with respect to the dependence on N.
Our proof of Theorem 3.4 is similar to the KI. divergence- argument for the MAB problem, but the key difference is that we observe the realized costs of all jobs, unlike the MAB setting where we observe the reward of at most arm. Morcover, jobs leave the system at some points under our setting, and we also need to deal with the costs incurred by all jobs currently in the system.
3.2 Instance-dependent regret upper bounds
The upper and lower bounds on the expected regret in the previous section are independent of the values of c,,...,oy. However, it intuitive to expect that Algorithm [ performance depends on the gaps between the values of c1/41, ..., CNJUN it would be difficult to separate jobs i and j with ej14; and Cgtl being close. Motivated by this, we give regret upper bounds that have an explicit dependence on the gaps between C1 ..., CNNN.
For the case of N 2, the expected regret depends on the quantity A, defined as,
A = |ci4 - (2/22/(p1 + 42)
that captures the gap between 61/4 and 02/22-
Theorem 3.5. When N = 2 and Mmin = min {M1, u23, the expected regret of Algorithm 1
E [[((T)] = =
log Log(TT/Hmia)
A

---

Note that the expected regret scales with a rate of A but the dependence on T is logarithmic for fixed A. For the general case, we consider the gap between ei and the other 63/4 values. Let Amin and max be defined as follows:
min ==
=min (|I - cupil/(m1 p.)), Amax = max flamp -C/4il/(1 + +c)) if1
1+1
Theorem 3.6. For general N, the expected regret of Algorithm is
E [[((T)] = ((4) N
Mmax
Amxx
N +
Mmax Mmin
N3/22
log(NT) ( (mini
log(
min
Mmin
A3 min
Amin
When M1.... PNN constants,
E [R((T) [
(0(
A
Amxx
Na/2) log(NT))
N+
N +
A2 min
A3 min
A
Recall that 14 2 1 for all E [N] and max S 1. Notice that the upper bound has a logarithmic dependence on T when the gaps between C1/1, CNNN are fixed. On the other hand, the largest factor in N is still 22/3 in the instance eetaace-independeee upper bound (I)
4 Stochastic service times
What is described in Algorithm 2 is an extension of Algorithm to the case of stochastic service times. We assume that for i E [N]. the mean of job i's service time is given by //; and known the decision-maker. This incorporates the setting of deterministic service times as a special case. Unlike the deterministic case, some jobs may be finished during the preemption phase in the stochastic case.
Algorithm 2 Preemptive- theeeettheneeee nonprcemptive empirical ep rule for stochastic service times
Require: T, is a predetermined length of the preemption period. <- [N].
(Preemption phase) For each .,................... Ts, select and process a job j in arg maxie Ci, If j is completed, update + J (i).
(Nonpreemptive phase) While J is nonempty, select job in arg maxiej 2, where / the current time step index.
Then keep processing job j until j is completed and update J J J {5}.
We prove that when the service time each job is geometrically distributed, the expected regret of Algorithm 2 can be still sublinear in T and subquadractic in N. The probability that each job i is completed when is served a time slot is pa/T. For this setting, we set T, as
T. 22/ /mmm (log(NT) (NT) (m
for some constant & > 0. Based on the memoryless property of the geometric distribution, we obtain the following regret upper bound.
Theorem 4.1. When the service time of each job is geometrically distributed with mean pa/ IT, the expected regret of Algorithm 2
B(R(T)) (T5/3(T/ (min)//m) 2/3 (NT/ (No((N)/mmin))
Compared to (1) and the upper bound given by Theorem 3.3 for the deterministic case, (3) has the
same scaling in T while has an additional N2/3 factor. Although we think that there is still a room for improvement in the regret analysis of Algorithm 2 it is interesting that the bound 3 already achieves the 72/3 scaling and subquadratic dependence on N.
5 Experiments
We run experiments to assess the numerical performance of the empirical cu rule. We test the efficiency of Algorithm compared to the preemptive empirical ep rule

---

and the nonpreemptive version. We also evaluate the tightness of the proposed upper and lower bounds on regret by measuring how the expected regret behaves function parameters N and T for ran- domly generated instances. Our code for running experiments and obtained data are publicly available bettts:///gthhi www/learninge.eeeeeeaecaaeaceome to- -o-aamminng----scculllleeeeeeeee wwwechheleeeeeerneeeeeeeeeeeeeee
to schedule, All experiments are conducted on an Intel Core i5 3GHz processor with 6 cores and 32GB memory.
Figure shows the first set of results for comparing Algorithm I against the preemptive and nonpre- for i E [M], and C1,..., cN being sampled from the uniform distribution on [0.5 E, 0.5 + E), where E is a parameter that we vary. For each value of E, we generated 100 instances, and for each of which, we recorded
emptive versions. For Figure | we used instances with N 20, T' 2000,
20000
smangeve
perprcomstive
Relative regret
0.10
0.08
prectpptee the wereeeeeeee
prestppree ncrpmemphee
Regres
15000
0.06
10000
0.02
0.2
Figure I: Comparing the three versions of the empirical ey rule for the case of deterministic service times and equal service times: (left) regret and (right) relative regret.
the expected regret of each algorithm where the expectation taken over the randomness in holding costs. The first plot in Figure depicts how the (expected) regret changes by varying the value of and the second plot shows the (expected) relative regret, defined as the regret divided by the minimum expected cumulative cost. As expected, the preemptive version suffers for instances of small e where the mean holding costs of jobs are close to each other, whereas the nonpreemptive ep rule's 's regret does seem to increase for instances of large where there may be large gaps between the jobs' mean holding costs. Compared to these two algorithms, our preemptiv--the-nnnnge teree-tteennoopremptieee empirical ou rule performs uniformly well over different values of This trend continues even when jobs have
800
preemppive nerpmemathe
prestipéee
Regre:
600
Relative regres
precrpptie gereeeeeeeeeeeee
nerpremmpher
400
0.04
200
0.02
0
0.00
0.1
0.2
0.5
0.1
0.3
Figure 2: Comparing the three versions of the empirical ep rule for the case of deterministic and heterogeneous service times: (left) regret and (right) relative regret.
heterogeneous service times. For the second set of results, we used the same setup as in the first ex- periment, but following [16), we sampled the mean service times "iii....TT/y... using translated (heavy-tailed) Pareto distribution so that T μ4: 2 100 for i E [N]. More precisely, for each T/p, we sample number z; from the distribution with the density function f(x) Z
os), d.7 for
and then, we set T/M, = 99 + [ Here, the density function corresponds to the Pareto distribution with shape parameter 0.7 which has infinite mean. As assumed that each T/p, is an integer, take [. to which we add 99 to ensure that T 144 is at least 100. Figure 2 shows that our algorithm achieves small regrets for all values of E even for the case of heterogeneous service times.
To examine how the expected regret of A Algorithm T grows as a function T, we test instances with N = 20 and different values of T from 20 to 1,000,000. To understand how the expected regret depends on N, we also run experiment with instances with T 1000 and different values of N from 2 to 1000. For both experiments, we set μ, 1 for i E [N] and e = 0.001, and the reason for this choice is that the family of instances used for providing the regret lower bound (2) have jobs
According to [16]. Google's s 2019 workload data shows that the resource- -ouus, corresponding to the service times, of jobs follow the Pareto distribution with shape parameter 0.69 (see Figure 12 in (16).
8

---

whose mean holding costs are concentrated around 1/2 when = for E [N]. For each setup, we generated 100 random instances by sampling ci..... ON from [0.5 E, 0.5 + E) uniformly at random. The left of Figure 3 is the log-log plot delineating the regret's dependence on T. The plot is
10a
10a
10
Regret
10a
10"
10a
10a
10
101
N
Figure Examining how the regret grows as function of T (left) and N (right).
almost linear, and its slope is roughly 3.4/4.9 0.69, which is close the exponent 2/3 for the T factors in both the upper bound (1) and the lower bound (2). The right of Figure is the log-log plot showing the regret's dependence on N. As the left one, the plot is also almost linear, and its slope is approximately 4.1/2.9 9 = 1.41. This result suggests that the upper bound (T) is close to being exact and that there may be larger room for improving the lower bound (
6 Conclusion and future work
This paper proposes and studies the problem of finding a learning and scheduling algorithm to find a schedule of jobs minimizing the expected cumulative holding cost under the setting that statistical parameters defining individual jobs' cost functions are unknown priori. We develop our algorithm learning- -base variant of the well-known ep rule for scheduling. The algorithm can be viewed as a combination of preemptive and nonpreemptive scheduling in the sense that it starts with a preemption phase that allows learn enough about the jobs' cost functions, and then schedules jobs nonpreemptively. We provide a regret analysis of our algorithm where the benchmark is the minimum possible cumulative holding cost that is achievable only when the statistical parameters of jobs are fully known. We give bounds on the expected regret of our algorithm for both the case of deterministic service times and the setting of geometrically distributed stochastic service times. Lastly, we provide numerical results that support our theoretical findings.
Our theoretical analysis reveals that the algorithm achieves near- netr-optimal performance guarantees, but the results rely on the assumption that the parameters ,i...., HAN are constants. More precisely, when there are large gaps between the parameters, the upper and lower bounds provided in this paper have a large gap. Moreover, we also assumed that 14 are sufficiently small to ensure that the preemption period's length is smaller than the minimum service time of job. Hence, we leave as an open question to provide matching upper and lower bounds on the expected regret of the weemmpiiv-ttee-nnnppeee
empirical ep rule for the case of large gaps Mi....,
Another open question concerns the case of geometrically distributed stochastic service times. Although we have proved that the expected regret of algorithm is sublinear in T and subquadratic in N, we think that there exists a more refined regret analysis. Our argument is based on the observation that the jobs remaining after the preemption phase will have generated T,, instantiated holding costs. However, as the service times jobs are stochastic, the number of observations for a job is also a random variable, but we could not take this into account in our analysis.
One may also consider some variations our problem by allowing for partial or delayed feedback. We can imagine situation where the learner observes stochastic holding costs only for subset of items in each time step, or another scenario is when there are some delays in receiving realized holding costs so that the learner observes only accumulated costs of jobs over multiple time steps. This may be of interest in real-world systems where only a limited information about stochastic holding costs is accessible by the learner due computation communication constraints in each time step.
Lastly, it is left for future work to study cases when both mean job holding costs and mean job service times are unknown parameters. [5] considers unknown mean service times, whereas our work studies the case of unknown mean job holding costs. Combining these two frameworks would be of interest.

---

Acknowledgments and Disclosure of Funding
This research is supported, in part, by the Institute for Basic Science (IBS-RO29-CI, Y2) and the Facebook Systems for ML Research Award.
References
[1] Saed Alizamir, Francis de Véricourt, and Peng Sun. Diagnostic accuracy under congestion. Management Science, 59(1):157-171, 2013.
[2] C. Buyukkoc, P. Varaiya, and Walrand. The ep rule revisited. Adv. in Appl. Probab., 17(1): 237-238, 1985.
[3] Miyuru Dayarathna, Yonggang Wen, and Rui Fan. Data center energy consumption modeling:
A survey. IEEE Communications Surveys Tutorials, 18(1):732-75) 794322--9444 2016.
[4] Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d' Aspremont. Convex relax- ations for permutation problems. SIAM Journal on Matrix Analysis and Applications, 36(4): 1465-1488, 2015.
[5] Subhashini Krishnasamy, Arapostathis, Ramesh Johari, and Sanjay Shakkottai. On learning the ep rule in single and parallel server networks. CoRR, abs/1 fbss/182..0623,, 2018. URLhttpp
//arxiv.org www.orr//////////////.oo/eeeeee/ abs/ /aee./102..0 06723
[6] Retsef Levi, Thomas Magnanti, and Yaron Shaposhnik. Scheduling with testing. Management Science, 65(2):776-799 2019.
[7] Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic right- sizing for power-propone pwwer-propottional data centers. In 2011 Proceedings IEEE INFOCOM, pages 1098-1106, 1106, 2011.
[8] Tin Liu. Learning to Rank for Information Retrieval. Springer, 2011.
(9] Avishai Mandelbaum and Alexander I.. Stolyar. Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cu-rule. Operations Research, 52(6))833-855 855, 2004.
[10] Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM Special Interest Group on Data Communication, SIGCOMM '19, page 270-288, New York, NY, USA, 2019. Association for Computing Machinery.
[11] Michael L. Pinedo. Scheduling: Theory, Algorithus, and Systems. Springer, 3 edition, 2008
[12] Aleksandrs Slivkins. Introduction multi-armed bandits. Foundations and Trends Machine Learning, 12(1-2):1-286, 2019.
[13] Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59-66, 1956.
[14] Philip C. Stillman and Philip C. Strong. Pre-triage procedures in mobile rural health clinics in Ethiopia. Rural Remote Health, 8(3):555, 2008
[15) Zhankun Sun, Nilay Tank Argon, and Serhan Ziya. Patient triage and prioritization under austere conditions. Management Science, 64(110)4471-444) 44899, 2018.
[16] Muhammad Tirmazi. Adam Barker, Nan Deng, Md E. Haque, Zhijing Gene Qin, Steven Hand, Mor Harchol-Balter and John Wilkes. Borg: The next generation. In Proceedings of the Fifteenth European Conference Computer Systems, EuroSys '20, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450368822
[17] Jan A. van Mieghem. Dynamic Scheduling with Convex Delay Costs: The Generalized c/mu Rule. The Annals of Applied Probability, 5(3):809 833, 1995.
[18] James Vincent. Facebook now using Al to sort content for quicker moderation, 2020. URI http://wwwwaaoroooo/////////////
ai htw.:aaaeeboooaiiamooomrrttiiooa
10


Reviews:
[{"review_id": "w11GvMLteKN", "reviewer": "Reviewer_ub4m", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nProposed 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. \n\nThe 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. \n\nIn conclusion, a clean, well written paper with a concrete set of theoretical results. I vote for acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "UUMCsp5euDV", "reviewer": "Reviewer_njGK", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n-- 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]. \n\nOther 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. \n\n-- 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SMMdLkbJ5FC", "reviewer": "Reviewer_wNcX", "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).\n\nConsider 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. \n\nOn 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. \n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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). \n\nAlthough the paper is general very well written, I feel that some parts can be substantially improved. In particular:\n\n1) the model is not adequately described and self contained,\n2) 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 \n3) 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\"). \n\nMost 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. \n\n(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).\n\nTo 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes they have.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't think there are any particular ethical concerns about this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "76mez0Zza6", "reviewer": "Reviewer_jqaB", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nNo negative societal impact as far as I can tell.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns as far as I can tell.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

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)