Abstract: In the rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives and creates a disruption. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. In this paper, we consider hierarchical optimization between the scheduling cost of all the jobs and the degree of this disruption. For every problem, we provide either a polynomial time algorithm or an intractable result. 

Key words: rescheduling, hierarchical optimization, time disruption, sequence disruption;
single machine