| 单可变资源最小化加权完工时间和排序问题的强NP-困难性 |
| |
| 引用本文： | 原晋江,王勤.单可变资源最小化加权完工时间和排序问题的强NP-困难性[J].运筹学学报,2010,14(1):31-36. |
| |
| 作者姓名： | 原晋江 王勤 |
| |
| 作者单位： | 1. 郑州大学数学系,郑州,450052
2. 中国计量学院数学系,杭州,310018 |
| |
| 基金项目： | The first author was supported by NSFC，NSFC-RGC，SRFDP，the second author was supported by NSFC，浙江省自然科学基金 |
| |
| 摘 要： | Baker和Nuttle提出了下述单可变资源排序问题：$n$个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小，而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时，Baker和Nuttle猜测该问题是NP-困难的.最近，Yuan、Cheng 和 Ng 证明该问题在一般意义下是NP-困难的，但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的.
|
| 关 键 词： | 运筹学 排序 资源的可利用率 资源需求 加权完工时间和 强NP-困难性 |
Strong NP-hardness of the Single-variable-resource Scheduling Problem to Minimize the Total Weighted Completion Time |
| |
| Yuan Jinjiang,Wang Qin.Strong NP-hardness of the Single-variable-resource Scheduling Problem to Minimize the Total Weighted Completion Time[J].OR Transactions,2010,14(1):31-36. |
| |
| Authors: | Yuan Jinjiang Wang Qin |
| |
| Institution: | Yuan Jinjiang Wang Qin 1.Department of Mathematics,Zhengzhou University,Zhengzhou 450052,People\'s Republic of China. 2.Department of Mathematics,China Jiliang University,Hangzhou 310018,People\'s Republic of China. |
| |
| Abstract: | Baker and Nuttle studied the following single-variable-resource scheduling problem:sequencing n jobs for processing by a single resource to minimize a function of job completion times,when the availability of the resource varies over time.When the objective function to be minimized is the total weighted completion time,Baker and Nuttle conjectured that the problem is NP-hard.Recently,Yuan,Cheng and Ng showed that this problem is NP-hard in the binary sense,but the exact complexity of the problem is still op... |
| |
| Keywords: | Operations research Scheduling Resource availability Resource require-ment Total weighted completion time Strong NP-hardness |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
