三台可拒绝平行机在线排序问题的近似算法

作     者：荣建华 侯丽英 Rong Jianhua;Hou Liying

作者机构：石家庄铁道大学四方学院河北石家庄051132 南京农业大学理学院江苏南京210095 

基　　金：南京农业大学青年科技创新基金(0506J0116) 河北省高等教育教学改革研究与实践项目(2015GJJG293) 河北省高等教育科学研究课题(GJXH2015-291) 

出 版 物：《石家庄铁道大学学报（自然科学版）》 (Journal of Shijiazhuang Tiedao University(Natural Science Edition))

年 卷 期：2017年第30卷第2期

页      码：101-104,110页

摘      要：研究了工件带有拒绝费用的3台平行机在线算法,假定有3台平行机M_1,M_2,M_3,n个工件J_1,J_2,…,J_n,每个工件可以被接收加工,消耗一定的加工时间tj;也可以被拒绝,但要付出相应的拒绝费用pj,目标为被接收工件的最大完工时间(makespan)与被拒绝工件的总罚值之和最小。进一步,假定每个工件有两套拒绝策略,最后输出目标值较好的一种。文中设计出在线算法H,并证明算法的竞争比为15/8。

主 题 词：同型机 拒绝费用 中断加工 运筹学 在线排序 竞争比 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.13319/j.cnki.sjztddxxbzrb.2017.02.18

馆 藏 号：203232119...