文献类型：期刊文献

英文题名：Complexity analysis and approximation algorithms for the single-machine scheduling problem with workload-dependent maintenance activities

作者：Liu, Peihai[1];Gu, Manzhan[2];Lu, Xiwen[1]

机构：[1]East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China;[2]Shanghai Univ Finance & Econ, Sch Math, Shanghai 200433, Peoples R China

年份：2025

卷号：28

期号：4

起止页码：391

外文期刊名：JOURNAL OF SCHEDULING

收录：;EI(收录号：20252218500479);WOS:【SCI-EXPANDED(收录号:WOS:001493941000001)】；

基金：This work is supported by the National Natural Science Foundation of China (12371317).

语种：英文

外文关键词：Single-machine scheduling; Computational complexity; Maintenance activities; Approximation algorithms

摘要：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.