Rescheduling to Minimize the Maximum Lateness Under the Sequence Disruptions of Original Jobs

Qiulan Zhao () and Jinjiang Yuan
Additional contact information
Qiulan Zhao: Department of Mathematics, Nanjing University, Nanjing, Jiangsu 210093, P. R. China
Jinjiang Yuan: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2017, vol. 34, issue 05, 1-12

Abstract: We introduce and study the rescheduling on a single machine to minimize the maximum lateness under the sequence disruptions of original jobs. In the problem, each original job Jj has a constraint disruption on its sequence respect to an original optimal schedule π, i.e., Dj(π) ≤ kj. That is, if Jj is the xth job in π, then it is required that the position index y of Jj in a schedule for all jobs satisfies |y − x|≤ kj. By introducing the positive sequence disruption Dj+(π) and the negative sequence disruption Dj−(π), three problems are considered in this paper: problem (P1) is 1|Dj(π) ≤ kj|Lmax, problem (P2) is 1|Dj+(π) ≤ k j|Lmax, and problem (P3) is 1|Dj+(π) ≤ k j,Dj−(π) = 0|Lmax. We show that the three problems are equivalent and can be solved in O(nlog n) time. Then we study an extension of problem (P2): 1|prec,σ−1(j) ≤ k j|fmax. We show that the extended problem can be solved in O(n2) time.

Keywords: Rescheduling; sequence disruption; maximum lateness (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595917500245
Access to full text is restricted to subscribers

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:wsi:apjorx:v:34:y:2017:i:05:n:s0217595917500245

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595917500245

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().