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

任务序号 * }) K7 `! W3 v	1 8 t4 O# o" b4 x+ E+ ~$ {, B# P	2 + `0 [+ R" N# W4 A# z	3 ( R$ G1 q6 r0 G0 Q	4 $ b6 c% A5 v8 d7 Y+ F. l* O5 e	5 - V& l" {# D- s/ t1 }5 a+ F	6 ! o0 v9 n% @- Q0 J	7 % \|" y* W) A% ^" W9 v" b$ a0 M( _	8 ) q- q0 s: V3 v, C) {. w6 R	9 $ y; ^9 {6 E7 D& ^- Y; r	10 $ D( \1 k6 S/ X- I& p4 N2 U+ d7 \	11 + y7 M+ B6 f0 i
到达时刻 6 Y0 J) @0 X& p$ w) G7 h: B! K	0 P* o1 a6 c5 E n	1 , n2 G' l O1 U	1 . ?" H b) L% F# z1 V6 [; ^	2 : h, G6 B) u7 k% j	4 4 ]9 Z& l2 }" a2 Z, B2 R7 H, }	5 / l ~4 A9 V# W: g1 \- V: \|# G	8 $ ]. [2 g& M( l% }1 D* W+ Y	7 6 O1 S8 k' i) f! p/ y	7 D5 c$ i1 z2 I; Q) V5 {" \|5 b- L	8 / f, q( p5 ^) T0 G	5 8 B- \|7 }: G' I# q! F
截止时刻 7 s$ e1 E0 _/ _; H6 C	2 & p# x% B3 w% _	2 / I/ W; ]/ \' G7 o$ k	3 9 B" ]6 r/ r, k7 Q	5 # O; O* P8 `, @. N4 A	8 ; C2 D! h: x6 O+ p# l7 z	7 + `! q# h) \|8 I9 ]	9 2 H( K. w' O# h# I8 y6 R. h8 f6 a	8 ) W# } z% l( @: I- W+ s$ _	9 {3 r. b# M+ ^# f" o! Q	10 4 b7 {0 c0 s9 X( B! m2 Q	10 g. v* s7 y( d
所需运算单位数（百万） : D" O! @; a5 \|" g/ g	3 * P o: o7 [3 h5 R* P S	6 % s9 Z' k0 M2 R3 X	9 & ]# ~7 V7 ?- T% M1 `	6 ; d: n( b- B$ v	12 8 Z9 {( _* {. G& Q3 O. A	6 9 v8 p, Y6 U8 k	3 4 \ a, V/ e7 R, w	9 , q6 z6 }$ ~. I" m3 c	6 / T, Q- z' M% K6 H, d	3 0 Y" h1 l% R' p! _$ O/ m	3 ) k$ @) h/ I- Z0 E