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

任务序号 $ K0 q( e' u+ H% K% ~; H	1 2 c7 \% S9 l9 y# l	2 ; d% _% k# H. a/ s) Q0 x" c	3 " b4 t& k6 _5 k) K! _0 w. v' P	4 1 Q4 B4 q P1 }: c) c/ X, I# E	5 5 O8 {% G- V9 H: v7 C* H	6 . `& \| T( P2 k; Q+ f% R	7 . d$ g0 \: _/ L3 k	8 7 m2 x& w+ H/ m3 \|: p4 A9 n	9 5 I1 P G9 P: x4 s, a	10 + h! v! \1 l5 r2 M+ J' b% g& ?	11 , Q$ L. E g3 Z. o
到达时刻 6 d0 C4 m. k. _, s	0 " ?' X4 b4 Q) K4 {	1 . v, @, B- P- c	1 : d0 `8 `+ \|# e0 G0 ~	2 + ]+ K* ?5 @. {3 e: \$ l& ^1 z% @	4 $ Z4 z: X& W2 v9 t' @" D6 a	5 8 [. s+ L- I, x3 r) C6 `4 y	8 6 i E K% d6 [- f2 p" J# }	7 , ^, Z$ K- `' ]2 X" A" [	7 ; s8 }. S/ m8 R# x8 F	8 # s; g' b j$ ~' n	5 " o4 x1 C& `/ _$ Y
截止时刻 6 Z/ R0 {- A" M+ M Q( z5 F	2 - ^# I1 I; ?9 \|- f	2 $ O: Z4 f; r) y. w% V0 h	3 . p& x3 D; j# i9 o) I f	5 ! q- J K% X1 t0 {9 i. T6 Y	8 8 _1 K- }$ n. A" g; R, T	7 ) L+ F+ ?) `5 b3 C' o: [	9 , w# t& y5 ?: I' m# ~9 G1 ]9 i	8 $ M" s1 D6 ^; y1 ?) J	9 9 \|. R ?# l+ D	10 4 ]$ I5 b3 Q% x# B/ ?	10 * ~( U. n8 x4 ?* }3 K/ x( T
所需运算单位数（百万） 3 E' E; f: f8 u3 I _. A. B: t	3 $ e4 l( f; h8 h1 b	6 0 h7 v6 V4 g' ^# D8 Q* J5 d# A% R	9 - i( s' N1 Z9 R \( I. \|% v	6 ! ]( V7 F& j# v4 J9 q& }$ y	12 4 u5 {: g) q- W	6 % B, j$ a/ _0 Y% y e8 y/ I" g	3 4 y8 F+ v' y" E! j1 l/ i- J	9 8 x4 X# }' b6 Y	6 - S4 o- G; ?, E2 s6 g( o	3 3 J; v: M$ O# \1 `	3 : F% A. v! j2 K0 n" a3 J