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

任务序号 1 \|, b3 `+ Q g+ ?; J0 O* A	1 & q# a7 h# \|" c& u9 }) r2 j- P	2 ! {7 z- x2 `& d$ c	3 + w6 P$ P1 t, T% {: z9 M6 x	4 ; s5 Y2 l7 G& d4 h5 m% l* v, E	5 5 U0 w8 W6 C% E8 T9 I. }1 c	6 9 [ ?' j" r* N& [4 }	7 ' `+ k" [# `! @; L4 ^8 F }	8 ! K: L, \|/ E# x	9 $ k, ?/ T8 K; Y" p7 y# ?	10 L# ~% S; e4 l6 P7 }6 p	11 3 }7 l8 O! P: `& M* m {' m: d
到达时刻 h$ o, d" D5 ` Z Q	0 . _# T% L* X/ V5 w" L% G	1 1 J& Z# ]5 Z3 ^/ I' b	1 5 \|; p @3 A* U7 G	2 . l' E' r' O+ ]: \|( ]	4 3 H9 ?8 {) a% c1 ]% H& {	5 ) }' I B9 j# \|# u9 K7 U	8 6 ]+ E/ t, l2 w" `8 {	7 ( \/ n9 m/ R: w! q4 X& F1 p	7 9 O+ D7 M( Q$ r- O! J) l	8 0 P* l1 R& P5 y F) p( x	5 / T3 n% l7 a( v3 W9 I/ Q
截止时刻 % a% K" ~! O$ a. r	2 7 k! C6 Y6 R( p4 J	2 / k2 y7 X* U4 M! y1 M1 W9 G. H	3 ( I* p5 i% D9 j* \|4 ]1 c, X	5 . ^1 M3 G% E U+ G5 Z' E	8 # D6 u% \( w; N" N0 m* \|8 I	7 + }2 r& y/ t, b6 }/ L0 O3 V- d	9 + S6 M" s8 j, v4 }4 R" B: H0 f	8 D! [/ \0 \7 E# p9 ~$ a& B	9 7 Y. L5 v* a: [& e/ G. g6 F0 E0 {	10 " o, i% Q8 m& Y	10 2 s+ Y; H. u4 f6 F, B/ ]2 k
所需运算单位数（百万） 1 E2 }) h0 g, i& ?1 G1 X	3 8 p! M' a8 D" L; G7 Q	6 " G. l0 @# {# G' S	9 ' p) v! o5 c' j( y	6 & D# ~! j! R# \" I9 D: E# F7 w	12 2 u+ F; U0 U. O: I) F6 A8 b' C7 g	6 % G( K9 h" o/ F	3 , z( _. Z) X5 i" g/ h	9 - u i7 ?" N$ V	6 $ ~( O3 p+ J5 u; z9 @1 c& r- d# k	3 ! l B0 Y! r1 q& ~1 i* t) W2 t	3 9 d2 y% o9 D; J1 q5 S) y7 Q