| Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on m Identical Machines |
| |
| 作者姓名： | 罗润梓 孙世杰 |
| |
| 作者单位： | DepartmentofMathematics,CollegeofSciences,ShanghaiUniversity,Shanghai200444,P.R.China |
| |
| 摘 要： | In this paper, a semi on-line version on m identical machines M1 , M2, …, Mm ( m ≥ 3 ) was considered, where the processing time of the largest job is known in advance. Our goal is to maximize the minimum machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m - 1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2 m - 1 )Pmax where pmax is the largest job‘s processing time, then the worstcase ratio is 2 - 1/m.
|
| 关 键 词： | 机械控制系统 机械完成时间 时序安排 在线控制系统 计算方法 |
| 收稿时间： | 14 October 2003 |
Semi on-line scheduling problem for maximizing the minimum machine completion time on <Emphasis Type="Italic">m</Emphasis> identical machines |
| |
| Luo?Run-zi,Sun?Shi-jie.Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on m Identical Machines[J].Journal of Shanghai University(English Edition),2005,9(2):99-102. |
| |
| Authors: | Luo Run-zi Sun Shi-jie |
| |
| Institution: | (1) Department of Mathematics, College of Sciences, Shanghai University, 200444 Shanghai, P.R. China |
| |
| Abstract: | In this paper, a semi cm-line version on m identical machines M
1, M
2, …, M
m (m≥3) was considered, where the processing time of the largest job is known in advance. Our goal is to maximize the minimum
machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m−1 which is the best possible
value. It is concluded that if the total processing time of jobs is also known to be greater than (2m−1)p
max where p
max is the largest job’s processing time, then the worst-case ratio is 2−1/m. |
| |
| Keywords: | scheduling semi on-line worst-case ratio |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
|
