数学建模期末考试题

《数学建模期末考试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数学建模》课程期末作业题目：单台机器上的任务调度问题专业名称：金融信息工程所在院系：国际软件学院论文时间：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、平均处理任务时间的最小值，处理任务时间是指任务发布时刻到任务实际

2、完成时刻这段时间。3、总超时时间的最小值。一、问题描述在一台机器上将要处理一组任务，任务的执行之间不具有抢先性，也就是任务一个一个的顺序执行，任务的发布时刻，持续时间，规定完成时间如下表所示：任务发布时间持续时间完成时间1251025621348154041050256841579222要求构建三个数学模型，分别求出完成所有任务所需时最小值、平均处理任务时间的最小值和总超时时间的最小值。二、问题分析首先我们可以把题目中的数据进行处理，在不考虑任务重叠的情况下各个任务执行过程可直观的表示为下图所示：问题一，每个任务都有自己的执行时间区间，也就是开始执行时间到实际完成时间这一段时间区间，在任

3、务执行的过程中不能发生中断，也就可以简单的看成任意两个任务的执行时间区间不发生重叠，这样任务就可以一个一个的顺序执行。而对于一个将要执行的任务，其必须在任务发布之后，才可以正式开始执行。要求最小的完成时间就是相当于将这些线段在一定的条件下在一条直线上安排时期总长度最小。问题二，题目中已经给出平均处理任务是指任务发布时间到任务完成时刻这段时间，我们只需将问题一中模型的目标函数进行修改，求出总的处理任务时间的最小值，然后除以任务个数。问题三，超时时间是指：如果某个任务没有超时，则超时时间为0；如果某个任务超时，则超时时间为规定完成时刻到任务实际完成时刻这段时间。总超时时间为超时时间之和。要使

4、得这个值最小必须要使的所谓的冲突时间最小既是要最小。具体有如下定理支持：三、模型假设1、机器运行期间稳定好，没有内在和外来的故障发生。2、当任务还没有发布时，机器可以等待任务。3、机器可连续执行任务且任务切换所需时间忽略不计。4、任务可超时执行且不影响机器继续执行。四、符号说明——第个任务；——第个任务的发布时刻；——第个任务的持续时间；——第个任务的规定完成时间；——第个任务的实际完成时间；——第个任务的实际开始执行时间；——第个任务的完成超时时间；；——完成任务总需时；——平均处理任务时间；——总超时时间；五、模型的建立与求解5.1问题一的模型建立与求解由于任务执行过程中不发生中断，

5、也就是一个任务执行完之后下一个任务才可以开始执行，所以两个任务的执行时间区间不能发生重叠。每个任务的执行时间区间为[]，由区间不重叠的知识可以知道两执行时间区间不重叠的充分必要条件是：同时任务开始执行时必须已经发布，由题目中所给的条件爱你我们可以建立模型一如下：s.t约束条件说明：（1）开始时间必须在发布时间之后；（2）任务区间不得有重叠，既在某一时刻只能执行一个任务；（3）结束时间为任务开始时间与持续时间之和；运用lingo程序对模型进行求解，得到总需时最小值为31小时，此时的各任务的开始时间和实际完成时间以及执行顺序见下表：任务1234567开始执行时间14256202119实际完成

6、时间193114622521顺序4732165任务的执行顺序为：5-4-3-1-7-6-2。这个顺序并不是唯一的总时间最小为31。5.2问题二的模型建立与求解处理任务时间是指任务发布时刻到实际完成时刻这段时间，我们可以通过求出所有任务的总处理任务时间最小值除以任务个数，即可得到平均处理任务时间最小值。这里我们只需要对模型一中的目标函数进行改动就可以得到模型二，如下：s.t约束条件说明：（1）开始时间必须在发布时间之后；（2）任务区间不得有重叠，既在某一时刻只能执行一个任务；（3）结束时间为任务开始时间与持续时间之和；运用lingo程序对模型进行求解，得到平均处理任务时间最小值为12.28

7、571小时，此时的各任务的开始时间和实际完成时间以及执行顺序见下表：任务1234567开始执行时间20256201614实际完成时间253114622016处理任务时间22261062127顺序6732154任务的执行顺序为：5-4-3-7-6-1-2。平均处理任务时间最小值为12.28571。5.3问题三的模型建立与求解因为超时时间有两种情况，一种实际完成时间比规定完成时间小，一种实际完成时间比规定完成时间大。我们可以对得到超时时