| 自由作业稠密时间表的性能比上界 |
| |
| 引用本文： | 陈秀宏,俞文.自由作业稠密时间表的性能比上界[J].华东理工大学学报(自然科学版),2000,26(6):670-673,677. |
| |
| 作者姓名： | 陈秀宏 俞文 |
| |
| 作者单位： | 华东理工大学应用数学研究所,上海 200237 |
| |
| 基金项目： | 国家自然科学基金，19731001， |
| |
| 摘 要： | 对于自由作业问题，如果从初始时刻开始，逐步在每个机器安排任一可以加工的工件，避免不必要的空闲，所得的安排称为稠密时间表。其加工总长与最优值之比具有上界２－１／ｍ（ｍ为机器数），是一个尚未证明的猜想。本文引入了最后工件组及相关机器集的概念，证明了ｍ＝５时该猜想是成立的。
|
| 关 键 词： | 自由作业 加工总长 稠密时间表 性能比 最优值 |
| 文章编号： | 1006-3080(2000)06-0670-04 |
Upper-bound of Performance Ratio of Dense Schedules for Open-shop |
| |
| CHEN Xiu hong,YU Wen ci.Upper-bound of Performance Ratio of Dense Schedules for Open-shop[J].Journal of East China University of Science and Technology,2000,26(6):670-673,677. |
| |
| Authors: | CHEN Xiu hong YU Wen ci |
| |
| Institution: | CHEN Xiu hong,YU Wen ci * |
| |
| Abstract: | For an open shop problem, if the principle of avoiding unnecessary idleness is applied to arrange available jobs for the schedule construction, a dense schedule is obtained. It is conjectured that the makespan of any dense schedule is at most 2-1/ m times the optimal makespan, where m is the number of machines. In this paper, we introduce the concepts of last job group and the related machines, and prove that the conjecture holds for m =5. |
| |
| Keywords: | open shop makespan dense schedule performance ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
