Randomized on-line scheduling similar jobs to minimize makespan on two identical processors

被引：1
作者：
Du D.-L. [1 ]
机构：
[1] Faculty of Administration, University of New Brunswick, Fredericton, NB E3B 5V4
来源：
Acta Mathematicae Applicatae Sinica | 2005年 / 21卷 / 3期
关键词：
On-line algorithm; Preemption; Randomized algorithm; Scheduling;
D O I：
10.1007/s10255-005-0255-6
中图分类号：
学科分类号：
摘要：
In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to minimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound. © Springer-Verlag 2005.
引用
收藏
页码：485 / 488
页数：3
相关论文
共 50 条
[21]   Scheduling Three-Operation Jobs in a Two-Machine Flow Shop to Minimize Makespan [J].
Jatinder N.D. Gupta ;
Christos P. Koulamas ;
George J. Kyparisis ;
Chris N. Potts ;
Vitaly A. Strusevich .
Annals of Operations Research, 2004, 129 :171-185
[22]   Scheduling three-operation jobs in a two-machine flow shop to minimize makespan [J].
Gupta, JND ;
Koulamas, CP ;
Kyparisis, GJ ;
Potts, CN ;
Strusevich, VA .
ANNALS OF OPERATIONS RESEARCH, 2004, 129 (1-4) :171-185
[23]   Online scheduling of two type parallel jobs on identical machines [J].
郭首玮 ;
康丽英 .
Advances in Manufacturing, 2010, (06) :396-399
[24]   Scheduling tool changes and special jobs on a single machine to minimize makespan [J].
Xu, Dehua ;
Liu, Min ;
Yin, Yungqiang ;
Hao, Jinghua .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2013, 41 (02) :299-304
[25]   Online scheduling of parallel jobs with preemption on two identical machines [J].
Guo, Shouwei ;
Kang, Liying .
OPERATIONS RESEARCH LETTERS, 2013, 41 (02) :207-209
[26]   Online scheduling on a single machine with one restart for all jobs to minimize the weighted makespan [J].
Liang, Xiaoxiao ;
Lu, Lingfa ;
Sun, Xueke ;
Yu, Xue ;
Zuo, Lili .
AIMS MATHEMATICS, 2024, 9 (01) :2518-2529
[27]   Scheduling parallel identical machines to minimize makespan: A parallel approximation algorithm [J].
Ghalami, Laleh ;
Grosu, Daniel .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2019, 133 :221-231
[28]   Optimal preemptive online scheduling to minimize lp norm on two processors [J].
Du, Donglei ;
Jiang, Xiaoyue ;
Zhang, Guochuan .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2005, 1 (03) :345-351
[29]   On-line scheduling of parallel jobs with runtime restrictions [J].
Bischof, S ;
Mayr, EW .
THEORETICAL COMPUTER SCIENCE, 2001, 268 (01) :67-90
[30]   Simultaneously scheduling n jobs and the preventive maintenance on the two-machine flow shop to minimize the makespan [J].
Allaoui, H. ;
Lamouri, S. ;
Artiba, A. ;
Aghezzaf, E. .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2008, 112 (01) :161-167
12345