Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

In this paper, we consider semi-online minimum makespan scheduling problem with reassignment on two identical machines. Two versions are discussed. In the first version, one can reassign the last job of one machine that is based on the problem proposed by Tan and Yu (2008) [1], in which case the last job of each machine is allowed to be reassigned. An optimal algorithm which has the same competitive ratio 2 is presented. In the second version we consider the combination of the next two conditions: the total size of all jobs is known in advance and one can reassign the last job of one machine. For this problem an optimal algorithm with competitive ratio 54 is also given.

Research highlights
► An identical machines scheduling problem with reassignment is considered.
► An optimal algorithm with competitive ratio for this model is obtained.
► Another scheduling problem with reassignment and known sum is studied.
► An optimal algorithm with competitive ratio 5/4 for it is presented.