IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v44y2022i1d10.1007_s10878-021-00836-9.html
   My bibliography  Save this article

Competitive algorithm for scheduling of sharing machines with rental discount

Author

Listed:
  • Yinfeng Xu

    (Donghua University)

  • Rongteng Zhi

    (Donghua University)

  • Feifeng Zheng

    (Donghua University)

  • Ming Liu

    (Tongji University)

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

Suggested Citation

  • Yinfeng Xu & Rongteng Zhi & Feifeng Zheng & Ming Liu, 2022. "Competitive algorithm for scheduling of sharing machines with rental discount," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 414-434, August.
    • Handle: RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00836-9
    DOI: 10.1007/s10878-021-00836-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-021-00836-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-021-00836-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. György Dósa & Yong He, 2006. "Scheduling with machine cost and rejection," Journal of Combinatorial Optimization, Springer, vol. 12(4), pages 337-350, December.
    2. Fang, Debin & Wang, Jiancheng, 2020. "Horizontal capacity sharing between asymmetric competitors," Omega, Elsevier, vol. 97(C).
    3. Juanjuan Qin & Kun Wang & Ziping Wang & Liangjie Xia, 2020. "Revenue sharing contracts for horizontal capacity sharing under competition," Annals of Operations Research, Springer, vol. 291(1), pages 731-760, August.
    4. Dai, Wenqiang & Dong, Yucheng & Zhang, Xiaotian, 2016. "Competitive analysis of the online financial lease problem," European Journal of Operational Research, Elsevier, vol. 250(3), pages 865-873.
    5. Liang Guo & Xiaole Wu, 2018. "Capacity Sharing Between Competitors," Management Science, INFORMS, vol. 64(8), pages 3554-3573, August.
    6. Adhau, Sunil & Mittal, M.L. & Mittal, Abhinav, 2013. "A multi-agent system for decentralized multi-project scheduling with resource transfers," International Journal of Production Economics, Elsevier, vol. 146(2), pages 646-661.
    7. Islam Akaria & Leah Epstein, 2020. "An optimal online algorithm for scheduling with general machine cost functions," Journal of Scheduling, Springer, vol. 23(2), pages 155-162, April.
    8. Seok, Hyesung & Nof, Shimon Y., 2014. "Dynamic coalition reformation for adaptive demand and capacity sharing," International Journal of Production Economics, Elsevier, vol. 147(PA), pages 136-146.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Peng Liu & Ying Chen, 2022. "Differential Game Model of Shared Manufacturing Supply Chain Considering Low-Carbon Emission Reduction," Sustainability, MDPI, vol. 14(18), pages 1-24, September.
    2. Yuriy Ekhlakov & Sergei Saprunov & Pavel Senchenko & Anatoly Sidorov, 2023. "Fuzzy Model for Determining the Risk Premium to the Rental Rate When Renting Technological Equipment," Mathematics, MDPI, vol. 11(3), pages 1-18, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Lin & Li, Guo, 2023. "Integrating logistics service or not? The role of platform entry strategy in an online marketplace," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 170(C).
    2. Sun, Huiping & Li, Yuchen & Zhang, Jianghua, 2022. "Collaboration-based reliable optimal casualty evacuation network design for large-scale emergency preparedness," Socio-Economic Planning Sciences, Elsevier, vol. 81(C).
    3. Yilmaz, Ibrahim & Yoon, Sang Won & Seok, Hyesung, 2017. "A framework and algorithm for fair demand and capacity sharing in collaborative networks," International Journal of Production Economics, Elsevier, vol. 193(C), pages 137-147.
    4. Tarun Jain & Jishnu Hazra & T. C. E. Cheng, 2023. "Analysis of upstream pricing regulation and contract structure in an agriculture supply chain," Annals of Operations Research, Springer, vol. 320(1), pages 85-122, January.
    5. Jiamin Lu & Nishan Chen & Xin Feng, 2023. "Competitive Analysis of the Online Leasing Problem for Scarce Resources," IJERPH, MDPI, vol. 20(1), pages 1-11, January.
    6. Liqi Zhang & Lingfa Lu & Shisheng Li, 2016. "New results on two-machine flow-shop scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1493-1504, May.
    7. Daozhi Zhao & Jiaqin Hao & Cejun Cao & Hongshuai Han, 2019. "Evolutionary Game Analysis of Three-Player for Low-Carbon Production Capacity Sharing," Sustainability, MDPI, vol. 11(11), pages 1-20, May.
    8. Cao, Kaiying & Xu, Yuqiu & Hua, Ye & Choi, Tsan-Ming, 2023. "Supplier or co-optor: Optimal channel and logistics selection problems on retail platforms," European Journal of Operational Research, Elsevier, vol. 311(3), pages 971-988.
    9. Bredael, Dries & Vanhoucke, Mario, 2023. "Multi-project scheduling: A benchmark analysis of metaheuristic algorithms on various optimisation criteria and due dates," European Journal of Operational Research, Elsevier, vol. 308(1), pages 54-75.
    10. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    11. Elahi, Hamid & Pun, Hubert & Ghamat, Salar, 2023. "The Impact of Capacity Information on Supplier Encroachment," Omega, Elsevier, vol. 117(C).
    12. Xin Geng & Harish Krishnan & Milind G. Sohoni, 2022. "Operational collaboration between rivals: The impact of cost reduction," Production and Operations Management, Production and Operations Management Society, vol. 31(4), pages 1856-1871, April.
    13. Xu, Jun & Wang, Jun-Qiang & Liu, Zhixin, 2022. "Parallel batch scheduling: Impact of increasing machine capacity," Omega, Elsevier, vol. 108(C).
    14. Guang Yang & Ying Wang & Mulin Liu, 2023. "Optimal Policy for Probabilistic Selling with Three-Way Revenue Sharing Contract under the Perspective of Sustainable Supply Chain," Sustainability, MDPI, vol. 15(4), pages 1-22, February.
    15. Wu, Xiangxiang & Zha, Yong & Yu, Yugang, 2022. "The developer’s sourcing strategy in the presence of a competing manufacturer and consumers’ two-dimensional differentiated preferences," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    16. Karaca, Utku & Birbil, Ş. İlker & Aydın, Nurşen & Mullaoğlu, Gizem, 2023. "Masking primal and dual models for data privacy in network revenue management," European Journal of Operational Research, Elsevier, vol. 308(2), pages 818-831.
    17. Gómez Sánchez, Mariam & Lalla-Ruiz, Eduardo & Fernández Gil, Alejandro & Castro, Carlos & Voß, Stefan, 2023. "Resource-constrained multi-project scheduling problem: A survey," European Journal of Operational Research, Elsevier, vol. 309(3), pages 958-976.
    18. Wuliang Peng & Jiali lin & Jingwen Zhang & Liangwei Chen, 2022. "A bi-objective hierarchical program scheduling problem and its solution based on NSGA-III," Annals of Operations Research, Springer, vol. 308(1), pages 389-414, January.
    19. Hyunwoo Park & Christian C. Blanco & Elliot Bendoly, 2022. "Vessel sharing and its impact on maritime operations and carbon emissions," Production and Operations Management, Production and Operations Management Society, vol. 31(7), pages 2925-2942, July.
    20. Nadia Chaudry & Ingunn Vermedal & Kjetil Fagerholt & Maria Fleischer Fauske & Magnus Stålhane, 2020. "A decomposition solution approach to the troops-to-tasks assignment in military peacekeeping operations," The Journal of Defense Modeling and Simulation, , vol. 17(4), pages 357-371, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00836-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.