第!"卷 第"期 运 筹 与 管 理 #$%&!"，’$&"
())*年+月 ,-./012,’3/. 9:;&())*
收稿日期：())"<)+<!=
基金项目：辽宁省教委科研基金资助项目（()(+((>)）
作者简介：赵琨（!?=@<），女，辽宁本溪人，沈阳师范大学硕士研究生，主要从事排序研究。
资源有限的加权总完工时间单机排序问题
唐恒永， 赵 琨
（沈阳师范大学 数学与系统科学学院，辽宁 沈阳!!))"*）
摘 要：本文讨论资源有限的加权总工时间单机排序问题，对现在仍为,-.’问题!!!"A#"B$"%"，"%"#&’!
"(")"给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况#"A#，("A
(，$"A$；#"A#，("A(，&%"A&%；$"A$，("A(，&%"A&%的最优算法。
关键词：运筹学；排序；最优算法；资源约束；加工时间
中图分类号：,((" 文章标识码：0 文章编号：!))=<"((!（())*）)"<))*@<)*
!"#$%&’()*"#&!)*&+,%"#$-./0%&12"3*’"#"1"4"#$5&"$*3&+
6/17%&3"/#8"1&92"3*:&9/,.)&6/#93.("#&+
10’85C;D<E$;D，F50,G:;
（)*++,-,*./$01,2$0345$678950,25843,64,，81,69$6-:*;2$+’63<,;5309，81,69$6-!!))"*，)136$）
;093.()3：2;HIJKLMLCNOCPJKQ:KKHICKJ;D%CRMQIJ;CKQICP:%J;DLN$S%CROJHIRJ;JRJTJ;DOCJDIHCPQ$RL%C<
HJ$;HJRCKOJHINCK$:NQCQ$;KHNMJ;CP&0;JRL$NHM;HLN$LCNHE$;$LHJRM%NCK$:NQCM%%$QMHJ$;J;$LHJRM%K$%:HJ$;
$U!!!"A#"B$"%"，"%"#&’!"(")"JKDJVC;&WJHIHICLN$LCNHEHINCC$LHJRM%M%D$NHIRKU$N#"A#，("
A(，$"A$；#"A#，("A(，&%"A&%；$"A$，("A(，&%"A&%MNCDJVC;NCKLCQHJVC%E&
<&=2/.+9：$LCNMHJ$;KNCKCMNQI；KQICP:%J;D；$LHJRM%M%D$NJHIR；NCK$:NQCQ$;KHNMJ;H；LN$QCKKJ;DHJRC
) 引言
在连续资源约束排序问题中，有这样一类问题：资源是不可再生的，工件的加工时间依赖于它分配到
的资源，即工件的加工时间是它所得到的资源量的函数，在这里只研究单处理机，工件加工不可中断，工件
的加工时间是一种资源的连续函数的情况；已有的研究都是在工件的加工时间是其得到资源量的线性函
数下作出的。这类问题的资源约束可以描述为：!"A#"B$"%"，)#%"#&%"（"A!，(，⋯6），其中#"是工件
="的正常加工时间（#"$)），$"是工件="的单位资源分配量的系数（$"$)），%"是待定的对工件="的资源
分配量，!"是工件="的实际加工时间，&%"是工件="的资源分配量的上限，("是工件="的权因子，)"是工
件="的完工时间，&’ 表示可使用的资源总量，目标函数是"(")"。利用三元组件!!"!#记号，我们可
用!!!"A#"B$"%"，"%"#&’!"(")"表示这种资源约束排序问题。给定工件集!A｛=!，=(，⋯=6｝，用
>A｛>!，>(，⋯>6｝表示确定工件可行排序的工件下标的一个排列。"是所有这些排列的集合，满足资源
约束的资源分配向量记为’A｛%!，%(，⋯%6｝。我们用（>%，’%）表示问题的最优解，’%为最优资源分
配。
万方数据
这个问题首先由!"#$%&$’［(］开始研究，但是没有解决该问题，因此至今仍是)*+%问题。但如果给定
一个可行排列!!!，!"#$%&$’给出了分配资源的最优算法［(］，其算法复杂性为"（#,)-#），但这个算法要
在#！个下标排列中找出最优的下标排列!"，求解的时间较长，后来又有人构造了一个十分有效的下降
算法［.］，并对满足资源优先关系的特殊情况给出了最优算法。下面我们将给出一个重要的性质，利用性
质可以得到三种特殊情况的最优算法。
( 性质
!"#$%&$’给出了任意可行排列资源分配的最优算法，但在最优解中资源分配是否存在一定的规律可
循呢？下面我们给出了一个有关最优解中资源分配的命题。
命题 如果问题(#$%/&%0’%(%，$(%%)*#$+%,%存在最优解，则最优的资源分配是(%/1或
(%/)(%，最多存在一个(%介于1与)(%之间（%/(，.，⋯，#）。
证明 假设存在最优解（!"，*"），则在最优排列!"中，有
$
#
%-(
+!"（%）,!"（%）/$
#
.-(
+!"（.）$
.
%-(
&!"（%）0［’!"（(）(!"（(）$
#
.-(
+!"（.）
2’!"（.）(!"（.）$
#
.-.
+!"（.）2⋯2’!"（#）(!"（#）+!"（#）］
令/!"（.）/’!"（.）$
#
%-.
+!"（%），按/!"（.）非增排列从而得到资源分配的先后次序!（工件在!"中加工顺序
不变）0!（%）表示第%个分配到资源的工件，/!（%）&/!（%2(）（%/(，.，⋯，#0(），则
$
#
%-(
+!"（%）,!"（%）/$
#
.-(
+!"（.）$
.
%-(
&!"（%）0［/!（(）(!（(）2/!（.）(!（.）2⋯2/!（#）(!（#）］
因为$
#
.-(
+!"（.）$
.
%-(
&!"（%）为定值，要使$
#
%-.
+!"（%）,!"（%）达到最小，就要使1//!（(）(!（(）2/!（.）(!（.）2⋯
2/!（#）(!（#）达到最大。又因为/!（(）&/!（.）&⋯&/!（#），所以在最优的资源分配就要按!中的先后顺序
分别满足各工件的资源分配量上限直到资源用完。
假设存在两个工件的资源分配量既不是零，也不是它们资源的上限，那么它们在!中一定排在资分
配量达到上限的工件的后面，同时它们在!中也要排在资源分配量是零的工件的前面（资源在分配给这
两个工件之后已经用完，在!中排在其后的工件没有得到资源）。
设0!（(）⋯0!（.20(）达到各自的资源分配量的上限)(!（%）（%/(，.，⋯，.
20(），令这两个工件分别为0!（.2），
0!（02），0!（.2）在!中位于0!（%2）前，所以/!（.2）&/!（%2）。0!（.2）的资源分配量为("!（.2）’)(!（.2），0!（%2）的资源分配量为
("!（%2）’)(!（%2），则("!（.2）2("!（%2）/)*0$
.23(
.-(
)(!（.），此时1的具体形式为：
1(//!（(）)(!（(）2/!（.）)(!（.）2⋯2/!（.20(）)(!（.20(）2/!（.2）("!（.2）2/!（%2）("!（%2）
（(）当("!（.2）2("!（%2）&)(!（.2），则满足只有一个工件的资源分配量为介于零与它的资源分配量上限之间
的1的具体形式为：
1.//!（(）)(!（(）2/!（.）)(!（.）2⋯2/!（.20(）)(!（.20(）2/!（.2）)(!（.2）2/!（%2）（("!（.2）2("!（%2）0)(!（.2））
1(01.//!（.2）（("!（.2）0)(!（.2））2/!（%2）（)(!（.2）0("!（.2））/（)(!（.2）0("!（.2））（/!（%2）0/!（.2））
因为)(!（.2）0("!（.2）(1，/!（%2）0/!（.2）%1，所以1(%1.。
（.）当("!（.2）2("!（%2）’)(!（.2），则满足只有一个工件的资源分配量为介于零与它的资源分配量上限之间
的1的具体形式为：
1.//!（(）)(!（(）2/!（.）)(!（.）2⋯2/!（.20(）)(!（.20(）2/!（.2）（("!（.2）2("!（%2））
1(01.//!（.2）（("!（.2）0("!（.2）0("!（%2））2/!（%2）("!（%2）/("!（%2）（/!（%2）0/!（.2））
因为("!（%2）(1，/!（%2）0/!（.2）%1，所以1(%1.。
所以在最优解的最优资源分配中或是资源分配量的上限或是零最多存在一个工件的资源分配量介于
34第5期 赵琨，等：资源有限的加权总完工时间单机排序问题
万方数据
零与它的资源分配量上限之间。
! 特殊情况的最优算法
由于问题"!!"##"$$"%"，"%"#&’!"(")"是%&’(问题，很难构造出多项式算法，所以我们把
问题特殊化，研究其特殊情况的最优算法。上面我们已经证明了最优解中资源分配的命题，我们下面利用
该命题得出特殊情况的最优算法。当#"##，("#(，$"#$时，该问题具体形式为
"!!"##$$%"，"%"#&’!"
*
+,"
()" （"）
算法! 对于问题（"），按照&%"非增排列可以得到最优排列，按照最优排列中的顺序依次满足工件的
资源分配量上限直到资源用完即可得到最优资源分配。
定理! 对于问题（"），算法"得到最优解。
证明 设任意给定排序为!，则
"
*
","
()","
*
","
(!（"）"
"
+,"
（#!（+）-$%!（+））
,"
*
","
(!（"）"
"
+,"
#!（+）-"
*
","
(!（"）"
"
+,"
$%!（+）
,"
*
","
(!（"）"#-$"
*
","
(!（"）"
"
+,"
%!（+）
,#"
*
","
"(!（"）-$"
*
","
%!（"）"
*
+,"
(!（+）
,#"
*
","
"(-$"
*
","
%!（"）"
*
+,"
(!（+）
,#(*（*."）／!-$("
*
","
（*-"."）%!（"）
由于#(*（*)"）／!是定值，要极小化"*+,"()"，等同于极大化"
*
","
（*$")"）%!（"），所以要按
%!（"）非增排列。由已证命题，最优解的最优资源分配为%"#*或%"#&%"，最多有一个%"介于*与&%"（"#
"，!，⋯，*）之间。所以要按&%"非增排列可以得到最优排序"，而最优资源分配是（&%"（"），&%"（!），⋯，&%"（/），
%"（/)"）#&’$"/+,"&%"（+）#&%"（/)"），*，*，⋯，*）。
上面是当#"##，("#(，$"#$时，问题"!!"##"$$"%"，"%"#&’!"(")"特殊情况的最优算
法，下面我们把条件变换一下，来分析另外一种特殊情况。当#"##，("#(，&%"#&%时，该问题具体形式
为
"!!"##$$"%"，&%"#&%，"%"#&’!"
*
+,"
()" （!）
算法" 对于问题（!）按照$"非增排列可以得到最优排列，按照最优排列中的顺序依次满足工件的
资源分配量上限直到资源用完即可得到最优资源分配。
定理" 对于问题（!），算法!得到最优解。
证明 设任意给定排序为!，则
"
*
","
()","
*
","
(!（"）"
"
+,"
（#!（+）-$!（+）%!（+））
,"
*
","
(!（"）"
"
+,"
#!（+）-"
*
","
(!（"）"
"
+,"
$!（+）%!（+）
,"
*
","
(!（"）"#-"
*
","
(!（"）"
"
+,"
$!（+）%!（+）
,#"
*
","
"(!（"）-"
*
","
$!（"）%!（"）"
*
+,"
(!（+）
*+ 运 筹 与 管 理 !**,年第"-卷
万方数据
!"!
#
$!!
$%&!
#
$!!
’!（$）(!（$）!
#
)!$
%!（)）
!"%#（#*!）／"&%!
#
$!!
（#&$*!）’!（$）(!（$）
"%#（##!）／"是定值，要极小化!
#
)!!
%+$，等同于极大化!
#
$!!
（#$$#!）’!（$）(!（$），所以要按’!（$）
(!（$）非增排列。由已证命题，最优解的最优资源分配为($%&或($%,($，最多有一个($介于&与,($（$%
!，"，⋯，#）之间。由于,($%,(，所以按’!（$）非增就可以得到最优排序，最优资源分配为（,(，,(，⋯，,("# $
-
，（,.$
-,(）%,(，&，⋯，&）。
上面当"$%"，%$%%，,($%,(时，问题!&/$%"$$’$($，!($%,.&!%$+$特殊情况的最优算法，
下面我们再把条件变换一下，来分析另外一种特殊情况。当’$%’，%$%%，,($%,(时，该问题具体形式为
!&/$%"$$’($，,($%,(，!($%,.&!
#
)!!
%+$ （’）
算法! 对于问题（’），按照"$非减排列可以得到最优排列，按照最优排列中的顺序依次满足工件的
资源分配量上限直到资源用完即可得到最优资源分配。
定理! 对于问题（’），算法’得到最优解。
证明 设任意给定排列为!，则
!
#
$!!
%+$!!
#
$!!
%!（$）!
$
)!!
（"!（)）&’!（)）(!（)））
!%!
#
$!!
!
$
)!!
"!（)）&%’!
#
$!!
!
$
)!!
(!（)）
!%!
#
$!!
（#&$*!）"!（$）&%’!
#
$!!
（#&$*!）(!（)）
令0%’%!
#
$!!
（#$$#!）(!（)），极小化!
#
$!!
%+$，等同于极大化0。则0%’%［#(!（!）#（#$!）(!（"）
#⋯#(!（#）］所以最优资源分配要满足（(!（!））’(!（"）’⋯’(!（#）。由已证命题，最优解的最优资源分配
($%&或($%,($，最多有一个($介于&与,($（$%!，"，⋯，#）之间。由于,($%,(，所以1!（!）首先达到,(，
1!（"）其次达到,(，⋯，直到可用资源,. 用完。所以最优的资源分配为（,(，,(，⋯，,("# $
-
，,.$-,(%,(，&，⋯，&）。
0%’%!
#
$!!
（#$$#!）(!（)）%’%［#,(#（#$!）,(#⋯#（#$-#!）,(#（#$-）（,.$-,(）］为定值。极小
化!
#
$!!
%+$等同于极小化%!
#
$!!
（#$$#!）"!（$），所以应按"!（$）非减顺序排列可以得到最优排序。
参考文献：
［!］()*+),-./+*0123)45+*262782*4+*09+:51+*2);3<=216<>?<@668@?24::<A;242=2*424<*6:;)+*:6［(］.-;45+983-8:.+B2123，!CDD，’’："&’E
"!&.
［"］赵玉芳，赵传立，唐恒永.一类资源约束排序问题!&/$%"$$’$($，!($%,.&!%$+$［(］.沈阳师范学院学报（自然学科版），!CCC，
（!）：F$!".
!G第’期 赵琨，等：资源有限的加权总完工时间单机排序问题
万方数据
