Pareto optimization of rescheduling with release dates to minimize makespan and total sequence disruption

We consider the rescheduling on a single machine with release dates to minimize the makespan and total sequence disruption simultaneously. In the literature, a polynomial‐time algorithm was presented for minimizing the makespan under a limit on the total sequence disruption. But the algorithm is not strongly polynomial. We present a strongly polynomial‐time algorithm for finding all Pareto optimal points of the Pareto optimization problem. Consequently, the rescheduling to minimize the makespan under a limit on the total sequence disruption can be solved in a strongly polynomial time.