带机器准备时间的同类机在线与半在线排序问题 |
| |
引用本文: | 丁际环,曲桂东,张伟,岳丽,张玉忠. 带机器准备时间的同类机在线与半在线排序问题[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 维普 等数据库收录! |