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

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/.