Exact and heuristic algorithms for minimizing the makespan on a single machine scheduling problem with sequence-dependent setup times and release dates

Rafael Morais, Teobaldo Bulhões and Anand Subramanian

European Journal of Operational Research, 2024, vol. 315, issue 2, 442-453

Abstract: This paper proposes efficient exact and heuristic approaches for minimizing the makespan on a single machine scheduling problem with sequence-dependent setup times and release dates. The exact procedure consists of a branch-and-price (B&P) algorithm implemented over an arc-time-indexed formulation with a pseudo-polynomial number of variables and constraints. Our B&P algorithm includes several modern features, such as a dynamic ng-path relaxation and a bidirectional labeling method for efficiently solving the pricing subproblem. The proposed heuristic algorithm is based on the iterated local search framework that employs a beam search approach adapted from the literature for generating initial solutions and an efficient scheme to perform move evaluations in amortized constant time. Computational experiments were carried out on benchmark instances containing 1800 instances ranging from 25 to 150 jobs. The results obtained attest the high performance of both the exact and heuristic algorithms in obtaining high-quality bounds when compared to existing methods. We report improved lower and upper bounds for the vast majority of the instances, as well as optimal solutions for 42.7% of the instances.

Keywords: Scheduling; Release dates; Column generation; Metaheuristics (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723008652
Full text for ScienceDirect subscribers only

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:eee:ejores:v:315:y:2024:i:2:p:442-453

DOI: 10.1016/j.ejor.2023.11.024

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().