欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
Baker和Nuttle提出了下述单可变资源排序问题：扎个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小，而资源的可利用率是随着时间而变化的．当最小化的目标函数是工件的加权完工时间和时，Baker和Nuttle猜测该问题是NP-困难的．最近，Yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的，但是问题的精确复杂性仍然是悬而未决的．本文我们证明了该问题是强NP-困难的．
英文摘要：
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 open. We show in this paper that this problem is strongly NP-hard.
同期刊论文项目
同项目期刊论文
Strong NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted
Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespa
Online scheduling on batching machines to minimise the total weighted completion time of jobs with p
SOME IMPROVED ALGORITHMS ON THE SINGLE MACHINE HIERARCHICAL SCHEDULING WITH TOTAL TARDINESS AS THE P
An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delive
期刊信息
位置：