| 具有优先权的自由作业时间表问题研究 |
| |
| 引用本文： | 时凌.具有优先权的自由作业时间表问题研究[J].内蒙古师范大学学报(自然科学版),2003,32(4):374-377. |
| |
| 作者姓名： | 时凌 |
| |
| 作者单位： | 湖北民族学院数学系 湖北恩施445000 |
| |
| 基金项目： | 湖北省教育厅重点项目(2002x13) |
| |
| 摘 要： | 研究了具有优先权的自由作业时间表问题，在工件具有准备时间的条件下，给出一种新的启发式算法，其最坏性能比不超过2，猜想该算法的紧界是2—2／(m 1)，其中m是机器的台数，证明在3台机器的情况下，该算法的最坏性能比为3／2，且上界是紧的。
|
| 关 键 词： | 优先权 自由作业时间表问题 启发式算法 准备时间 最坏性能比 |
| 文章编号： | 1001-8735(2003)04-0374-04 |
| 修稿时间： | 2003年5月9日 |
A HEURISTIC ALGORITHM FOR OPEN-SHOP SCHEDULING PROBLEMS WITH JOB PRIORITIES |
| |
| SHI Ling.A HEURISTIC ALGORITHM FOR OPEN-SHOP SCHEDULING PROBLEMS WITH JOB PRIORITIES[J].Journal of Inner Mongolia Normal University(Natural Science Edition),2003,32(4):374-377. |
| |
| Authors: | SHI Ling |
| |
| Abstract: | This paper considers the open shop scheduling problems with job priorities and release times.For arbitrary number of machines,a simply algorithm can produce a schedule whose make span is at most 2 times of the optimal one in the worst-case in general.However,we conjecture the tight bound is 2-2/(m+1) (m is the number of machines).The worst-case ratio is proved to be 3/2 for m=3,and the bound is tight. |
| |
| Keywords: | heuristic algorithm open shop scheduling problem job priorities release time worst-case ratio |
| 本文献已被 CNKI 维普 等数据库收录！ |
