An Optimal Online Algorithm for Scheduling on Two Parallel Machines with GoS Eligibility Constraints

被引：6
|
作者：
Xu J. [1 ]
Liu Z.-H. [1 ]
机构：
[1] Department of Mathematics, East China University of Science and Technology, Shanghai
来源：
Journal of the Operations Research Society of China | 2016年 / 4卷 / 03期
基金：
中国国家自然科学基金;
关键词：
Eligibility constraint; Online algorithm; Parallel machine; Scheduling;
D O I：
10.1007/s40305-016-0119-1
中图分类号：
学科分类号：
摘要：
We consider the online scheduling problem on two parallel machines with the Grade of Service (GoS) eligibility constraints. The jobs arrive over time, and the objective is to minimize the makespan. We develop a (1 + α) -competitive optimal algorithm, where α≈ 0.555 is a solution of α3- 2 α2- α+ 1 = 0. © 2016, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg.
引用
收藏
页码：371 / 377
页数：6
相关论文
共 50 条
  • [1] Online scheduling on parallel machines with two GoS levels
    Yiwei Jiang
    Journal of Combinatorial Optimization, 2008, 16 : 28 - 38
  • [2] Online scheduling on parallel machines with two GoS levels
    Jiang, Yiwei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2008, 16 (01) : 28 - 38
  • [3] Online scheduling on parallel machines with two GoS levels
    Jiang, Yiwei
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2006, 4041 : 11 - 21
  • [4] Semi-online scheduling with GoS eligibility constraints
    Lee, Kangbok
    Hwang, Hark-Chin
    Lim, Kyungkuk
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2014, 153 : 204 - 214
  • [5] On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints
    Zhang, An
    OPERATIONS RESEARCH LETTERS, 2015, 43 (05) : 522 - 525
  • [6] Optimal algorithm for semi-online scheduling on two machines under GoS levels
    Taibo Luo
    Yinfeng Xu
    Optimization Letters, 2016, 10 : 207 - 213
  • [7] Optimal parallel machines scheduling with machine availability and eligibility constraints
    Gwo-Ji Sheen
    Lu-Wen Liao
    Cheng-Feng Lin
    The International Journal of Advanced Manufacturing Technology, 2008, 36 : 132 - 139
  • [8] Optimal parallel machines scheduling with machine availability and eligibility constraints
    Sheen, Gwo-Ji
    Liao, Lu-Wen
    Lin, Cheng-Feng
    International Journal of Advanced Manufacturing Technology, 2008, 36 (1-2): : 132 - 139
  • [9] Optimal parallel machines scheduling with machine availability and eligibility constraints
    Sheen, Gwo-Ji
    Liao, Lu-Wen
    Lin, Cheng-Feng
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2008, 36 (1-2): : 132 - 139
  • [10] Optimal algorithm for semi-online scheduling on two machines under GoS levels
    Luo, Taibo
    Xu, Yinfeng
    OPTIMIZATION LETTERS, 2016, 10 (01) : 207 - 213
12345