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

任务序号 & O' L5 Y4 t5 q6 e	1 0 P! W" _. }3 R c5 J4 Q4 k	2 / f7 s) O+ Y$ ~- V, y$ Z' [$ a9 R	3 6 H8 Q+ J3 b8 Y+ f" g1 l	4 ! y! F$ J5 z; @% }; \/ p# ]8 \) \|	5 , j5 F2 `: h; D2 c	6 4 p1 [3 I6 n: L1 Q1 d2 ]	7 1 j$ B9 I, f) Z( ]) J# }	8 + w' {8 X) N, ]& _. g9 \|	9 " f2 F2 ` ?: D. K, P! M/ M	10 3 @2 t8 c& S4 e% Q7 V	11 + P0 q! G- P& H3 u8 Q s3 z! h
到达时刻 6 y0 }8 }. u' F; m	0 6 n2 S2 @% L2 F( F$ ?/ d	1 ' r5 S5 u% X' H5 }: [	1 & o# E/ U0 S% \. `	2 8 k$ B9 B- G6 O' j9 a7 v" R	4 - Y! Z% M4 T0 r6 P/ n	5 % U7 b' g& u+ g7 C- J6 Y; z: s	8 " N% k6 ?2 D4 h" v. s	7 0 q' Q* b7 f! u	7 3 A) E, a# t1 _( E6 O+ V. O$ O	8 " N% g1 h& H z: i! s	5 ' y' e# v _% n9 a: S7 d6 r! _6 [
截止时刻 4 j- ?4 c& L: v' g. x. a	2 5 o, S: h. D9 p! E6 x! @) c	2 6 r3 U! y4 N8 T	3 $ ^8 q# P7 ]" j, T \	5 9 X5 _9 O+ X7 l' N. z	8 9 c5 R1 w- P2 Q	7 . T/ {/ O, \|8 `9 F! } ^	9 0 K5 v( e+ P: j6 I F	8 4 P$ N$ m2 I% a- M& o	9 , m4 r% A1 V, w2 p	10 % z% L; a/ E& N$ L5 g* Q	10 - Z: v: L5 } O( Q3 }0 l- M
所需运算单位数（百万） : E( e$ A$ t( ^# k9 Q5 ?/ Q" I J E	3 7 `5 O# U' z/ N- N) f	6 ( q" E( X& o- v# f	9 ' Y1 c/ \: v; R	6 7 R+ u. ?; c8 ]: `- I	12 ' s; C0 f3 k3 T2 i& k* [, U I	6 ! C3 w1 @) J/ x* m* a4 C$ W	3 ( M4 N7 ^$ u7 L3 ~1 B	9 % w) _5 `: u- v# b3 G	6 ; `4 @% o `* \|( I1 W; d) \|	3 4 s- h: C8 o) L# \	3 + y+ ]! G8 p5 O2 ^ b