Neighbourhood search-based metaheuristics for the bi-objective Pareto optimization of total weighted earliness-tardiness and makespan in a JIT single machine scheduling problem

Sona Babu and B.S. Girish

Operations Research Perspectives, 2025, vol. 14, issue C

Abstract: This paper studies the simultaneous minimization of total weighted earliness-tardiness (TWET) and makespan in a just-in-time single-machine scheduling problem (JIT-SMSP) with sequence-dependent setup times and distinct due windows, allowing idle times in the schedules. Multiple variants of variable neighbourhood descent (VND) based metaheuristic algorithms are proposed to generate Pareto-optimal solutions for this NP-hard problem. An optimal timing algorithm (OTA) is presented that generates a piecewise linear convex trade-off curve between the two objectives for a given sequence of jobs. The trade-off curves corresponding to the sequences of jobs generated in the proposed metaheuristics are trimmed and merged using a Pareto front generation procedure to generate the Pareto-optimal front comprising line segments and points. The computational performance of the proposed VND-based metaheuristic algorithms is compared with state-of-the-art metaheuristic algorithms from the literature on test instances of varying sizes using four performance metrics devised to compare Pareto fronts comprising line segments and points. The performance comparisons reveal that a proposed variant of backtrack-based iterated VND with multiple neighbourhood structures outperforms the other algorithms in most performance metrics.

Keywords: Pareto front generation; Variable neighbourhood descent; Total weighted earliness and tardiness; Makespan; Just-in-time manufacturing; Single machine scheduling (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716025000119
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:oprepe:v:14:y:2025:i:c:s2214716025000119

DOI: 10.1016/j.orp.2025.100335

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().