运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2010年
1期
31-36
,共6页
运筹学%排序%资源的可利用率%资源需求%加权完工时间和%强NP-困难性
運籌學%排序%資源的可利用率%資源需求%加權完工時間和%彊NP-睏難性
운주학%배서%자원적가이용솔%자원수구%가권완공시간화%강NP-곤난성
Operations research%Scheduling%Resource availability%Resource require-ment%Total weighted completion time%Strong NP-hardness
Baker和Nuttle提出了下述单可变资源排序问题: n个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan,Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的.
Baker和Nuttle提齣瞭下述單可變資源排序問題: n箇工件利用某箇單資源進行加工使得工件的完工時間的某箇函數達到最小,而資源的可利用率是隨著時間而變化的.噹最小化的目標函數是工件的加權完工時間和時,Baker和Nuttle猜測該問題是NP-睏難的.最近,Yuan,Cheng和Ng證明該問題在一般意義下是NP-睏難的,但是問題的精確複雜性仍然是懸而未決的.本文我們證明瞭該問題是彊NP-睏難的.
Baker화Nuttle제출료하술단가변자원배서문제: n개공건이용모개단자원진행가공사득공건적완공시간적모개함수체도최소,이자원적가이용솔시수착시간이변화적.당최소화적목표함수시공건적가권완공시간화시,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.
