A bi-objective approach to reschedule new jobs in a one machine model

We consider a one machine scheduling model, minimizing a classical objective function–either the total completion time or the maximum tardiness–and with two sets of jobs: one with initial jobs already scheduled and one with new jobs that must be inserted in the schedule. As such rescheduling can create a modification of the schedule of the initial jobs, a disruption objective is considered in addition to the original objective. This additional objective can be formulated in four different ways. Such model has been introduced by Hall and Potts, minimizing either a linear aggregation of the two objectives or the initial objective under a constraint giving an upper limit of the disruption objective. In this paper, the aim is to obtain the set of efficient schedules in regard to the two objectives. Algorithms are provided for the eight possible bi‐objective problems and illustrated by some didactic examples.