English

运筹学学报

• 运筹学 • 上一篇    下一篇

两台带服务等级的可拒绝同型机排序问题的在线算法

闵啸1,* 朱俊蕾1   刘静1   

  1. 1. 嘉兴学院数理与信息工程学院, 浙江嘉兴 314001
  • 收稿日期:2016-11-14 出版日期:2018-09-15 发布日期:2018-09-15
  • 通讯作者: 闵啸 E-mail: mxggppt@126.com
  • 基金资助:

    浙江省高等学校访问学者专业发展项目(No. FX2014074), 嘉兴学院科研重点项目(No. 70112023BL)

An online algorithm for hierarchical scheduling on two identical machines with rejection

MIN Xiao1,*   ZHU Junlei1   LIU Jing1   

  1. 1. College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing 314001,  Zhejiang, China
  • Received:2016-11-14 Online:2018-09-15 Published:2018-09-15

PDF

150

摘要：

两台同型机M_1,M_2, 加工速度一致, 但拥有不同的加工能力，用其服务等级表示, M_1的服务等级为1, M_2的服务等级为2. 工件j按列表在线到达，每个工件带有三个参数: 长度t_j,等级g_j=1或2, 罚值p_j. 当j到达时, 可以被拒绝, 但要付出相应的罚值p_j, 也可以被接受并分配给服务等级不超过该工件等级的机器加工，事实上等级为1的工件只能分给M_1加工, 等级为2的工件可以分给M_1或M_2加工, 加工不允许中断. 目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和. 对于该问题给出了一个在线算法, 其竞争比为11/6, 以及问题一个下界5/3.

关键词: 在线排序, 同型机, 服务等级, 可拒绝, 竞争比

Abstract:

 Two identical machines M_{1}, M_{2} with same speed but different processing capabilities labeled by their hierarchies are provided. M_{1} has the hierarchy 1 and that of M_2 is 2. Jobs come one by one over list. Each job has three parameters: size t_{j}, hierarchy g_{j}=1,2, penalty p_{j}. When a job arrives, which can be rejected by paying its penalty or be accepted and scheduled on some machine whose hierarchy does not exceed the job's hierarchy. In fact, the job with hierarchy 1 can only be assigned to M_{1}, but the job with hierarchy 2 can be assigned to M_{1} or M_{2} . Preemption is not allowed. The objective is to minimize the sum of makespan yielded by all accepted jobs and the total penalties of all rejected jobs. For this problem, we present an online algorithm with a competitive ratio 11/6 and a relative lower bound 5/3.

Key words: online scheduling, identical machines, hierarchy, rejection, competitive ratio