Abstract: In this paper, we consider two single machine rescheduling problems with deteriorating jobs under sequence disruptions, the actual processing time of a job is a linear function of the starting time for deteriorating job. Rescheduling means that a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. We consider the rescheduling problem to minimize the total lateness under a limit of the sequence disruption for deteriorating job. We research the properties of feasible schedules and optimal schedules for two problems, the jobs in the set of original jobs or new jobs are ordered by non-decreasing order of the processing rate alpha_j. For each problem, the polynomial algorithm is proposed by sorting by stages or dynamic programming method, respectively.

Key words: sequence disruption, deadline, total lateness, actual processing time