Lower bounds for scheduling on identical parallel machines with heads and tails

被引：10

作者：

Haouari, M ^{[1
]}

Gharbi, A ^{[1
]}

机构：

[1] Ecole Polytech Tunisie, Lab Math Engn, La Marsa, Tunisia

来源：

ANNALS OF OPERATIONS RESEARCH | 2004年 / 129卷 / 1-4期

关键词：

scheduling; identical parallel machines; release dates; delivery times; makespan; lower bound;

D O I：

10.1023/B:ANOR.0000030688.31785.40

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we investigate new lower bounds for the P|r(j), q(j) | C-max scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP-hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.

引用

页码：187 / 204

页数：18

共 50 条

[31] Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates
Kedad-Sidhoum, Safia
Solis, Yasmin Rios
Sourd, Francis
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 189 (03) : 1305 - 1316
[32] Online scheduling of parallel jobs with preemption on two identical machines
Guo, Shouwei
Kang, Liying
OPERATIONS RESEARCH LETTERS, 2013, 41 (02) : 207 - 209
[33] Parallel solutions for preemptive makespan scheduling on two identical machines
Leah Epstein
Journal of Scheduling, 2023, 26 : 61 - 76
[34] Online scheduling of two type parallel jobs on identical machines
郭首玮
康丽英
Advances in Manufacturing, 2010, (06) : 396 - 399
[35] Preemptive scheduling on two identical parallel machines with a single transporter
Hans Kellerer
Alan J. Soper
Vitaly A. Strusevich
Journal of Combinatorial Optimization, 2013, 25 : 279 - 307
[36] Scheduling Jobs with Stochastic Processing Time on Parallel Identical Machines
Stec, Richard
Novak, Antonin
Sucha, Premysl
Hanzalek, Zdenek
PROCEEDINGS OF THE TWENTY-EIGHTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2019, : 5628 - 5634
[37] A note on scheduling identical parallel machines with preemptions and setup times
Boudhar, Mourad
Dolgui, Alexandre
Haned, Amina
Kerdali, Abida
Kovalev, Sergey
Kovalyov, Mikhail Y.
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2025, 63 (03) : 1203 - 1208
[38] On the Complexity of Scheduling Problems with a Fixed Number of Parallel Identical Machines
Jansen, Klaus
Kahler, Kai
SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2023, 13878 : 192 - 206
[39] Efficient Variable Neighborhood Search for Identical Parallel Machines Scheduling
Chen Jing
Li Jun-qing
PROCEEDINGS OF THE 31ST CHINESE CONTROL CONFERENCE, 2012, : 7228 - 7232
[40] Scheduling identical parallel machines involving flexible maintenance activities
Li, Chunhao
Wang, Feng
Gupta, Jatinder N. D.
Chung, Tsui-Ping
EXPERT SYSTEMS WITH APPLICATIONS, 2025, 263

← 1 2 3 4 5 →