Rescheduling problems with allowing for the unexpected new jobs arrival

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$$ . 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.