A branch-and-price algorithm for unrelated parallel machine scheduling with machine usage costs

Jianfu Chen, Chengbin Chu, Abderrahim Sahli and Kai Li

European Journal of Operational Research, 2024, vol. 316, issue 3, 856-872

Abstract: This paper considers unrelated parallel machine scheduling involving machine usage costs, in addition to classic job completion time-related costs. The usage cost of each machine is made up of a fixed usage cost and a variable usage cost proportional to the total processing time of the jobs assigned to it. These features model many practical situations where machine usage costs include, for example, rental fees when the machines are not owned but rented. To tackle this problem, four mathematical models based on the Shortest Weighted Processing Time (SWPT) rule are introduced. Additionally, the problem is formulated into a set-partitioning model, for which a branch-and-price algorithm is proposed with an appropriate branching strategy. This facilitates the development of an efficient pseudo-polynomial dynamic programming algorithm and a polynomial-time heuristic to solve the pricing problem. Extensive numerical experiments demonstrate the superior performance of the proposed branch-and-price algorithm over the four SWPT-based mathematical formulations and an existing branch-and-price algorithm designed for a special case. Notably, it can optimally solve instances involving up to 225 jobs and 15 machines within one hour. Moreover, statistical analyses reveal that the proposed polynomial-time heuristic significantly reduces the computation time, and the mathematical model based on the contribution of every job to the total weighted completion time exhibits the best overall performance.

Keywords: Parallel machine scheduling; Total weighted completion time; Machine usage costs; Column generation; Branch-and-price (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/S0377221724001851
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:316:y:2024:i:3:p:856-872

DOI: 10.1016/j.ejor.2024.03.011

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