Selling reserved instances (or virtual machines) is a basic service in cloud computing. In this paper, we consider a more flexible pricing model for instance reservation, in which a customer can propose the time length and number of resources of her request, while in today's industry, customers can only choose from several predefined reservation packages. Under this model, we design randomized mechanisms for customers coming online to optimize social welfare and providers' revenue. We first consider a simple case, where the requests from the customers do not vary too much in terms of both length and value density. We design a randomized mechanism that achieves a competitive ratio @math for both and , which is a improvement as there is usually no revenue guarantee in previous works such as azar2015ec,wang2015selling . This ratio can be improved up to @math when we impose a realistic constraint on the maximum number of resources used by each request. On the hardness side, we show an upper bound @math on competitive ratio for any randomized mechanism. We then extend our mechanism to the general case and achieve a competitive ratio @math for both social welfare and revenue, where @math is the ratio of the maximum request length to the minimum request length and @math is the ratio of the maximum request value density to the minimum request value density. This result outperforms the previous upper bound @math for deterministic mechanisms wang2015selling . We also prove an upper bound @math for any randomized mechanism. All the mechanisms we provide are in a greedy style. They are truthful and easy to be integrated into practical cloud systems.
In this paper, we study online algorithms that schedule malleable jobs, i.e., jobs that can be parallelized on any subset of the available @math m identical machines. We study a model that accounts for the tradeoff between multiprocessor speedup and overhead time, namely, if job @math j has processing requirement @math pj and is assigned to run on @math kj machines, then @math j's execution time becomes @math pj kj+(kj-1)c, where @math c is a constant parameter to the problem. For @math m=2, we present an online algorithm OCS that has a strong competitive ratio of 3 2, matching a previously established lower bound. We also present an online algorithm ASYM2 that is asymptotically @math ((4-∈) (3-∈))-competitive when @math m=2, where @math 0<∈≤2 is a parameter to the algorithm, improving upon an existing asymptotically (3 2)-competitive algorithm. Finally, we present an online algorithm OTO that is strongly @math 2-competitive when @math m=3, improving upon the previous best upper bound of @math 9 4. We consider the online scheduling of malleable jobs on parallel systems, such as clusters, symmetric multiprocessing computers, and multi-core processor computers. Malleable jobs is a model of parallel processing in which jobs adapt to the number of processors assigned to them. This model permits the scheduler and resource manager to make more efficient use of the available resources. Each malleable job is characterized by arrival time, deadline, and value. If the job completes by its deadline, the user earns the payoff indicated by the value; otherwise, she earns a payoff of zero. The scheduling objective is to maximize the sum of the values of the jobs that complete by their associated deadlines. Complicating the matter is that users in the real world are rational and they will attempt to manipulate the scheduler by misreporting their jobs' parameters if it benefits them to do so. To mitigate this behavior, we design an incentive compatible online scheduling mechanism. Incentive compatibility assures us that the users will obtain the maximum payoff only if they truthfully report their jobs' parameters to the scheduler. Finally, we simulate and study the mechanism to show the effects of misreports on the cheaters and on the system.