数学建模期末考试题.docx
- 文档编号:2825874
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:21
- 大小:154.22KB
数学建模期末考试题.docx
《数学建模期末考试题.docx》由会员分享,可在线阅读,更多相关《数学建模期末考试题.docx(21页珍藏版)》请在冰点文库上搜索。
数学建模期末考试题
《数学建模》课程
期末作业
题目:
单台机器上的任务调度问题
专业名称:
金融信息工程
所在院系:
国际软件学院
论文时间:
2011年11月
学号:
Xxxxxx
姓名:
XXX
单台机器上的任务调度问题
在一台机器上将要处理一组任务。
任务的执行不具有抢先性,即一旦一个任务开始执行,就不允许被打断。
任务1—7的发布时刻分别是2,5,4,0,0,8,9,持续时间分别是5,6,8,4,2,4,2,规定完成时刻分别是10,21,15,10,5,15,22。
试构建模型求出如下目标的最优值,且对目标函数和约束条件作必要的说明。
1、完成所有任务总需时的最小值。
2、平均处理任务时间的最小值,处理任务时间是指任务发布时刻到任务实际完成时刻这段时间。
3、总超时时间的最小值。
一、问题描述
在一台机器上将要处理一组任务,任务的执行之间不具有抢先性,也就是任务一个一个的顺序执行,任务的发布时刻,持续时间,规定完成时间如下表所示:
任务
发布时间
持续时间
完成时间
1
2
5
10
2
5
6
21
3
4
8
15
4
0
4
10
5
0
2
5
6
8
4
15
7
9
2
22
要求构建三个数学模型,分别求出完成所有任务所需时最小值、平均处理任务时间的最小值和总超时时间的最小值。
二、问题分析
首先我们可以把题目中的数据进行处理,在不考虑任务重叠的情况下各个任务执行过程可直观的表示为下图所示:
问题一,每个任务都有自己的执行时间区间,也就是开始执行时间到实际完成时间这一段时间区间,在任务执行的过程中不能发生中断,也就可以简单的看成任意两个任务的执行时间区间不发生重叠,这样任务就可以一个一个的顺序执行。
而对于一个将要执行的任务,其必须在任务发布之后,才可以正式开始执行。
要求最小的完成时间就是相当于将这些线段在一定的条件下在一条直线上安排时期总长度最小。
问题二,题目中已经给出平均处理任务是指任务发布时间到任务完成时刻这段时间,我们只需将问题一中模型的目标函数进行修改,求出总的处理任务时间的最小值,然后除以任务个数。
问题三,超时时间是指:
如果某个任务没有超时,则超时时间为0;如果某个任务超时,则超时时间为规定完成时刻到任务实际完成时刻这段时间。
总超时时间为超时时间之和。
要使得这个值最小必须要使的所谓的冲突时间最小既是要
最小。
具体有如下定理支持:
三、模型假设
1、机器运行期间稳定好,没有内在和外来的故障发生。
2、当任务还没有发布时,机器可以等待任务。
3、机器可连续执行任务且任务切换所需时间忽略不计。
4、任务可超时执行且不影响机器继续执行。
四、符号说明
——第
个任务;
——第
个任务的发布时刻;
——第
个任务的持续时间;
——第
个任务的规定完成时间;
——第
个任务的实际完成时间;
——第
个任务的实际开始执行时间;
——第
个任务的完成超时时间;
;
——完成任务总需时;
——平均处理任务时间;
——总超时时间;
五、模型的建立与求解
问题一的模型建立与求解
由于任务执行过程中不发生中断,也就是一个任务执行完之后下一个任务才可以开始执行,所以两个任务的执行时间区间不能发生重叠。
每个任务的执行时间区间为[
],由区间不重叠的知识可以知道两执行时间区间不重叠的充分必要条件是:
同时任务开始执行时必须已经发布,由题目中所给的条件爱你我们可以建立模型一如下:
约束条件说明:
(1)开始时间必须在发布时间之后;
(2)任务区间不得有重叠,既在某一时刻只能执行一个任务;
(3)结束时间为任务开始时间与持续时间之和;
运用lingo程序对模型进行求解,得到总需时最小值为31小时,此时的各任务的开始时间和实际完成时间以及执行顺序见下表:
任务
1
2
3
4
5
6
7
开始执行时间
14
25
6
2
0
21
19
实际完成时间
19
31
14
6
2
25
21
顺序
4
7
3
2
1
6
5
任务的执行顺序为:
5-4-3-1-7-6-2。
这个顺序并不是唯一的总时间最小为31。
问题二的模型建立与求解
处理任务时间是指任务发布时刻到实际完成时刻这段时间,我们可以通过求出所有任务的总处理任务时间最小值除以任务个数,即可得到平均处理任务时间最小值。
这里我们只需要对模型一中的目标函数进行改动就可以得到模型二,如下:
约束条件说明:
(1)开始时间必须在发布时间之后;
(2)任务区间不得有重叠,既在某一时刻只能执行一个任务;
(3)结束时间为任务开始时间与持续时间之和;
运用lingo程序对模型进行求解,得到平均处理任务时间最小值为小时,此时的各任务的开始时间和实际完成时间以及执行顺序见下表:
任务
1
2
3
4
5
6
7
开始执行时间
20
25
6
2
0
16
14
实际完成时间
25
31
14
6
2
20
16
处理任务时间
22
26
10
6
2
12
7
顺序
6
7
3
2
1
5
4
任务的执行顺序为:
5-4-3-7-6-1-2。
平均处理任务时间最小值为。
问题三的模型建立与求解
因为超时时间有两种情况,一种实际完成时间比规定完成时间小,一种实际完成时间比规定完成时间大。
我们可以对得到超时时间的表达式:
通过题目中所给的约束条件,对之前的模型进行改进得到模型三,要加强目标的要求使得冲突的时间最小这样就使得超时最小.模型如下:
约束条件说明:
(1)开始时间必须在发布时间之后;
(2)任务区间不得有重叠,既在某一时刻只能执行一个任务;
(3)结束时间为任务开始时间与持续时间之和;
(4)超时的任务具体超时时间取值为0和
;(当在
小于0时取0;大于0时取自身的值);
运用lingo程序对模型进行求解,得到总超时时间最小值为32小时,此时的各任务的开始时间和实际完成时间以及执行顺序见下表:
任务
1
2
3
4
5
6
7
开始执行时间
6
11
17
2
0
27
25
实际完成时间
11
17
25
6
2
31
27
超时时间
1
0
10
0
0
16
5
顺序
3
4
5
2
1
7
6
任务执行的顺序为:
5-4-1-2-3-7-6。
总超时32小时。
六、模型的说明
本模型是计算机操作系统课程中任务调度算法的一个常见实例,模型一就是多种调度算法中的“先到先服务”算法的实现,模型二则是求的任务的平均带权周转时间最小值。
所以该模型具有一定的实用性和推广性。
但是不可避免的是计算精度问题运用程序单一可能导致结果不是很精确;从而得到的可能并不是最优方案。
附录
模型一的程序:
model:
sets:
jh/1..7/:
ft,st,ct,x;endsets
data:
ft=2540089;
ct=5684242;
enddata
min=@smax(x
(1),x
(2),x(3),x(4),x(5),x(6),x(7));
@for(jh:
st>=ft);
@for(jh:
x=st+ct);
@for(jh(i):
@for(jh(j)|i#lt#j:
(st(j)-x(i))*(st(i)-x(j))<=0));
end
模型一的lingo运算结果:
Localoptimalsolutionfound.
Objectivevalue:
Totalsolveriterations:
35
VariableValueReducedCost
FT
(1)
FT
(2)
FT(3)
FT(4)
FT(5)
FT(6)
FT(7)
ST
(1)
ST
(2)
ST(3)
ST(4)
ST(5)
ST(6)
ST(7)
CT
(1)
CT
(2)
CT(3)
CT(4)
CT(5)
CT(6)
CT(7)
X
(1)
X
(2)
X(3)
X(4)
X(5)
X(6)
X(7)
RowSlackorSurplusDualPrice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
模型二的程序:
model:
sets:
jh/1..7/:
ft,st,ct,x;endsets
data:
ft=2540089;
ct=5684242;
enddata
min=@sum(jh:
(x-ft)/7);
@for(jh:
st>=ft);
@for(jh:
x=st+ct);
@for(jh(i):
@for(jh(j)|i#lt#j:
(st(j)-x(i))*(st(i)-x(j))<=0));
end
模型二的lingo运算结果:
Localoptimalsolutionfound.
Objectivevalue:
Totalsolveriterations:
35
VariableValueReducedCost
FT
(1)
FT
(2)
FT(3)
FT(4)
FT(5)
FT(6)
FT(7)
ST
(1)
ST
(2)
ST(3)
ST(4)
ST(5)
ST(6)
ST(7)
CT
(1)
CT
(2)
CT(3)
CT(4)
CT(5)
CT(6)
CT(7)
X
(1)
X
(2)
X(3)
X(4)
X(5)
X(6)
X(7)
RowSlackorSurplusDualPrice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
模型三的程序:
model:
sets:
jh/1..7/:
ft,st,ct,x,wt;
endsets
data:
ft=2540089;
ct=5684242;
wt=1021151051522;
enddata
min=@sum(jh:
(@abs(x-wt)+x-wt)/2);
@for(jh:
st>=ft);
@for(jh:
x=st+ct);
@for(jh(i):
@for(jh(j)|i#lt#j:
(st(j)-x(i))*(st(i)-x(j))<=0));
end
模型三的lingo运算结果:
Localoptimalsolutionfound.
Objectivevalue:
Totalsolveriterations:
32
VariableValueReducedCost
FT
(1)
FT
(2)
FT(3)
FT(4)
FT(5)
FT(6)
FT(7)
ST
(1)
ST
(2)
ST(3)
ST(4)
ST(5)
ST(6)
ST(7)
CT
(1)
CT
(2)
CT(3)
CT(4)
CT(5)
CT(6)
CT(7)
X
(1)
X
(2)
X(3)
X(4)
X(5)
X(6)
X(7)
WT
(1)
WT
(2)
WT(3)
WT(4)
WT(5)
WT(6)
WT(7)
RowSlackorSurplusDualPrice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 期末 考试题