| 无容量限制的批处理机时间表问题 |
| |
| 引用本文： | 刘朝晖,俞文(鱼此). 无容量限制的批处理机时间表问题[J]. 华东理工大学学报(自然科学版), 2001, 27(4): 431-433 |
| |
| 作者姓名： | 刘朝晖 俞文(鱼此) |
| |
| 作者单位： | 华东理工大学数学系;华东理工大学数学系 |
| |
| 基金项目： | 国家自然科学基金资助项目 (1973 10 0 1) |
| |
| 摘 要： | 研究无容量限制的批处理机时间表问题,在工件有到达时间和工期约束下,证明了当工件的到达时间和工期,或到达时间和加工时间一致单调时,该问题是多项式时间可解的;当加工时间和工期一致单调时,该问题是NP困难的。
|
| 关 键 词： | 排序 批处理机 多项式时间算法 NP困难性 |
| 文章编号： | 1006-3080(2001)04-0431-03 |
| 修稿时间： | 2000-08-19 |
Scheduling a Batch Processor with Unbounded Capacity |
| |
| LIU Zhao hui,YU Wen ci. Scheduling a Batch Processor with Unbounded Capacity[J]. Journal of East China University of Science and Technology, 2001, 27(4): 431-433 |
| |
| Authors: | LIU Zhao hui YU Wen ci |
| |
| Affiliation: | LIU Zhao hui,YU Wen ci * |
| |
| Abstract: | The problem of scheduling jobs with release times and due dates on a batch processor with unbounded capacity is considered.Polynomial time algorithms are provided for the case with agreeable release times and due dates and the case with agreeable release times and processing times.NP hardness is established for the case with agreeable processing times and due dates. |
| |
| Keywords: | scheduling batch processor polynomial time algorithm NP hardness |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
