A bi-objective unrelated parallel machine scheduling problem with additional resources and soft precedence constraints

Mengxing Gao, ChenGuang Liu and Xi Chen

European Journal of Operational Research, 2025, vol. 325, issue 1, 53-66

Abstract: This paper investigates an unrelated parallel machine scheduling problem with practical production constraints, where the upper limit of additional resources varies across distinct time intervals, and the precedence relationships between jobs can be violated by paying specified penalty costs. We formulate a novel mixed integer linear programming model to minimize the makespan and total penalty cost simultaneously. To tackle this problem, we utilize the framework of the multi-objective evolutionary algorithm based on decomposition, which decomposes the original problem into multiple scalar subproblems. In solving each subproblem, we propose three decoding algorithms to explore different solution spaces in the Pareto front and design a cyclic decoding mechanism inspired by the greedy idea. Furthermore, a 2-swap local search strategy is applied in the evolutionary process to enhance the proposed algorithm. Computational experiments on extensive numerical instances indicate that the cyclic decoding mechanism performs better than the single decoding algorithm. The results of small-scale instances show that the evolutionary algorithms, regardless of using the 2-swap local search, outperform the MILP model in terms of computational efficiency when achieving the optimal Pareto front. For large-scale instances, applying the 2-swap local search strategy significantly enhances the quality of the Pareto front, albeit at the cost of a substantial increase in computational time. The results also demonstrate the superior effectiveness and efficiency of the proposed algorithm compared to NSGA-II.

Keywords: Scheduling; Unrelated parallel machine; Additional resources; Soft precedence constraint; Multi-objective optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725002164
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:325:y:2025:i:1:p:53-66

DOI: 10.1016/j.ejor.2025.03.019

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 ().