Competitive algorithm for scheduling of sharing machines with rental discount.

This paper addresses the online parallel machine scheduling problem with machine leasing discount. Rental cost discount is a common phenomenon in the sharing manufacturing environment. In this problem, jobs arrive one by one over-list and must be allocated irrevocably upon their arrivals without knowing future jobs. Each job is with one unit of processing time. One manufacturer leases a limited number of identical machines over a manufacturing resource sharing platform, and pays a rental fee of α per time unit for processing jobs. Especially, when the time duration of a leasing machine reaches the discount time point, the manufacturer will get a discount for further processing jobs on the machine, i.e., the unit time rental cost is α β , where β = 1 / 2 is the discount coefficient. The objective function is the sum of makespan and the rental cost of all the sharing machines. When the unit time rental cost α ≥ 2 , we first provide the lower bound of objective value of an optimal schedule in the offline version and prove a lower bound of 1.093 for the problem. Based on the analysis of the offline solution, we present a deterministic online algorithm LS-RD with a tight competitive ratio of 3/2. When 1 ≤ α < 2 , we prove that the competitive ratios of algorithm LIST are 1 and 2 for the case of m = 2 and m → ∞ , respectively. For the general rental discount 0 < β ≤ 1 , we give the relevant results for offline and online solutions. [ABSTRACT FROM AUTHOR]