|
|||||
|
|
| 带有到达时间和拒绝费用工件的同类机排序问题 | |
| 引用本文： | 荣建华,侯丽英. 带有到达时间和拒绝费用工件的同类机排序问题[J]. 浙江大学学报(理学版), 2016, 43(5): 545-549. DOI: 10.3785/j.issn.1008-9497.2016.05.009 |
| 作者姓名： | 荣建华 侯丽英 |
| 作者单位： | 1. 石家庄铁道大学四方学院 基础部, 河北 石家庄 050000; 2. 南京农业大学 理学院, 江苏 南京 210095 |
| 基金项目： | 南京农业大学青年科技创新基金项目（0506J0116）；河北省高等教育教学改革研究与实践项目（2015GJJG293）；河北省高等教育科学研究课题（GJXH2015-291）. |
| 摘 要： | 研究了工件带有拒绝费用的m台同类机在线排序问题，m台机器的速度分别为s1=s2=…=sm-1=1，sm=s，当工件到达时，可以接收加工，占用一定的加工时间，也可以拒绝，付出相应的罚值. 目标是被接收工件的最长完工时间（makespan）与被拒绝工件的总罚值之和最小. 对工件2次到达时间问题（零时刻和r时刻各到达一批工件）设计了在线算法H，并证明该算法的竞争比为4-（2s）/（s+m-1）. |
| 关 键 词： | 在线排序 同类机 拒绝费用 竞争比 |
| 收稿时间： | 2015-10-29 |
Uniform machine scheduling with arrival time and rejection |
|
| RONG Jianhua,HOU Liying. Uniform machine scheduling with arrival time and rejection[J]. Journal of Zhejiang University(Sciences Edition), 2016, 43(5): 545-549. DOI: 10.3785/j.issn.1008-9497.2016.05.009 | |
| Authors: | RONG Jianhua HOU Liying |
| Affiliation: | 1. Department of Basic, Shijiazhuang Tiedao University Sifang College, Shijiazhuang 050000, China; 2. College of Sciences, Nanjing Agricultural University, Nanjing 210095, China |
| Abstract: | An on-line scheduling problem on m uniform machines with arrival time and rejection is investigated. The speeds of the machines are respectively s1=s2=…=sm-1=1, sm=s. When a job arrives, it can either be assigned to a certain machine or be rejected by paying penalty. The objective is to minimize the sum of the makespan of all accepted jobs and the total penalty of the rejection. In addition, for jobs that arrive at two different times, namely zero and r, we propose an on-line approximation algorithm H with competitive ratio is 4-(2s)/(s+m-1). |
| Keywords: | on-line scheduling uniform machine rejection competitive ratio |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 | |
| 点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文 | |