查看: 4975|回复: 9

浙江大学第四届大学生数学建模比赛B题

字体大小: 正常放大

3 主题	4 听众	8 积分

升级 3.16%

该用户从未签到

电梯直达

1^#

发表于 2009-6-17 07:46 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

题6

建设节约型社会要求在社会生产、建设、流通、消费的各个领域，在经济和社会发展的各个方面，切实保护和合理利用各种资源，提高资源利用效率，以尽可能少的资源消耗获得最大的经济效益和社会效益。近年来，能源紧缺问题日益突出。尽管单台计算机功率不大，但总的数量增长十分迅速。据统计，1998 年在美国计算机消耗了13％的电力供应。CPU 节能的另一个动因来自笔记本电脑、智能手机等靠电池供电的电子设备上。为了延长电池使用时间，必须尽可能地减少能量消耗。

一般说来，单位时间CPU 能耗与CPU 在该时刻的工作率有关，工作率越大，能耗越高。而工作率又影响设备的性能，决定程序的反应时间和完成工作所需的时间。当然不同情况下，侧重有所不同。以下是两类常见的问题。

问题一：现有一批任务，每个任务有其到达时刻和截止时刻，任务必须在两者之间完成，但允许在多个不连续的时间区间内运行，CPU 在同一时刻也可执行多个任务。要求这些任务都可按时完成，并且耗用的能量最小。

问题二：假设任务只有到达时刻，没有截止时刻，完成这些任务所消耗的能

量有一个上限。要求在耗用能量不超过上限的条件下，使这些任务的流程时间之和尽可能小，这里某个任务的流程时间是指其完成时刻与到达时刻之差。

对以上两个问题，试作出合理的假设，建立模型，设计算法以给出CPU 如何处理一批任务的方案，并分析你的算法的性能。

下面给出一组简单数据用于问题一的测试，你的算法应能处理更复杂的情况。假设CPU 每秒最多可完成1000 万个单位的运算，到达时刻与截止时刻单位均为秒。

任务序号 + I# _. ~" l3 t" f, j	1 - Y3 P; O6 l/ c	2 - _5 j/ ?/ O; ?2 p3 ]	3 8 T- {4 Z3 p# w; j0 B( ~	4 ( f8 w0 u4 {1 a0 [6 }3 v	5 / s( Q: }7 L3 v) B' `/ ?	6 4 N: Z( L/ X& X. a' Z6 O2 r& H( W	7 4 w6 O* Z1 H# W/ }: z+ g( W6 c: X	8 1 Z: o- d" \|4 K6 u& o( @9 R	9 + f* n: W* F$ l+ ~5 H3 J1 }9 t	10 & \|0 Y! l! g `+ n7 b& G( g	11 - t$ f% _! t- {3 A) C2 E" [5 p
到达时刻 2 U w8 ^2 q- a' K	0 9 ~* ~ `8 r4 s% c/ Q* G! O	1 : N& N' W3 Q9 w0 J/ K# f) z	1 9 j( X) [" ?- c/ ?+ l3 h4 i' m	2 2 e; N: k# i! ^0 ]$ } I. y, P	4 - r1 h8 X: @* V) ?* a1 [	5 6 j& U/ f* J! I* y D: r8 z$ j3 }# @	8 7 \|; K, R" e4 U0 S	7 5 \|9 _" _( q" i$ F' ?2 ]& f) w	7 / A/ e, \ a- M$ r1 N! ^	8 2 `3 a, z8 v8 ^7 K4 B	5 : K! e/ s. A# @
截止时刻 7 @" ^# y# }, i4 v1 @; m0 D& M	2 5 L; ^7 r5 \2 E2 [4 M6 S8 L	2 ) F* k* f' R: V5 c# H& Y2 f	3 + G8 \0 c y1 p0 q6 \8 N	5 4 t" p1 \+ r+ l3 \|# b5 r) d	8 5 m" E4 o6 f$ x	7 0 p$ T+ J& I) \|' D1 ]) c7 M	9 / v* r" `1 R; w4 @' i	8 # K+ ?& D! p7 z- \	9 # ?: t) H( w6 N- N# e( k! ^- }( s	10 : C7 \|- t4 U( W7 e% ^	10 , Y9 g; c e0 Z, ~. [- \|7 ?
所需运算单位数（百万） 5 m7 M' g: L8 H" x6 t. s	3 ! h: B5 i' {* W4 m1 I	6 / s( P9 i$ p$ ?- x' X( h0 B	9 , J b. p% \+ \|8 u	6 , d. `2 A. y3 o* ~	12 - B$ L4 C7 [& R5 j; }: I' h	6 . v: C: D/ r: B) T8 D j9 e	3 $ u& w' J$ V5 g- v	9 * f* c% c4 Y+ \|	6 $ U+ ~0 o- X$ k6 I2 l0 Z( w	3 5 G6 a: d" m$ T; l6 \. g6 u	3 % m* U" v8 A) \|$ ^; V