Optimal sequence for single server scheduling incorporating a rate-modifying activity under job-dependent linear deterioration

Hyunjoon Kim and Byung-In Kim

European Journal of Operational Research, 2022, vol. 298, issue 2, 439-450

Abstract: This study considers single processor scheduling problems incorporating a rate-modifying activity (RMA) as well as processing time deterioration rates. The RMA fully restores the processing speed of a processor. As discussed in recent literature, the optimal position of an RMA for a single processor scheduling problem with the objective of makespan minimization, 1|p[j]A=α[j]S[j],rm|Cmax, where the processing time of a job (p[j]A:[j]denotesthejthposition)is determined by its start time (S[j])and position-dependent rate (α[j]), can be found easily. This study considers six variants of the problem: (P1) 1|p[j]A=p¯+α[j]S[j],rm|Cmax, (P1+)1|p[j]A=p¯+α[j]S[j],drm|Cmax, (P2) 1|p[i,j]A=pj+α[i]Sj,rm|Cmax, (P2+)1|p[i,j]A=pj+α[i]Sj,drm|Cmax, (P3) 1|pjA=αjSj,rm|Cmax, and (P3+)1|pjA=αjSj,drm|Cmax, where p¯ is the common basic processing time, pjis the basic processing time for job j, [i,j] is the job j scheduled at the ith position, and drm is the deteriorating RMA. We show that (P1) and (P1+), where the common basic processing time is considered, can be converted into the problem 1|p[j]A=α[j]S[j],rm|Cmax, so that the optimal position of the RMA can be found easily. In the other variants, the optimal sequences of jobs and positions of the RMA must be determined. In (P2) and (P2+), the basic processing time for each job (pj)is considered, whereas, in (P3) and (P3+), the deterioration rate depends not on the position of the job (α[j]) but on the job itself (αj). We show that the optimal schedules for (P2), (P2+) and (P3), (P3+) can be found by solving the assignment problems and the knapsack problems, respectively.

Keywords: Scheduling; Single processor scheduling; Rate-modifying activity; Job-dependent linear deterioration rate; Optimal policy (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721006184
Full text for ScienceDirect subscribers only

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:eee:ejores:v:298:y:2022:i:2:p:439-450

DOI: 10.1016/j.ejor.2021.07.023

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().