Rescheduling problems with allowing for the unexpected new jobs arrival

Xingong Zhang, Win-Chin Lin and Chin-Chia Wu ()
Additional contact information
Xingong Zhang: College of Mathematics Science, Chongqing Normal University
Win-Chin Lin: Feng Chia University
Chin-Chia Wu: Feng Chia University

Journal of Combinatorial Optimization, 2022, vol. 43, issue 3, No 7, 630-645

Abstract: Abstract In modern manufacturing and services, rescheduling frequently happens in manufacturing practice, which a disruption may happen. In this paper, the rescheduling problem with the unexpected new jobs arrival is studied, and the effect of time disruptions is taken into account on a previously planned optimal schedule. Rescheduling means that a set of original jobs has already given jobs sequence by minimizing some classical objective, then a set of new jobs arrived will create a time disruption for the original jobs. Our focus is to find a feasible rescheduling to minimize maximum weighted tardiness costs under a limit of time disruptions from the original schedule. Two time disruption problems will be involved: under an upper restriction of the total time disruption and relaxing time disruption restriction. For the former case, the proof of strongly NP-hard by reducing 3-Partition problem is presented. For latter case, a strongly NP-hard proof is also given,and then a two-approximation polynomial time algorithm is presented to confirm that the latter problem has not an approximation polynomial-time algorithm, which a performance ratio is less than 2 unless $$P=NP$$ P = N P . Finally, one of the proposed algorithms is improved by three local searches, respectively, as three seeds used in simulated annealing for approximate solution. Furthermore, we also present some extensive numerical experiment to evaluate their performance.

Keywords: Rescheduling; Time disruption; Approximation algorithm; Simulated annealing (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00803-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:jcomop:v:43:y:2022:i:3:d:10.1007_s10878-021-00803-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00803-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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