We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have machine-type dependent sizes and have individual deadlines. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. Since we observe the slack of jobs to have a fundamental influence on the competitiveness, we study the model when instances are parameterized by their (minimum) slack. An instance is called to have a slack of @math if, for all jobs, the difference between the job's release time and the latest point in time at which it needs to be started is at least @math . While for @math no finite competitiveness is possible, our main result is an @math -competitive online algorithm for @math with @math , where @math and @math denotes the largest setup time and the cost ratio of the machine-types, respectively. It is complemented by a lower bound of @math .
In the leasing variant of Set Cover presented by [1], elements (U ) arrive over time and must be covered by sets from a family (F ) of subsets of (U ). Each set can be leased for (K ) different periods of time. Let ( | U | = n ) and ( | F | = m ). Leasing a set (S ) for a period (k ) incurs a cost (c_ S ^ k ) and allows (S ) to cover its elements for the next (l_k ) time steps. The objective is to minimize the total cost of the sets leased, such that elements arriving at any time (t ) are covered by sets which contain them and are leased during time (t ). [1] gave an optimal (O( n) )-approximation for the problem in the offline setting, unless ( P = NP ) [22]. In this paper, we give randomized algorithms for variants of Set Cover Leasing in the online setting, including a generalization of Online Set Cover with Repetitions presented by [2], where elements appear multiple times and must be covered by a different set at each arrival. Our results improve the ( O ( ^2 (mn)) ) competitive factor of Online Set Cover with Repetitions [2] to ( O ( d (dn)) = O ( m (mn)) ), where (d ) is the maximum number of sets an element belongs to. Consider the following Steiner Tree leasing problem. Given a graph G= (V,E) with root r, and a sequence of terminal sets D t i¾? Vfor each day ti¾? [T]. A feasible solution to the problem is a set of edges E t for each tconnecting D t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we leaseedges for say, a day, a week, a month, a year . Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting. We consider an online facility location problem where clients arrive over time and their demands have to be served by opening facilities and assigning the clients to opened facilities. When opening a facility we must choose one of K different lease types to use. A lease type k has a certain lease length lk. Opening a facility i using lease type k causes a cost of @math and ensures that i is open for the next lk time steps. In addition to costs for opening facilities, we have to take connection costs cij into account when assigning a client j to facility i. We develop and analyze the first online algorithm for this problem that has a time-independent competitive factor. This variant of the online facility location problem was introduced by [7] and is strongly related to both the online facility problem by [5] and the parking permit problem by [6]. Nagarajan and Williamson gave a 3-approximation algorithm for the offline problem and an O (Klogn)-competitive algorithm for the online variant. Here, n denotes the total number of clients arriving over time. We extend their result by removing the dependency on n (and thereby on the time). In general, our algorithm is @math -competitive. Here @math denotes the maximum lease length. Moreover, we prove that it is @math -competitive for many "natural" cases. Such cases include, for example, situations where the number of clients arriving in each time step does not vary too much, or is non-increasing, or is polynomially bounded in @math . We consider online problems where purchases have time durations which expire regardless of whether the purchase is used or not. The parking permit problem is the natural analog of the well-studied ski rental problem in this model, and we provide matching upper and lower bounds on the competitive ratio for this problem. By extending the techniques thus developed, we give an online-competitive algorithm for the problem of renting steiner forest edges with time durations.