Online scheduling of two type parallel jobs on identical machines

被引：0
|
作者：
郭首玮 [1 ]
康丽英 [1 ]
机构：
[1] Department of Mathematics,College of Sciences,Shanghai University
来源：
Advances in Manufacturing | 2010年 / 06期
基金：
中国国家自然科学基金;
关键词：
scheduling; parallel jobs; preemption; online algorithm; competitive analysis;
D O I：
暂无
中图分类号：
O223 [统筹方法];
学科分类号：
070105 ; 1201 ;
摘要：
In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using "temporary schedule".
引用
收藏
页码：396 / 399
页数：4
相关论文
共 50 条
  • [31] Online batch scheduling of equal-length jobs on two identical batch machines to maximise the number of early jobs
    Li, Wenjie
    Li, Shisheng
    INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2015, 46 (04) : 652 - 661
  • [32] Online scheduling of equal-length jobs on parallel machines
    Ding, Jihuan
    Ebenlendr, Tomas
    Sgall, Jiri
    Zhang, Guochuan
    ALGORITHMS - ESA 2007, PROCEEDINGS, 2007, 4698 : 427 - +
  • [33] On-line scheduling of parallel jobs on two machines
    Chan, Wun-Tat
    Chin, Francis Y. L.
    Ye, Deshi
    Zhang, Guochuan
    Zhang, Yong
    JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (01) : 3 - 10
  • [34] Scheduling two identical parallel machines with preparation constraints
    Labbi, Wafaa
    Boudhar, Mourad
    Oulamara, Ammar
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2017, 55 (06) : 1531 - 1548
  • [35] Order acceptance and scheduling on two identical parallel machines
    Wang, Xiuli
    Huang, Guodong
    Hu, Xiuwu
    Cheng, T. C. Edwin
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2015, 66 (10) : 1755 - 1767
  • [36] Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines
    Sun, Kaibiao
    Li, Hongxing
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2010, 124 (01) : 151 - 158
  • [37] Scheduling jobs with equal processing times and time windows on identical parallel machines
    Brucker, Peter
    Kravchenko, Svetlana A.
    JOURNAL OF SCHEDULING, 2008, 11 (04) : 229 - 237
  • [38] Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays
    Sevastyanov, S. V.
    Sitters, R. A.
    Fishkin, A. V.
    AUTOMATION AND REMOTE CONTROL, 2010, 71 (10) : 2093 - 2101
  • [39] Scheduling jobs with equal processing times and time windows on identical parallel machines
    Peter Brucker
    Svetlana A. Kravchenko
    Journal of Scheduling, 2008, 11 : 229 - 237
  • [40] Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays
    Fishkin, AV
    Jansen, K
    Sevastyanov, SV
    Sitters, R
    ALGORITHMS - ESA 2005, 2005, 3669 : 580 - 591
12345