On the local dominance properties in single machine scheduling problems

Natalia Jorquera-Bravo () and Óscar C. Vásquez ()
Additional contact information
Natalia Jorquera-Bravo: University of Santiago of Chile (USACH)
Óscar C. Vásquez: University of Santiago of Chile (USACH)

Annals of Operations Research, 2024, vol. 338, issue 1, No 12, 335-345

Abstract: Abstract 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_0 \ge 0$$ t 0 ≥ 0 . For this problem, every job j has a priority weight $$w_j$$ w j and a processing time $$p_j$$ p j , and the goal is to find an order on the given jobs that minimizes $$\sum w_j f(Cj)$$ ∑ w j f ( C j ) , where $$C_j$$ C j 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^{\lceil n/3 \rceil }$$ 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.

Keywords: Single machine scheduling problem; Local dominance properties; Search space; Computational complexity (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05801-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:338:y:2024:i:1:d:10.1007_s10479-023-05801-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-023-05801-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().