Lagrangian relaxation and branch-and-price algorithm for resource assignment problem in divisional seru systems

Shiming Chen, Chengkuan Zeng, Yu Zhang, Jiafu Tang and Chongjun Yan

European Journal of Operational Research, 2025, vol. 327, issue 2, 432-449

Abstract: This paper addresses seru formation problem in divisional seru production system (SPS), which focuses on job-seru assignment, worker-seru assignment and operation-worker assignment in each seru. The problem is formulated as a mixed-integer nonlinear programming (MINLP) model with the objective of minimizing training and processing costs of workers. Once the job-seru assignment is determined, we employ a mixed-integer linear programming (MILP) model to describe worker-seru and operation-worker assignment in each seru. To tackle this challenge, we propose a two-phase approach to deal with this problem. In the first phase, we propose a Lagrangian relaxation algorithm to determine job-seru assignment, this approach can quickly compute the lower bound of the MILP by enumerating all possible job-seru assignments and eliminate unpromising ones. Subsequently, in the second phase, for each remaining job-seru assignment, we develop a branch-and-price algorithm to solve the MILP exactly. It is in the branch-and-bound framework, each node is solved by column generation (CG) algorithm. In CG, we apply a Dantzig Wolfe decompose to divide the original problem into a master problem and the pricing problems. A novel label-setting algorithm is employed based on the characteristics of the pricing problem. Additionally, we introduce effective acceleration strategies such as dominance rules and heuristic pricing. It facilitates the selection of the optimal job-seru assignment and obtains the optimal solution for the entire problem. Finally, extensive experiments validate the effectiveness and superiority of our proposed algorithm. We also discuss the impact of selected parameters on the cost and offer managerial insights.

Keywords: Combinatorial optimization; Lagrangian relaxation; Branch-and-price algorithm; Seru formation; Divisional SPS (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725001742
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:327:y:2025:i:2:p:432-449

DOI: 10.1016/j.ejor.2025.02.038

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