1 Introduction
Consider a cloud service provider that makes resources available to its clients via a cloudbased system. Over time, various jobs are submitted to the system by multiple clients and must be assigned to the servers in order to satisfy their demanded resources. Each server has limited resources available and job assignment must respect these capacity constraints. The company’s operating costs are proportional to the total time servers are active. This is an online problem since jobs arrive in the system one after another, and the scheduler must decide how to assign these jobs to the servers to minimize overall costs. In our scenario migrating a job from one server to another after it has been assigned is prohibitively expensive, so all the assignment decisions are fully irrevocable. A natural question arises here: how should jobs be assigned to servers in order to obtain the minimum cost? Two natural strategies are NextFit and FirstFit. In NextFit, the scheduler keeps track of at most one “open” server and keeps assigning jobs to it while the server capacity can accommodate the demanded resources. As soon as a new job requests more resources than there are available at the open server at that time, then the server is closed (meaning no future jobs will be assigned to it unless it is released), and a new server is opened to accommodate the job. In the FirstFit strategy, every active server is considered “open” when a job arrives. The servers are scanned in the order in which they were opened and the first server that can accommodate the job is assigned that job. If no such server exists a new server gets opened.
The above scenario is formalized in the socalled renting servers in the cloud problem, denoted by , which was recently introduced by Li et al. [12]: there is an infinite supply of identical servers, each having capacity . The job scheduler needs to process a sequence of jobs , where job is a triple such that is the size of a job, is the arrival time of a job, and is the finishing time of a job, and assign each job to a server. The ordering of jobs satisfies . The input sequence is chosen by the adversary subject to this restriction. A server can be rented starting at any time and it continues to be rented until all jobs assigned to it terminate. The cost of a single server is the duration of its rental period. The cost of a whole solution is the sum of costs of all rented servers. The goal is to assign jobs to servers to minimize the overall cost while satisfying server capacity constraints, that is at every time the sum of all sizes of jobs assigned to a given server and active at time should not exceed . Jobs must be processed in the adversarial order that they are given. Thus, this problem on an instance with and for all is equivalent to the classical bin packing problem on the corresponding instance . Clearly, is a generalization of the bin packing problem, that introduces a temporal component to the classical problem. Indeed, FirstFit and NextFit algorithms, as defined above, are direct analogues of the same algorithms for bin packing. The performance of online algorithms is measured by the notion of competitive ratio, which is the worstcase ratio (over the inputs) between the cost achieved by the online algorithm and the cost achieved by an offline optimal solution that knows the entire input instance in advance. One distinguishes two notions of competitive ratio – strict, that is it applies to all inputs, and asymptotic, that is it applies only to large enough inputs ignoring terms. This distinction becomes very important for renting servers in the cloud problem, as we describe below. It is easy to see that in its generality does not admit algorithms with a constant competitive ratio. Thus, the research so far has focused on the inputs parameterized by , which is the ratio between the maximum and minimum duration of a job in the input.
The research literature on the classical bin packing problem is quite rich and spans over years of active research. The asymptotic competitive ratio of 1.7 for FirstFit was established in the early seventies [16]. It took over years to establish the same result for the strict competitive ratio [3]. By now there are many different proofs of competitiveness of FirstFit and its variants. The key technique that is used to establish the majority of upper bounds is called the weighting technique. The idea is to define a weight function which modifies sizes of items that satisfies the following two properties:

for most of the bins of a given algorithm we have ,

for any bin of an offline optimal solution we have .
If such a weight function is found for a given algorithm , it implies a competitive ratio of at most , since the sum of all weights of items is at least and at most . This technique can be seen to be an instance of the more general primaldual framework applied to bin packing. Variations on this technique involve making weights dependant on the schedules of and/or , splitting weight function into several functions, and applying amortization.
is also related to the dynamic bin packing problem. In the dynamic bin packing the items arrive and depart from the system, and repacking of previously packed items may or may not be allowed depending on the version of the problem. The goal is to maintain a small number of bins at all times compared to an optimal solution. In repacking is not allowed and the objective function is different. In fact, aims to reduce the total cost of all rented servers. We describe the known results for the problem in greater detail in Section 2. Due to the vast interest in cloud computing in recent years, this problem has received much attention from applied researchers and now there are attempts to prove theoretical guarantees. However, there is a significant gap between the known lower and upper bounds for this problem and for NextFit and FirstFit, in particular. This is not surprising, in light of the history of analysis of FirstFit and its variants for the vanilla bin packing problem. Adding a temporal component makes the problem significantly more difficult to analyze.
The known upper bound proofs on the performance of FirstFit in case of are based on utilization, denoted by , and span, denoted by , of the input , defined as follows:
Thus, the utilization can be thought of as the total volume (size times duration) of all jobs, and span is the total duration of all jobs ignoring overlaps. The previous results, which are based on span and utilization, such as the upper bound for NextFit and for FirstFit, include additive terms and which arise from applying the span bound, and which we suspect to be too loose. One of the ways of making progress towards analyzing this problem is to reduce or even completely eliminate these additive terms. There is a natural reason for the appearance of these additive terms and it has to do with the distinction between the asymptotic and strict competitive ratios. Let denote the number of servers that are used by at time , and define similarly. Suppose one proves that for all times we have , which would be analogous to an “asymptotic bound” for a fixed time , so to speak (note that this bound does not have to apply for each time , and amortization tricks may be used to prove this bound on average, but we assume such a bound for each for simplicity of the argument). The overall cost of the algorithm is . Thus, an “asymptotic bound” for a fixed time with competitive ratio gets converted into the overall bound of for the problem. The “asymptotic bounds” for a fixed time arise because often one needs to ignore one or two special servers to argue the desired inequality. Thus, one approach towards tightening these bounds is to attempt to prove “strict bounds” for a fixed time , i.e., . This way would avoid the appearance of the term. This is akin to the difference between proving the asymptotic competitive ratio of FirstFit and strict competitive ratio of FirstFit for the classical bin packing. We view this as the main obstacle to improving the known results.
We now describe one possible program to overcome the abovementioned obstacle. First, generalize the weight function technique from the bin packing problem to the problem to prove asymptotic bounds in restricted cases. Second, optimize these bounds and make them strict in restricted cases. Third, generalize these techniques to the original problem. In this paper we make progress towards the above program. We focus on the special case of , which we call equal duration. Sometimes we consider restricted input sequences which result in all FirstFit servers having the same start time and same finishing time – we refer to this scenario as the case of uniform servers.
Our main results for for jobs of equal duration are summarized below:

We show a tight bound of on NextFit demonstrating that the previous bestknown upper bound of was not tight (Theorem 4.1).

We demonstrate a lower bound of on the competitive ratio for FirstFit where jobs have duration and arrival times and for (Theorem 5.1).

We show a tight asymptotic bound of on the load of longrunning uniform FirstFit servers when jobs have duration and integer arrival times (Corollary 5.6). This implies a competitive ratio of for FF in the longrunning uniform case.

For the uniform server case, using the weight function techniqe, we show an upper bound of on the asymptotic competitive ratio of FirstFit where jobs have duration , arrival times and for , and FirstFit servers are uniform (Theorem 5.9). Observe that under the uniform servers assumption, for small in a particular range, we can get an improvement over the bin packing problem’s ratio of . However, we conjecture that as approaches , the case becomes worstcase.

We prove a strict competitive ratio of for FirstFit where each job has a duration and arrival times and (Theorem 5.12).
Note that the third result demonstrates that if we consider the case of jobs of duration and integer arrival times then those servers running for a long time automatically have a high load in the limit. This suggests that the difficult inputs for FirstFit are those where servers are short lived. Thus, we conjecture that the case of jobs having duration and arrival times and and uniform FirstFit servers is responsible for the worstcase competitive ratio. By the above items (2) and (4) specialized to we get lower bound of and the asymptotic upper bound of , respectively, for this case.
Our conceptual contributions are as follows: we show how to extend and apply the weight function technique to the problem, we prove the strict competitive ratio on the performance of FirstFit for a special case, and we outline the above program towards closing the gap in the analysis of the FirstFit for .
The rest of this paper is organized as follows. The related work is summarized in Section 2. Section 3 introduces some basic notation and definition for the renting servers in the cloud problem. In Section 4, we discuss the bounds for the NextFit algorithm. Then, in Section 5, we present our lower and upper bounds for the FirstFit algorithms. We discuss long running uniform FirstFit servers in Section 5.2, which suggests that shorterlived servers may result in worse competitive ratio. As such, we analyze the case of arrival times and uniform FirstFit servers in Section 5.3. The strict bound for FirstFit is analyzed in Section 5.4. Finally, conclusions are made in Section 6.
2 Related Work
The research literature related to bin packing and its variants is rather large. Google scholar produces 211,000 records in response to the “bin packing” query. We cannot do it justice in this short section, so instead we mention only the most relevant (to this paper) fundamental results, restricted to the online setting and mostly to FirstFit and NextFit algorithms.
The bin packing problem [11] is one of the most fundamental NPhard ([4]) problems in the field of algorithm design that has received a lot of attention among researchers. In the online setting of this problem, we are given a sequence of items with sizes in the range . The goal is to pack these items in the minimum number of bins of capacity . Many online algorithms have been designed for the bin packing problem; among them, FirstFit is among the most famous ones. This algorithm keeps the bins in the order in which they were opened and places a given item in the first bin that has enough space for it. If such a bin does not exist, it opens a new one. Ullman in [16] established the asymptotic bound on the competitive ratio of FirstFit of the form . The additive term was improved multiple times [7, 6, 17] until when Dosa et al. demonstrated the absolute ratio [3]. Another algorithm that we investigate in this paper is related to the bin packing NextFit algorithm. This algorithm only allows one bin to be open at a time. If there is space, it assigns a given item to the open bin; otherwise, it closes that bin and opens a new one. Johnson et al. [8] proved that the competitive ratio of NextFit is . Other algorithms with better competitive ratios for this problem are known, such as BestFit and with ratios of and , respectively [16, 14]. FirstFit and BestFit belong to the more general family of AnyFit algorithms, which is essentially the family of greedy algorithms (never open a new bin unless you have to). In general, AnyFit has tight competitive ratio ; however, rather large subfamilies of AnyFit have tight competitive ratio of [9]. However, we do not go into detail about those algorithms in this paper.
The dynamic bin packing, generalizing the vanilla bin packing, was first proposed by Coffman et al. [2]. In this problem items with different sizes arrive and depart in sequential order. The size and arrival time of an item are revealed when the item arrives but the duration of a job is hidden. Thus, the algorithm is notified of the departure of an item at the time the item departs from the system. The objective function here is the same as online bin packing. Coffman et al. were studying the version where repacking of items is not allowed. They established the lower bound of for any online algorithm . In the discrete version of the problem, each item has size for some integer . The competitive ratio of the AnyFit algorithm in the discrete version is . However, no online algorithm can do better than [1].
problem, which can be viewed as a new type of dynamic bin packing, was introduced by Li et al. [12] for the first time. In this problem, bins are referred to as servers and the cost of each server is a function of the duration of its usage. Li et al. showed that no algorithm from AnyFit family can achieve a competitive ratio less than , which is the ratio of the maximum to the minimum duration of all the items in the input sequence. They showed that the competitive ratio of FirstFit is at most . Li et al. also analyzed FirstFit under restricted input families. More specifically, they proved that the competitive ratio of FirstFit when the sizes of jobs are greater or equal to , where is a positive integer, is at most , and when job sizes are less than or equal to then FirstFit has competitive ratio at most . Li et al. [12] also presented the algorithm which achieves competitive ratio of at most when is not known in advance and when is known. Later, Kamali and LopezOrtiz [10] presented a general lower bound for the problem (not just for AnyFit algorithms) of at least where is a lower bound on the sizes of jobs. Kamali and LopezOrtiz also considered the NextFit algorithm and proved that it has competitive ratio of and introduced a variant of NextFit with competitive ratio . Tang et al. [15] improved the analysis of FirstFit establishing the upper bound of on the competitive ratio. In his PhD thesis [13], Ren improved the upper bound on the competitive ratio of FirstFit further to , which is the current stateoftheart.
3 Preliminaries
We use to denote the set .
The input to the general problem is a sequence of items , where item is a triple denoting a job of size starting at time and finishing at time . The duration of a job is . We say that a job is active or alive at time if . Two jobs and are said to be nonoverlapping if , otherwise they are said to be overlapping. Note that representing active times of jobs by halfopen intervals allows us to consider the two jobs such that one starts at exactly the same time as the other one finishes as nonoverlapping. We say that a server is active or alive at time if it has at least one job scheduled on it that is active at time . The jobs are presented in an order that respects their starting times, i.e., . For the same starting time , jobs starting at time are presented in an adversarial order. An important parameter of the input sequence is , which is the ratio of the maximum duration of a job to the minimum duration of a job in the sequence. The case of all jobs having equal duration corresponds precisely to . In the case of jobs having equal duration (which shall be clear from the context) we specify each job by its size and start time to simplify the notation, i.e., , since the finishing time is a function of the start time, i.e., .
In this paper we focus on the case of equal duration of jobs and two arrival times and , where is arbitrary, and jobs of duration . In some sections, we concentrate on arrival times and and jobs of duration , unless stated otherwise; by scaling, this setting is equivalent to arrival times and and jobs of duration . Which of these notations is used in a particular section will be clear from the context.
For we use to denote the sum of all sizes of jobs that have start time , i.e., . For we use to denote the sum of all sizes of jobs that have start time in the interval . For a server we use to denote the sum of all sizes of jobs that were scheduled to run on and that are active at time . The value is also called the load of server at time .
For an algorithm we use to denote the value of the objective function achieved by on the input . For a specific time we use to denote the number of servers that are active (i.e., “alive”) at time . If the last finishing time of any job is then we have:
We omit from the above notation, when it is clear from the context. We use similar notation for an optimal solution denoted by .
When the input sequence is such that it results in FirstFit servers all having the same start time and the same finishing time (which, consequently, must be the largest finishing time of any job in the sequence), we refer to this scenario as the case of uniform servers.
4 Tight Competitive Ratio for NextFit
In this section we prove a tight bound of on the competitive ratio of the NextFit algorithm for the problem when and jobs have arbitrary start times. Recall that the NextFit algorithm keeps at most one server open at any time, i.e., a server that can be assigned newly arriving jobs. If a given job does not fit in the open server, the algorithm closes the server (meaning it will not assign any new jobs to it from this point onward), opens a new server, and assigns the job to the newly opened server. Note that NextFit never reopens a closed server. Algorithm 1 presents the pseudocode for NextFit.
The lower bound of follows immediately from the lower bound on the competitive ratio of NextFit for the bin packing problem and the fact that renting servers in the cloud problem generalizes bin packing. The upper bound of on the competitive ratio of NextFit follows from the theorem below, which shows that the upper bound holds not only on the total cost of the schedule of NextFit, but, in fact, it holds at each individual time .
Theorem 4.1.
Suppose that the duration of each job in is exactly while arrival times are arbitrary. Then for every time we have
Proof.
If there are no active jobs at time then and the claim trivially holds. If there are active jobs at time and then we have and the claim also trivially holds.
It remains to show the claim for those where . Let and let be the servers of NextFit that are still active at time and ordered in the nondecreasing order of their opening times. Observe that since NextFit maintains only one open server at a time, servers must be closed at time . We also use the following simple fact based on duration of each job being exactly : a job is active at time if and only if its arrival time is in . Therefore we have:
(1) 
Since is active at time , it must have had a job scheduled on it in time interval . Also, the job that closed must have arrived in . We conclude that servers were opened in and thus all jobs scheduled on these servers since their opening are still active at time . Consider a server that got closed at time by a job . This means that job was scheduled on server so we have the inequality
Combining this with the fact that all jobs scheduled on servers are still active at time , we conclude
(2) 
Observe that the above inequality might fail for since the jobs present at time in might finish before time . Consider grouping servers in maximally many disjoint pairs , , , . The last pair must satisfy , which implies that . Summing up equations (2) corresponding to this pairing we derive
Combining this with equation (1) we conclude that . Rounding the lefthand side up we get , which implies that by integrality. Multiplying both sides by we get
To conclude, we have demonstrated that and the equation is obvious. ∎
Corollary 4.2.
The competitive ratio of NextFit for the case equal duration and arbitrary arrival times is at most .
5 FirstFit
In this section we consider the FirstFit algorithm, which unlike NextFit does not close servers unless they are no longer active. In the FirstFit algorithm, a newly arriving job is assigned to the earliest (in the order of opening) active server that can accommodate it. If none of the active servers has enough residual capacity to accommodate the new job, then a new server is opened. When all of the jobs in a server depart, the server is no longer active and it is closed. Algorithm 2 provides the pseudocode.
5.1 Lower Bound
In this section, we present a parameterized lower bound on the competitive ratio of FirstFit for the case of equal duration and derive a couple of consequences of this parameterized lower bound. The adversarial instance consists of two sequences of jobs. In the first sequence all jobs have arrival time and in the second sequence all jobs have arrival time , by which our lower bound is parameterized. All jobs have duration in this instance. The first sequence is simply the nemesis instance for the bin packing problem due to [5]. Recall that this instance creates three groups of FirstFit servers: (1) those with the load roughly , (2) those with the load roughly , and (3) those with the load roughly . Meanwhile, is able to schedule all the jobs in the same instance into servers of duration and load close to . Our second sequence consists of jobs that arrive at time and are used to extend the duration of each existing FirstFit server by an additive . Thus, the items used to extend group (1) servers have size each. Those items used to extend group (2) have size each. Lastly, those items used to extend group (3) have size each. These items can be neatly combined by into servers of duration and load . The following theorem presents the parameterized lower bound. The proof is selfcontained, since we reproduce the nemesis instance from [5] as part of the proof.
Theorem 5.1.
The asymptotic competitive ratio of FirstFit for the problem in the case where the duration of each job is and jobs arrive at times and is at least .
Proof.
Fix a large positive integer and take such that . For we define . The adversarial sequence of input items is a concatenation of two sequences. The jobs in the first sequence start at time zero, while the jobs in the second sequence start at time . Furthermore, the first sequence is subdivided into three phases. The first phase consists of groups, where each one consists of jobs. Likewise, the second phase consists of groups, where each group consists of jobs. The third phase consists of individual large jobs. Next, we describe the entire input with more details. It may be helpful to refer to Figure 1 while following the text below.
We begin by describing the first sequence. In the first phase, group consists of items where , and the sizes are defined as follows:
FirstFit puts into server , which results in the server having the load . None of the jobs fit into this server. So, FirstFit assigns these jobs to server with resulting load of . Note that, none of the jobs in group will fit in any of the previous servers from group . The smallest load of a server corresponding to group jobs, which is server , is , while the smallest job in group is . Therefore, cannot fit into server . Thus, FirstFit has to open servers for each group , where in total servers are used for all of the jobs in the first phase.
The second phase has groups, where each one consists of jobs . Each job has start time and their sizes are given in order as follows:
According to FirstFit, jobs and are assigned to one server with the total size of ; and, jobs and are packed into one server with total load of . It is clear that, the smallest job from the remaining items in this group cannot fit in any of the open servers. Thus, FirstFit has to place each pair and ; and ; and into different servers, each with a total load of . Note that the smallest job in group , which is , cannot fit into any server from group , as the load of all the servers is at least . In other words, FirstFit has to open servers for assigning jobs in each group , employing servers for all the jobs in the second phase.
In the third phase, jobs of size each are presented having start time . Since none of these jobs fit into the previously opened servers, FirstFit has to assign these jobs to new servers, resulting in opening servers in this phase. This finishes the description of the first sequence.
In the second sequence all jobs have start time , and their sizes are as follows. The first jobs are of size each, which are followed by jobs of size each, followed by jobs of size each. FirstFit assigns the first jobs to the servers that were opened in the first phase (one job per server), the next jobs to the servers that were opened in phase (one job per server), and the last jobs to the bins that were opened in phase (one job per server).
In general, FirstFit uses servers in the first phase, bins in the second phase and servers in the third phase. See Figure 1.. The second sequence has the effect of extending the duration of each server (the period during which the server is active) to . Therefore, the cost of FirstFit is .
The optimal offline algorithm, , uses servers for all the jobs from phase (i.e., jobs of size ). The remaining space in these bins will be filled with the following combinations of items from phases and :

for all jobs ; , in group : combines with .

since cannot be combined with , combines:

with and,

with .

According to this packing scheme, two jobs and remain unpacked. Therefore, uses one extra server for packing these two jobs. Thus, uses servers for duration to pack all jobs in the first phases, i.e., the first sequence. For the jobs in the second sequence, uses servers for jobs that are released at time . In total, uses servers, each of duration . See Figure 1..
As a result, the competitive ratio of FirstFit for is at least as . ∎
Consequently, from Theorem 5.1, we can conclude the following result for this problem in the case that jobs have arbitrary arrival times:
Corollary 5.2.
The competitive ratio of FirstFit for the case of equal duration and arbitrary arrival times is at least .
Proof.
Take in Theorem 5.1. ∎
As another consequence, we derive a lower bound on the competitive ratio of FirstFit in the case of each job having duration and arrival times and .
Corollary 5.3.
The competitive ratio of FirstFit for the case of all jobs having duration and arrival times and is at least .
Proof.
Take in Theorem 5.1 and observe that the case of duration and arrival and is the same as the one in the statement of the theorem (by scaling). ∎
5.2 Upper Bound for LongRunning Uniform Servers
In this section we consider the case when all jobs in the input sequence have duration and arrival times , and FirstFit packs these items into servers starting at time and finishing at time . Thus, as we let go to infinity, this setting represents “longrunning” uniform servers of FirstFit. We show that asymptotically (as ) such FirstFit servers have amortized load of at all times. We also observe that this bound is tight, i.e., there are inputs on which longrunning FirstFit servers have load of roughly at all times. Thus, longrunning servers are beneficial for FirstFit since load of translates to competitive ratio of when FirstFit cost is compared to the cost of . This suggests that worstcase adversarial instances for FirstFit on equal duration jobs should be such that FirstFit servers are shortlived, and, perhaps even when jobs arrive at times and only with each server being of duration – the case analyzed in the following sections of this paper.
We begin with a few basic observations about long running servers in the next lemma, before giving our main result in Lemma 5.5.
Lemma 5.4.
Fix . Let be such that all jobs in have duration and arrival times and let be a set of FirstFit servers of duration exactly that were opened at time . We denote the servers in by (opened in this order), where .
For we define the layer , denoted by , to be the set of all items packed in that arrived at time . Let denote the size of all items in layer . Assume that . Then we have:

The cost of FirstFit arising from servers in is

;

for
Proof.

Immediate from the definition of the cost and the fact that each server in has duration exactly .

This is a standard argument about FirstFit. Let denote the total size of items in server that arrived at time . We have for since otherwise items in server would have been placed in server instead. Adding up all these inequalities we get By adding and to both sides, we obtain Observe that by the same reasoning as before. Moreover, we have by definition. Combining all these facts, establishes this part of the lemma.

Fix . Let denote the total size of items in server that arrived at time . Similarly, let denote the total size of items in server that arrived at time . For we have otherwise items packed into bin at time should have been placed into bin by FirstFit. Summing all these inequalities we obtain By adding to both sides we obtain We have and . Therefore, we obtain
∎
Now from the results in Lemma 5.4, we can establish strong upper bounds on the ratio between utilization and FirstFit cost, as follows.
Lemma 5.5.
Let be the input such that each job has duration and arrival times and suppose FirstFit opens servers and each server of FirstFit on starts at time and finishes at time . Then we have:
Proof.
Fix . From the results in Lemma 5.4, we have:
We will choose multipliers such that the linear combination of inequalities has on the lefthand side (sum of sizes is half of utilization, since all items have duration ). The multipliers are defined recursively: .
Next, we verify that has on the lefthand side. For that it is convenient to think of inequality as , where we define . We prove by induction on that for the lefthand side of is . The base case of is clear, since it is simply itself. Assuming the lefthand size of is as in the claim, we observe that the lefthand side of is
as required. Plugging in and using gives the desired result.
Next, we derive the bound on the righthand side of , which is expressed as . Thus, we introduce partial sums of the by letting . We have for :
By adding with we obtain Then satisfy the recurrence:
Solving the recurrence we obtain:
Therefore, Since we conclude:
∎
Corollary 5.6.
On the inputs described in Lemma 5.5 with FirstFit achieves competitive ratio .
Proof.
The upper bound on the competitive ratio follows from Lemma 5.5, since we have and . ∎
The bound on utilization in Lemma 5.5 is tight asymptotically as . It is witnessed by the following example. Fix and .

at time we present items of size each;

at even times we present items of size each.
Arrival time of the last job is in the above. Assume is even for simplicity of the presentation. As can be seen in Figure 2, FirstFit opens servers of duration each and utilization is . Thus, for this example we have:
Comments
There are no comments yet.