| 带拒绝费用的平行机在线排序 |
| On line Scheduling on Identical Machines with Rejection |
| 投稿时间：2015-04-06 |
| 中文关键词:在线排序； 竞争比； 同型机； 拒绝费用；不可中断 运筹学 |
| 英文关键词:on line scheduling competitive ratio identical machine rejection nonpreemptive operations research |
| 基金项目:国家自然科学基金（11426133）, 南京农业大学青年科技创新基金（0506J0116） |
|
| 摘要点击次数: 1179 |
| 全文下载次数: 893 |
| 中文摘要: |
| 研究了工件带有拒[WTBX]绝费用的m台平行机在线算法，假定有m台平行机[WTBX]M1,M2,…,Mm，n个工件J1,J2,…,Jn,每个工件的加工时间与拒绝费用成固定的比例α(α≥0)，即pj=αtj，当α较大时，即工件的拒绝费用相对于加工时间较大，则将此工件接收加工；当α较小时，即每个工件的拒绝费用相对于其加工时间较小，此时将工件拒绝。文中设计出在线算法[WT]PRLS,并证明算法的竞争比为关于参数α的分段函数，且为紧界。 |
| 英文摘要: |
| This paper investigates the on line scheduling problem on m identical machines with rejection . An identical processors system denoted by and a sequence of independent jobs are given.We assume that the processing time of each job and its penalty forms the regular proportion denoted by.The objective is to minimize the sum of the makespan produced by the accepted jobs and the total penalty of the jobs which have been rejected.Preemption is not allowed.For this version,we present an on line algorithm and prove the competitive ratio. |
| 荣建华,侯丽英.带拒绝费用的平行机在线排序[J].石家庄铁道大学学报：自然科学版,2016,(2):107-110. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
| 关闭 |