| 带单服务器的流水作业排序问题的复杂性 |
| |
| 引用本文： | 时凌,张琼,龙彩燕. 带单服务器的流水作业排序问题的复杂性[J]. 延边大学学报(自然科学版), 2022, 0(4): 332-335 |
| |
| 作者姓名： | 时凌 张琼 龙彩燕 |
| |
| 作者单位： | (广州工商学院通识教育学院,广东广州510850) |
| |
| 基金项目： | 国家自然科学基金(61763009)； |
| |
| 摘 要： | 研究了一个带单服务器且加工时间相等的两机流水作业排序问题，其目标函数是使总完工时间达到最小.研究表明，该流水作业排序问题是强NP-困难的.针对该流水作业排序问题构造了一种新的加工顺序，并证明该加工顺序的紧界为7/6.
|
| 关 键 词： | 流水作业排序问题 总完工时间 单服务器 最坏性能比 |
Complexity for flow - shop scheduling problems with a single server |
| |
| SHI Ling,ZHANG Qiong,LONG Caiyan. Complexity for flow - shop scheduling problems with a single server[J]. Journal of Yanbian University (Natural Science), 2022, 0(4): 332-335 |
| |
| Authors: | SHI Ling ZHANG Qiong LONG Caiyan |
| |
| Affiliation: | (Institute of General Education, Guangzhou College of Technology and Business, Guangzhou 510850, China) |
| |
| Abstract: | We consider the problem of two - machine flow - shop scheduling with a single server and equal processing times, the objective function is to minimize total completion time.We show that this problem is NP - hard in the strong sense and present a busy schedule for it with worst case ratio 7/6, and the bound is tight. |
| |
| Keywords: | flow - shop scheduling problem total completion time a single server worst case ratio |
|
| 点击此处可从《延边大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《延边大学学报(自然科学版)》下载免费的PDF全文 |
