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. For this problem every job j has a priority weight wj and a processing time pj, and the goal is to find an order on the given jobs that minimizes Σ wj (Cj), where Cj is the completion time of job j. This paper explores the local dominance properties in this problem, 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, reducing the search space from n! to n!=3n/3 schedules and providing insights to show the computational complexity status for problem with a convex penalty from a general framework, such as the problem of minimizing the sum of weighted mean squared deviation of the completion times with respect to a common due date and jobs with arbitrary weights. © 2022 by SCITEPRESS–Science and Technology Publications, Lda.