Optimization of scheduling problems with deterioration effects and an optional maintenance activity

Xinyu Sun (), Tao Liu, Xin-Na Geng (), Yang Hu and Jing-Xiao Xu
Additional contact information
Xinyu Sun: Xi’an Jiaotong University
Tao Liu: Xi’an Jiaotong University
Xin-Na Geng: Xi’an Jiaotong University
Yang Hu: Shenyang Aerospace University
Jing-Xiao Xu: Shenyang Aerospace University

Journal of Scheduling, 2023, vol. 26, issue 3, No 2, 266 pages

Abstract: Abstract In this investigation, the single-machine scheduling problem with deterioration effects and an optional maintenance activity is explored. Deterioration effect means that the actual processing time of the job is a function of its normal processing time and its starting time. As an optional maintenance activity, the machine will perform a maintenance activity. After the maintenance activity is completed, the machine will return to the initial state, and the job deterioration will start again. The goal is to determine an optimal sequence and the location of the maintenance activity that minimizes some objective functions. We prove that the problem of minimizing the makespan, total completion time, and total absolute differences in completion (waiting) times can be solved in polynomial time $$O(n^4)$$ O ( n 4 ) , where n is the number of jobs. For the total weighted completion time minimization, if the weights are positional-dependent weights, we prove that the problem can be solved in polynomial time; if the weights are job-dependent weights, this problem is NP-hard. To solve the problem with job-dependent weights, we present the heuristic, tabu search, and branch-and-bound algorithms.

Keywords: Deterioration effect; Rate-modifying activity; Scheduling; Single machine (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00756-4 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:26:y:2023:i:3:d:10.1007_s10951-022-00756-4

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

DOI: 10.1007/s10951-022-00756-4

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 ().