Mathematical models and an effective exact algorithm for unrelated parallel machine scheduling with family setup times and machine cost

Kai Li (), Fulong Xie (), Jianfu Chen (), Wei Xiao () and Tao Zhou ()
Additional contact information
Kai Li: Hefei University of Technology
Fulong Xie: Hefei University of Technology
Jianfu Chen: Hefei University of Technology
Wei Xiao: Hohai University
Tao Zhou: Hefei University of Technology

OR Spectrum: Quantitative Approaches in Management, 2025, vol. 47, issue 1, No 5, 129-176

Abstract: Abstract This paper investigates unrelated parallel machine scheduling problems, considering machine- and sequence-dependent family setup times and machine usage costs to minimise the sum of the total weighted completion time and the total machine usage cost. The machine usage cost consists of a fixed cost and a variable cost proportional to the processing times of jobs. These features align with numerous real-world applications that include machine usage costs, for example, rental fees when customers rent machines via a cloud manufacturing platform. To address the problem, five integer programming models are developed from different perspectives. Afterwards, a modified branch-and-price algorithm (B&P) based on the set-partitioning model is proposed. To enhance the performance of B&P, we introduce two dynamic programming algorithms and a heuristic pricing algorithm, and the initial solution is generated by an improved variable neighbourhood search algorithm. Extensive experimental results show that the proposed B&P outperforms state-of-the-art mathematical models and algorithms. Notably, B&P can optimally solve instances with up to 10 machines, 100 jobs, and 12 families within half an hour. Interestingly, experimental results also show that the B&P performs significantly better when total completion time is dominated by the total variable cost of machine usage.

Keywords: Scheduling; Unrelated parallel machines; Family setup times; Machine cost; Branch-and-price algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00291-024-00778-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:orspec:v:47:y:2025:i:1:d:10.1007_s00291-024-00778-8

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-024-00778-8

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().