On the Local Dominance Properties in Single Machine Scheduling Problems

We consider a non-preemptive single machine scheduling problem for a non-negative penalty function f, where an optimal schedule satisfies the left-shifted property, i.e. in any optimal sequence all executions happen without idle time with a starting time t<inf>0</inf>≥0. For this problem, every job j has a priority weight w<inf>j</inf> and a processing time p<inf>j</inf>, and the goal is to find an order on the given jobs that minimizes ∑w<inf>j</inf>f(Cj), where C<inf>j</inf> is the completion time of job j. This paper explores local dominance properties, which provide a powerful theoretical tool to better describe the structure of optimal solutions by identifying rules that at least one optimal solution must satisfy. We propose a novel approach, which allows to prove that the number of sequences that respect the local dominance property among three jobs is only two, not three, reducing the search space from n! to n!/3⌈n/3⌉ schedules. In addition, we define some non-trivial cases for the problem with a strictly convex penalty function that admits an optimal schedule, where the jobs are ordered in non-increasing weight. Finally, we provide some insights into three future research directions based on our results (i) to reduce the number of steps required by an exact exponential algorithm to solve the problem, (ii) to incorporate the dominance properties as valid inequalities in a mathematical formulation to speed up implicit enumeration methods, and (iii) to show the computational complexity of the problem of minimizing the sum of weighted mean squared deviation of the completion times with respect to a common due date for jobs with arbitrary weights, whose status is still open. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.