Brief Announcement: New Pruning Rules for Optimal Task Scheduling on Identical Parallel Machines

被引：0

作者：

Akram, Matthew ^{[1
]}

Schreiber, Dominik ^{[1
]}

机构：

[1] Karlsruhe Inst Technol, Karlsruhe, Baden Wurttembe, Germany

来源：

PROCEEDINGS OF THE 36TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2024 | 2024年

基金：

欧洲研究理事会;

关键词：

scheduling; branch and bound; combinatorial optimization;

D O I：

10.1145/3626183.3660268

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We address optimal makespan-minimizing identical parallel machine scheduling (P vertical bar vertical bar C-max) by introducing new pruning rules for branch-and-bound (BnB) and integrating them into a prior BnB algorithm. Experimental results indicate that the presented rules are inexpensive to evaluate, applicable frequently, and extremely beneficial to the BnB algorithm's overall performance.

引用

页码：137 / 139

页数：3

共 9 条

[1]

Berndt S, 2022, Algorithm Eng Exp, P104

[2]

Dell'Amico M., 1995, ORSA Journal on Computing, V7, P191, DOI 10.1287/ijoc.7.2.191

[3] STRONG NP-COMPLETENESS RESULTS - MOTIVATION, EXAMPLES, AND IMPLICATIONS [J].

GAREY, MR ;

JOHNSON, DS .

JOURNAL OF THE ACM, 1978, 25 (03) :499-508

[4]

Graham R. L., 1979, Discrete Optimisation, P287

[5] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].

GRAHAM, RL .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+

[6]

Haouari M., 2006, International Transactions in Operational Research, V13, P529, DOI 10.1111/j.1475-3995.2006.00562.x

[7]

Haouari Mohamed, 2008, International Transactions in Operational Research, V15, P19, DOI 10.1111/j.1475-3995.2007.00605.x

[8]

Lawrinenko Alexander, 2017, Ph. D. Dissertation

[9] An Arc-Flow Model fo the Makespan Minimization Problem on Identical Parallel Machines [J].

Mrad, Mehdi ;

Souayah, Nizar .

IEEE ACCESS, 2018, 6 :5300-5307

← 1 →