Complexity analysis and approximation algorithms for the single-machine scheduling problem with workload-dependent maintenance activities

Peihai Liu, Manzhan Gu () and Xiwen Lu
Additional contact information
Peihai Liu: East China University of Science and Technology
Manzhan Gu: Shanghai University of Finance and Economics
Xiwen Lu: East China University of Science and Technology

Journal of Scheduling, 2025, vol. 28, issue 4, No 2, 406 pages

Abstract: Abstract This paper considers the single-machine scheduling problem with workload-dependent maintenance activities of variable length. The time needed to perform a maintenance activity is a function of the total processing time of the jobs that are processed between the starting time of this activity and the end of the last previous activity. In the case where the function is concave, we study the computational complexity of the three problems with the goal of minimizing the makespan, the total completion time, and the total weighted completion time, respectively. In addition, we propose a 2-approximation algorithm for the first problem and a 2.5-approximation algorithm for the second problem.

Keywords: Single-machine scheduling; Computational complexity; Maintenance activities; Approximation algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-025-00842-3 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:jsched:v:28:y:2025:i:4:d:10.1007_s10951-025-00842-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-025-00842-3

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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