Scheduling equal-length jobs with delivery times on identical processors

被引:3
作者
Vakhania, N
机构
[1] State Univ Morelos, Fac Sci, Cuernavaca 62210, Morelos, Mexico
[2] Inst Computat Math, Tbilisi 93, Georgia
关键词
scheduling identical processors; release time; delivery time; computational complexity;
D O I
10.1080/00207160211288
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The problem of scheduling n jobs of equal duration p with release and delivery times on m identical processors with the objective to minimize the maximal job completion time is considered. An algorithm is proposed that has the time complexity O(mn log n) if the maximal job delivery time q(max) is bounded by some constant. This is better than the earlier known best bound of O(mn(2)log(np/m)) for the version of the problem with non-restricted q(max). The algorithm has the time complexity O(q(max)(2) n log n max {m, q(max) }) without the restriction on q(max). As the presented computational experiments show, practical behavior of the algorithm remains good without restriction on q(max), i.e., for arbitrarily long delivery times, the running time of the algorithm, in practice, does not depend on q(max).
引用
收藏
页码:715 / 728
页数:14
相关论文
共 50 条
[41]   Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts [J].
Liu, Hai-Ling ;
Lu, Xi-Wen .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2022, 10 (01) :113-131
[42]   Delivery Times Scheduling with Deterioration Effects in Due Window Assignment Environments [J].
Mao, Rong-Rong ;
Wang, Yi-Chun ;
Lv, Dan-Yang ;
Wang, Ji-Bo ;
Lu, Yuan-Yuan .
MATHEMATICS, 2023, 11 (18)
[43]   Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts [J].
Hai-Ling Liu ;
Xi-Wen Lu .
Journal of the Operations Research Society of China, 2022, 10 :113-131
[44]   A best on-line algorithm for single machine scheduling with small delivery times [J].
Tian, Ji ;
Fu, Ruyan ;
Yuan, Jinjiang .
THEORETICAL COMPUTER SCIENCE, 2008, 393 (1-3) :287-293
[45]   A best possible online algorithm for parallel batch scheduling with delivery times and limited restart [J].
Hailing Liu ;
Xiwen Lu ;
Wenjie Li .
Optimization Letters, 2021, 15 :1155-1173
[46]   Bounding Strategies for the Parallel Processors Scheduling Problem With No-Idle Time Constraint, Release Date, and Delivery Time [J].
Hidri, Lotfi ;
Al-Samhan, Ali M. ;
Mabkhot, Mohammed M. .
IEEE ACCESS, 2019, 7 :170392-170405
[47]   Common due date assignment and single-machine scheduling with release times to minimize the weighted number of tardy jobs [J].
Zhao, Chuanli .
JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS, 2016, 33 (01) :239-249
[48]   Common due date assignment and single-machine scheduling with release times to minimize the weighted number of tardy jobs [J].
Chuanli Zhao .
Japan Journal of Industrial and Applied Mathematics, 2016, 33 :239-249
[49]   Single-machine scheduling with past-sequence-dependent delivery times and learning effect [J].
Yang, Suh-Jenq ;
Hsu, Chou-Jung ;
Chang, Teng-Ruey ;
Yang, Dar-Li .
JOURNAL OF INDUSTRIAL AND PRODUCTION ENGINEERING, 2011, 28 (04) :247-255
[50]   A branch-and-bound algorithm for identical parallel-machine total completion time scheduling problem with preemption and release times [J].
Liaw, Ching-Fang .
JOURNAL OF INDUSTRIAL AND PRODUCTION ENGINEERING, 2016, 33 (06) :383-390