Abstract: Responding reactively in scheduling environments subject to uncertainty may be modeled using reoptimization. Reoptimization begins by optimally solving an initial problem instance which is subsequently perturbed. The new objective is to update the initial optimal solution into a good solution for the new instance. We propose greedy algorithms and prove that they are efficient and tight for a variety of perturbations. In the case of job rejection or processing time reduction, reoptimization starting from an arbitrary optimal solution is not effective. But if our initial solution is lexicographic optimal, then we achieve a much better ratio. This result implies that reoptimization should be considered a two-step process where the phase of initial optimization has its own significance. For the initial phase, we propose a novel, branch-and-bound lexicographic optimization approach using vectorial bounds. Computational experiments with respect to the standard, weighted method validate our algorithm. This work is joint with Dr Dimitris Letsios.