| 带机器准备时间的同类机在线与半在线排序问题 |
| |
| 引用本文： | 丁际环,曲桂东,张伟,岳丽,张玉忠.带机器准备时间的同类机在线与半在线排序问题[J].曲阜师范大学学报,2003,29(3):1-5. |
| |
| 作者姓名： | 丁际环 曲桂东 张伟 岳丽 张玉忠 |
| |
| 作者单位： | [1]曲阜师范大学运筹与管理学院，山东省日照市276800 [2]威海职业学院信息工程系，山东省威海市264200 [3]青岛师范学院数学系，山东省青岛市266071 |
| |
| 基金项目： | 国家自然科学基金，教育部高校骨干教师项目，山东省中青年学术骨干项目 |
| |
| 摘 要： | 研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题，目标函数为极小化最大机器(工件)完工时间。对于在线情形，证明了LS算法的最坏情况为ρ=｛（1 √5）/2，m=2,1 √2m-2/2,m≥3，并且当m=2，LS算法是最好的近似算法；当m=2，3，…，6时界是紧的，特别地，当s1=s2=…=sm-1,sm≥l时，证明了LS算法的最坏情况界为ρ=｛（1 √5）/2，m=2,3-4/m 1,m≥3，而且界是紧的；对于已知加工时间递减的半在线排序问题，证明了LS算法的最坏情况界为2—2/(m 1)。
|
| 关 键 词： | 在线排序 半在线排序 机器准备时间 同类机 近似算法 最坏情况 LS算法 |
| 文章编号： | 1001-5337(2003)03-0001-05 |
| 修稿时间： | 2002年10月18 |
ON-LINE AND SEMI ON-LINE SCHEDULING ON UNIFORM MACHINES WITH NON-SIMULTANEOUS MACHINE AVAILABLE TIMES |
| |
| Abstract: | |
| |
| Keywords: | on-line scheduling approximation algorithm worst case performance ratio |
| 本文献已被 CNKI 维普 等数据库收录！ |
