| 两个加工时间恶化的半线性平行机排序问题的启发式MBLS 算法 |
| |
| 引用本文： | 程明宝,孙世杰.两个加工时间恶化的半线性平行机排序问题的启发式MBLS 算法[J].上海大学学报(英文版),2007,11(5):451-456. |
| |
| 作者姓名： | 程明宝 孙世杰 |
| |
| 作者单位： | Department of Mathematics College of Sciences,Shanghai University,Department of Mathematics,College of Sciences,Shanghai University,Shanghai 200444,P.R.China,Shanghai 200444,P.R.China |
| |
| 摘 要： | The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered. In the first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, bj ∈0, α], where 0 〈α≤ 1 and bj denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is known in advance, that is, b = max1≤j≤n {bj }. For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same time, the worst-case ratio of the list （LS） algorithm is investigated and it is proved that all the ratios are tight.
|
| 关 键 词： | 加工时间 半线性平行机排序问题 启发式 MBLS算法 |
| 收稿时间： | 22 December 2005 |
| 修稿时间： | 2005-12-22 |
A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs |
| |
| CHENG Ming-bao,SUN Shi-jie.A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs[J].Journal of Shanghai University(English Edition),2007,11(5):451-456. |
| |
| Authors: | CHENG Ming-bao SUN Shi-jie |
| |
| Institution: | Department of Mathemat ics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China |
| |
| Abstract: | The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this
paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered. In the
first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, b
j
∊ 0, α], where 0 < α ⩽ 1 and b
j
denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is
known in advance, that is,
. For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same
time, the worst-case ratio of the list (LS) algorithm is investigated and it is proved that all the ratios are tight.
|
| |
| Keywords: | scheduling semi-online linear deteriorating processing time worst-case ratio |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《上海大学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《上海大学学报(英文版)》下载免费的PDF全文 |
|
