A new efficient algorithm for the single-machine sequencing problem with anticipation and delay under fixed permutation

We consider the single-machine scheduling problem with earliness and tardiness under
a fixed permutation. In this problem, a set of jobs must be processed on a single machine according
to a fixed order and without preemption, so as to minimize the sum of earliness and tardiness pe-
nalties. We propose a new exact two-phase greedy algorithm with time complexity O(n log n) that
provides a simpler, more intuitive, and more straightforward-to-implement alternative to the exis-
ting approach in the literature, with potential for greater computational efficiency in practice. In the
first phase, the jobs are scheduled as early as possible. In the second phase, a greedy right-shifting
procedure is applied, postponing the schedule as much as possible without increasing the objec-
tive value. Finally, the method is embedded into a metaheuristic to explore different permutations
and evaluate its performance as an exact solver for a subproblem within a more general solution
procedure.