Single machine scheduling with bounded job rearrangements

In operations scheduling, changes in the scenario predicted beforehand (due to, e.g., disruptions, breakdowns, realizations different from expected data values) make it often necessary to revise a plan in order to meet the original objectives under the new circumstances and with the changed data. In this case, cost and/or stability issues require the consideration of solutions which do not differ too much, i.e., that can be obtained by a small number of modifications, from the original ones. In this paper we focus on a single-machine scheduling setting where we need to “adjust” a given, predefined solution, by re-sequencing jobs, but there are bounds on the number and type of allowed job shifts. We propose mathematical programming models and possible solution approaches.