EUVIMEDEUVIMED entdecken
Crossref

An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem

Yang Yu, Xiaolong Li, Roberto Baldacci, Zhiqiao Wu, Wei Sun, Jiafu Tang, Han Zhu

INFORMS Journal on Computing · 09.06.2026

DOI: 10.1287/ijoc.2024.0704 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Computing, online erschienen am 09.06.2026. Verfasst von Yang Yu und 6 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We investigate the Unrelated Parallel Machine Scheduling Problem (UPMSP), where independent jobs need scheduling on unrelated parallel machines. Each job has a distinct processing time, a weight, and a completion time. The goal is to find an optimal schedule that minimizes the total weighted completion time. This problem has been extensively studied in the scheduling literature. To address the UPMSP, we model feasible schedules using Smith’s rule, representing them as paths on directed acyclic graphs, and derive a corresponding set-partitioning-based model. To solve the model, we introduce a branch-price-and-cut (BPC) algorithm with dynamic shrink upper bounds, incorporating state-of-the-art techniques such as the bucket graph-based labeling algorithm, limited-memory subset-row cuts, and strong branching. Notably, the proposed BPC algorithm is the first exact algorithm capable of addressing widespread real-life UPMSPs with rational-number processing times. Extensive numerical experiments demonstrate that our proposed algorithm outperforms state-of-the-art algorithms for the UPMSP with integer-valued processing times, solving larger-scale instances with up to 20 machines and 200 jobs efficiently. Furthermore, it effectively addresses real-life instances (from JD.com) with rational-number processing times involving up to 20 machines and 200 jobs. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: Financial support from the National Natural Science Foundation of China [Grants 72571039, 72322018, 72272027, 72471050, and 72171043] and the Fundamental Research Funds for the Central Universities [Grant DUT23RC(3)070] is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0704 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0704 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Zitieren

APA

Yu, Y., Li, X., Baldacci, R., Wu, Z., Sun, W., Tang, J., & Zhu, H. (2026). An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2024.0704

Vancouver

Yu Y, Li X, Baldacci R, Wu Z, Sun W, Tang J, et al. An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem. INFORMS Journal on Computing. 2026. doi:10.1287/ijoc.2024.0704

BibTeX
@article{Yu2026,
  author = {Yu, Yang and Li, Xiaolong and Baldacci, Roberto and Wu, Zhiqiao and Sun, Wei and Tang, Jiafu and Zhu, Han},
  title = {An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem},
  journal = {INFORMS Journal on Computing},
  year = {2026},
  doi = {10.1287/ijoc.2024.0704}
}
Kostenlos starten →