带有到达时间和拒绝费用工件的同类机排序问题

• 作者: 侯丽英 荣建华
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 在线排序 同类机 拒绝费用 竞争比
• 年，卷（期）: 2016,（5）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 545-549
• 页数: 5页
• 分类号: O223
• 字数: 4102字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2016.05.009

摘要

研究了工件带有拒绝费用的 m台同类机在线排序问题，m台机器的速度分别为s1＝ s2＝?＝ sm－1＝1，sm＝s，当工件到达时，可以接收加工，占用一定的加工时间，也可以拒绝，付出相应的罚值．目标是被接收工件的最长完工时间（makespan）与被拒绝工件的总罚值之和最小．对工件2次到达时间问题（零时刻和 r时刻各到达一批工件）设计了在线算法H ，并证明该算法的竞争比为4－2ss＋ m－1．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	荣建华	石家庄铁道大学四方学院基础部	12	1	1.0	1.0
2	侯丽英	南京农业大学理学院	7	2	1.0	1.0