查看: 4973|回复: 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 万个单位的运算，到达时刻与截止时刻单位均为秒。

任务序号 9 Z+ V2 V% N- B& Y. b& I& C) ?	1 Z! w6 A2 x% G& j% k	2 4 U+ N$ ^0 K0 _% n" S	3 : l$ @9 C# L8 Z1 f$ j- q, z+ g# ~	4 0 b4 j; N" \|( F8 Z/ [# ?/ A6 d	5 & c& m! W% L" a8 _3 g9 y# H	6 + g J1 D+ e" t	7 / Z4 ^/ B8 t- u% A+ x$ I	8 + u+ t9 ^& O% `1 r) y' m" g; ]	9 9 i3 J$ ? \% a3 s	10 ], @# [& q4 y5 R! X3 s- Y	11 + i+ n; `+ `" w3 a3 D% M* p
到达时刻 " \& ^5 @ ]9 q8 h0 S3 @	0 # N x$ `' f. x7 F* Z* g	1 + `3 }8 M9 T0 K; c$ h/ \|	1 1 \7 }" V, i, Q' @( L4 L- {" w" t	2 1 m- {5 k, a" g P4 i7 @( C	4 & _+ ^/ y. o! ^( E( i9 @	5 , y. P" p/ ^5 ?6 n+ ?8 k" }	8 3 @! \|1 L7 `4 t) E, q/ h9 ?	7 ; S. f0 }6 ^5 Z- G	7 * M# Y7 ?$ R" c4 K	8 ( c8 M" J+ x# }	5 ( Z2 x6 M7 R5 _, S) v5 j% R7 ?
截止时刻 # h2 F0 B! D( ? y	2 6 I' E9 u: n. h' Q: Y	2 $ `/ A3 h3 n: U5 G8 M2 j S7 F( C	3 : S' A* B" h9 e) T2 e) g& L	5 " U2 l9 t* v" I: ^% y+ b7 Q	8 3 y" w8 V# _: I& y' I	7 # R N# S$ w0 d5 O, w% _1 Y' U	9 ' w( W3 y9 M# i	8 $ U, h7 r; {! D" V l	9 ! v2 C5 t0 i8 h3 t* g4 p	10 % C0 x* y3 O! m+ P+ o, i	10 2 L0 V% E7 V. m2 b
所需运算单位数（百万） ; ]+ `' v6 ]! a% \! u# N. v9 v	3 ( r4 C* ^8 c$ u& {- y$ Y$ S	6 $ o; h( L7 e2 V J" ~ V1 X	9 , R$ w" I+ b) Y2 X8 q, W1 h	6 6 G9 G9 o. K1 i9 `	12 . B+ Y, J6 }* c	6 4 y6 g) D* {$ i* t7 T! R( U' E6 r: N	3 3 I. K& v* [% w	9 ! x8 b# A/ e0 m" _	6 ) S; ]0 a3 R9 X	3 E8 i* c+ y+ C# B* d6 ~	3 ! y% j7 V& \|: l) `