Competitive algorithm for scheduling of sharing machines with rental discount

Yinfeng Xu (), Rongteng Zhi (), Feifeng Zheng () and Ming Liu ()
Additional contact information
Yinfeng Xu: Donghua University
Rongteng Zhi: Donghua University
Feifeng Zheng: Donghua University
Ming Liu: Tongji University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 1, No 20, 414-434

Abstract: Abstract 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 $$\alpha $$ α 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 $$\alpha \beta $$ α β , where $$\beta =1/2$$ β = 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 $$\alpha \ge 2$$ α ≥ 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\le \alpha

Keywords: shared manufacturing; Online scheduling; Competitive analysis; Rental discounts; Makespan (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00836-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00836-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00836-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().