时间网络图

时间网络图（共4篇）

时间网络图 篇1

0 引言

为了优化工程周期, 实现资源的最大化, 需要借助计算模型对工程各项工作的开始时间、完成时间以及推迟时间等进行科学的分析, 而这些工作开展的前提需要确定准确的时间参数, 因此研究网络图时间参数的识记经验对于加深对工程设计的认识具有积极的作用和现实的意义。

1 网络图时间参数的重要性

网络图时间参数在建筑行业中具有重要的作用, 它是建筑专业的基础知识点, 也是各项知识学习的基础, 首先网络图时间参数是工程进行各项进度安排、工作周期设计的基础因素, 只有正确理解与应用时间参数才能将工程关键工作落实到实处;其次网络时间参数也是进行其他工程时间安排、优化工程网络化计划、控制工程进度的重要依据, 通过时间参数的确认可以将工程的一些工作进行对比参考, 提高工程的建设效率;最后网络时间参数是建筑行业工作人员最基本的知识, 也是工作人员从事建筑工程行业的前提, 如果工作人员对网络图时间参数没有清晰的认识, 那么无论其专业知识怎么丰富, 都不可能对工程进行科学的计算, 因此要从事建筑工程行业工作前, 要具备独立认识网络图时间参数的能力。

2 网络图时间参数的内容构成及符号

网络图时间参数主要由工期、工作的时间参数以及节点的时间参数构成。具体内容见表1。

针对表1可以清晰的认识到网络图时间参数的基本概念: (1) 最早开始时间就是紧前工序全部完成、本工序可能开始的时间。 (2) 最早完成时间是本工序最早可能完工的时间, 也就是最早开始时间与持续时间之和。 (3) 最迟完工时间 (简称迟完) 是在不影响全工程如期完成的条件下, 本工序最迟必须完工的时间。 (4) 最迟开始时间是在不影响全工程如期完成的条件下, 本工序最迟必须开工的时间。 (5) 总时差指一道工序所拥有的机动时间的极限值。一道工序的活动范围要受其紧前、紧后工序的约束, 它的极限范围是从其最早开始时间到最迟完成时间这段时间中, 扣除本身作业必须占有的时间之外, 所余下的时间, 这段时间可以机动使用。它可以推迟开工或提前完工, 如可能, 它也能继续施工或延长其作业时间, 以节约人员或设备。 (6) 自由时差是总时差的一部分, 是指一道工序在不影响紧后工序最早开始前提下, 可以灵活机动使用的时间。这时, 工序活动的时间范围被限制在本身最早开始时间与其紧后工序的最早开始时间之间。从这段时间扣除本身的作业时间之后, 剩余的时间就是自由时差。

因为自由时差是总时差的构成部分, 所以总时差为零的工序, 其自由时差也必然为零。一般地说, 自由时差只可能存在于有多条内向箭杆的节点之前的工序之中。

3 网络图时间参数标记的经验分析

网络图时间参数具有工作时间参数和节点时间参数两种方式, 在一般的工程时间参数的计算方式中, 人们应用工作时间参数的途径比较多, 因此本文主要以工作的时间参数识记经验为重点阐述内容, 工作的时间参数主要有持续时间、最早开工时间、最迟开工时间、最迟开始时间、最迟完成时间、总时差以及自由时差。针对这些比较绕口而且繁多的时间参数需要掌握一定的灵活方法进行识记。

3.1 牢固掌握最基本的时间参数

中职学生由于他们的抽象化思维模式还不成熟, 他们的发散性思维相对比较狭窄, 他们对于这些种类繁多、而且名字比较绕口的时间参数的认识存在一定的概念混淆, 因此学生掌握这些时间参数的前提就是要熟悉的掌握最基本的时间参数的概念, 能够对基本的时间参数有一个清晰的认识, 比如“工作持续时间”是工程建设中经常使用的时间参数, 工作持续时间的概念是一项工作从开始到完成的时间。对于此概念学生是很容易理解的, 因为工作持续时间如论是从概念上还是在其日常的应用上都是比较使用广泛的。

3.2 从时间参数的名称入手, 了解时间参数

虽然网络图时间参数的种类比较繁多, 而且每个时间参数的内容比较难以理解, 但是主要掌握时间参数的内在关联规律就可以轻松的熟记各种时间参数。例如时间参数的名字符号与其英语单词的第一个字母是相同的, 工作持续时间就是Di-j, D就是“date”的名称缩写, i-j的下标就是前后两个节点的编号;“最早开始时间”则是由“早的”英文“early”, “开始”英文“start”, 取它们两个单词的第一个字母并大写。ESi-j就是最早开始时间。通过对时间参数的英文的了解, 可以帮助学生在看到时间参数字母符号的时候能够在一时间做出其英语词汇的反应, 进而知道此符号所代表的含义。

3.3 在实践中要广泛应用各种时间参数

对于网络图时间参数的识记并不能单靠死记硬背的方式获得, 而必须要借助灵活的学习方式, 才能将枯燥的网络图时间参数转化为自己的内在知识, 首先学生之间要相互的讨论与分析不同时间参数的区别, 对比不同时间参数的意义, 以及其描述的事项内容, 通过学生之间的相互讨论可以增强学生对时间参数认识的理解程度, 有关研究表明:讨论式学习比学生的死记硬背效果要强很多;其次学生要在时间参数计算中广泛使用不同的时间参数, 通过对时间参数的计算可以增强应用时间参数的经验, 从而提高了自己在以后的工作中的实践应用能力。

3.4 教师要侧重对网络图时间参数本质讲解

学生对于网络图时间参数的理解存在不深刻, 认识不全面的问题, 因为中职学生对于立体式的图形的概念还没建立相应的立体模型, 学生不能对其的本质意义有深刻的认识, 对此教师需要掌握授课方式, 通过灵活多变的手段, 以迎合学生的学习兴趣为契机, 增强学生的学习兴趣, 将学生的主动学习性充分的发挥出来, 实现学生对网络图时间参数的灵活应用。

参考文献

[1]王立霞, 刘天萍.施工组织设计[M].北京, 中国建筑工业出版社, 2012, 3:54-55.

[2]李文涛.双代号网络计划的时间参数计算及其要点[J].科技信息, 2010 (23) .

[3]徐运明双代号网络计划时间参数的教学模型[J].中国建设教育, 2013 (1) .

[4]冯永伟.基于网络计划技术的工程设计进度管理[J].建筑设计管理, 2012 (2) .

二部图网络信息传输的最短时间 篇2

对于计算机网络, 人们最关心的通常是它的传输效率, 也就是以最短的时间传送最多的信息量。例如, 一个单位的各部门每天都需要共享信息, 即需要用网络进行信息传输。于是, 如何设计传输方案, 使得把所有的文件都传输完毕的时间最短就显得极为重要。

本文通过探讨二分图网络传输信息的方法, 结合图论中的匹配、边着色等原理, 给出了相应的算法, 并得到此类网络传输信息的最佳方案, 从而解决树状网络、棋盘网络、蜂巢网络等常见的二分图状网络的信息传输优化问题。

2 预备知识

定义1:设G是无环图, M⊆E (G) , M≠φ, 若M中任意两条边在G中都不相邻, 则称M是图G的一个匹配。

定义2:若对图G的任意匹配M', 均有, 则称M为图G的最大匹配, 且M中的边数称为匹配数。

定义3:设M是图G的匹配, G中与M中的边关联的顶点称为M饱和点, 否则称为非M饱和点。

定义4:设M是图G的匹配, P是G的一条路, 且在P中M的边和E (G) -M的边交替出现, 则称P是G的一条M交错路。若M交错路P的两个端点为M非饱和点, 则称P为M可增广路。

定义5:图G的边色数 (记作χ' (G) ) 是指给G的边着色, 使得相邻边的颜色都不同, 所需的最少颜色数。

性质1:若G是连通的简单图, G的最大顶点度为, 则

性质2:若G是二分图图, 则χ' (G) =∆ (G) 。

性质3:图G的边不交匹配的最小数目即为图G的边色数。

3 主要结果

3.1 问题描述

某单位各部门每天都要使用二分图网络传输信息, 网络用图G表示, 其中各部门 (计算机) 用顶点表示v1, v 2, L, vn, 两个部门 (计算机) 之间要传输的文件用边e1, e 2, L, em表示。假定:任一文件的传输时间都为1, 任一计算机可以同时传输的最大文件数目为1;每个文件的传输以一个连续的整体进行, 文件传输无优先权, 即文件一旦开始, 不得中断直到所有文件传输完毕;传输的切换时间可以忽略;所有计算机不给自身传输文件。我们要设计一种最佳的传输方案, 使网络总的传输时间最短。

3.2 算法描述

根据问题的描述, 我们可以得到不同的传输方案, 但无论怎样传输, 一对正传输一个文件的计算机都不能进行另外一个文件的传输。因此, 我们可以通过选择网络中适当的边, 得到某种匹配。当把每个时间单位分开考虑时, 就会得到边不交的多个匹配, 这些匹配恰好覆盖了整个图。由此得到, 最小的传输时间就等于产生整个图的最少匹配数。

由于G是二分图, 所以由性质2、性质3知, G的边不交的最少匹配数就等于G顶点的最大度。下面, 我们结合二分图的最大匹配生成法, 给出找G的边不交的最少匹配的算法。设G具有二部划分 (V1, V2) 。

BEGIN

Step1.令0G=G;

Step2.任给0G初始匹配M, 若M不存在, 则结束, 否则转st ep 3;

Step3.若M饱和1V, 则M是最大匹配, 输出M, 转step8;否则转step4;

Step4.在1V中找一非M饱和点x, 置S={x}, T=φ;

Step5.若N (S) =T, 则停止;否则任选一点y∈N (S) -T;

Step6.若y为M饱和点, 则转step7;

否则作一条从x到y得M可增广路P, M= (M-P) U (P-M) 置, 转step3;

Step7.由于y是M饱和点, 故M中存在边yu, 置S=S U{u}, T=T U{y}, 转st e p 5;

S t e p 8.置G0=G0M, 转s t e p 2.

END

设图G有n个顶点, m条边, 且顶点最大度为∆。在找最大匹配时, 该算法最多找n条可增广路, 每找一条可增广路, 最多比较m条边, 又由前面的分析知, 总共找到的匹配数等于图G的顶点最大度。因而该算法的时间复杂度为O (∆nm) , 故该算法为有效算法。由性质3知, 该算法得到的匹配数也就是传输完所有文件所需的最少时间。同时, 每次找图的最大匹配也使得单位时间内传输的文件数最多, 故应用该算法可得最优传输方案。

3.3 实例求解

某单位有22个部门, 每个部门一台计算机 (分别用图1中G的22个顶点表示) , 每天需传送24个文件 (分别用图1中G的24条边表示) 。假定:任一文件的传输时间都为1, 任一计算机可以同时传输的最大文件数目为1。我们设计一种传输方案, 使得网络总的传输时间最短。G是一个二分图, 利用以上算法, 可依次得到G的4个匹配为:

从而我们得到该网络的一个传输方案, 如表1。

4 结语

本文结合最大匹配的生成算法, 给出了二分图网络信息传输的最优方案。该方案不仅使得所有文件传输完毕的时间最短, 还保证了在任意时刻之前传送的文件量最大, 从而解决了树状网络、棋盘网络、蜂巢网络等常见的二分图状网络的信息传输优化问题。

摘要：本文利用图论中的匹配、边着色等原理, 探讨了二分图网络传输信息的最佳方案, 并给出相应的算法, 使得网络总的传输时间最短。

关键词：二分图,网络,匹配,边色数

参考文献

[1]卜月华.图论及其应用.南京:东南大学出版社, 2002.

[2]殷剑宏, 吴开亚.图论及其算法.合肥:中国科学技术大学出版社, 2005.

时间网络图 篇3

考试时间安排属于典型的时间表问题 (Time Table Problem, 简称TTP) , 本文对时间表问题的论述就是针对大学考试时间表问题的。为提高考试时间安排的科学性和合理性, 本文设计并实现一种新的图着色方法来解决考试时间安排问题, 并使得算法满足以下需要:

(1) 通过合理安排考试时间, 使冲突人数减少到最低。

(2) 多数学生的考试时间间隔尽量大, 以保证学生有足够的休息时间。

1问题的描述

大学考试时间表问题即在一些有限的时间段中安排考试, 同时要求避免冲突并且满足一些约束条件, 本文所要解决的考试时间安排有以下要求:

硬约束条件:

(1) 考试时间段固定, 一般是每天4个考试时间段。

(2) 集中考试时间, 全校所有专业的考试都安排在一周之内。

(3) 所有学生的正考科目 (当学期所开设课程) 不允许有冲突。

(4) 考场有限, 监考老师有限, 这两者属于一体要求。

软约束条件:

(1) 各个时间段安排的考试科目数目尽量均衡。

(2) 同一年级的学生参加的考试课程在时间安排上应有一定的间隔。

(3) 使得补考学生出现考试时间冲突的数目降到最低。

2算法的总体设计思想

本文所研究的图着色类型是给定颜色数m, 要求对图的顶点或边进行着色。

m着色:给定一个无向连通图G和m 种不同的颜色, 用这些颜色为图G的各顶点着色, 每个顶点着一种颜色。是否有一种着色法, 使G中每条边的两个顶点着不同颜色, 这个问题是图的m 可着色判定问题。若一个图可用m种颜色着色, 求一个图的m着色方案, 为m 可着色优化问题。m可着色判定问题是NP难度的问题。

在求解时间表问题时, 要求在一定数目的时间段内完成所有活动, 使有冲突的活动被安排在不同的时间段中。与图着色问题相关联, 将图中的顶点看作活动, 有冲突的活动 (顶点) 之间用一条边相连, 相应的问题求解转化为有连边的节点分配不同的颜色, 使得所用的颜色数目最少。

2.1建立图着色模型

在考试时间安排的问题中共有n门课程, 要安排在m个时段中进行考试, 每门课程的考试人数不等, 构造图G, 包含n个顶点, 每个顶点表示一门课程。每个顶点的权值表示报考该顶点所代表课程的总人数, 边上的权值表示同时报考该边相连的两个顶点所表示课程的学生人数。

在构造无向图时, 先选择一个专业, 将该专业的各个年级在本学期所学的课程分别提取出来, 形成一个一个的无向完全子图 (也称为团) , 并根据学生人数形成每个团中顶点的权值。

考试问题描述:假设某系有三个年级同时进行期末考试, 假设不考虑补考和公共课的情况。一年级共有50人, 需要考试的科目有ABCD四门, 这里我们称为一年级的正考科目为ABCD四门, 二年级共有60人, 正考科目为EFGH四门, 三年级共40人, 正考科目为I和J两门。其中二年级中有15人需要补考课程C, 又有5人需要补考课程A, 三年级的考生中有8人需补考B课, 那么二年级中有15人不仅要参加课程E、F、G、H的考试还要参加课程C的考试, 就需要将C分别和团中的顶点E、F、G、H连接起来, 并将权值15加到对应的边上。其他补考的连接方法以及权值设置同上, 这样就使得原来孤立的各个团之间建立起联系, 如图1所示:

针对具体考试问题, 本文中我们给出一个自定义的概念——原始团, 后文中提到的原始团都是指:每个年级的正考科目所组成的一个团。

这样, 图1中共有ACEFGH, ABCD, IJB三个团, 其中最大团ACEFGH是在原始团EFGH (二年级正考科目) 的基础上, 因为有个别人需要补考其他年级的课程AC, 连接后形成的, 这就使得A和C都不能和EFGH之一分在同一个时间段。而团IJB, 是在原始团IJ (三年级正考科目) 的基础上, 因为有个别人需要补考其他年级课程B连接后形成的, 显然补考现象的出现加大了考试课程时间安排的复杂度。对于公共课和补考情况大同小异, 这里不再具体阐述。

图1中每个顶点的权值表示报考该顶点课程的总人数, 边上的权值表示同时报考该边两个顶点所表示课程的学生人数。

一般来说, 在考试安排中, 所提供的考试时间段不应少于最大原始团的顶点个数。应首先安排正考科目, 使得科目之间的考试时间尽量有一定的间隔, 在安排补考科目 (对其他人也是正考科目) 时, 既要考虑不产生冲突, 也要考虑与已经安排好的时间段之间有一定的间隔。

2.2设计思路

在算法设计上, 模拟人工安排考试时间的方式, 先安排一些特殊课程, 如公共课, 因为参加公共课考试的人数较多, 所以一般将公共课考试的时间选在某个上午时间段中;再按照专业年级来划分课程, 将正考课程最多的一个年级的各门考试分散到各个时间段中, 注意产生间隔, 后面依次安排各个年级的考试课程, 既要产生一定间隔又要防止产生冲突。

3算法的设计

3.1算法的初始化

(1) 构造边集数组Gset={{ v11, v21, p1}, { v12, v22, p2}, { v13, v23, p3}, …, { v1k, v2k, pk}} (其中k为图中边的总数) 用来存放图, 数组中每个单元包括三个域, 分别为顶点v1、顶点v2、顶点v1和v2之间边的权值p。

(2) 构造G'= (T', V') 其中T'和V'分别表示已着色的团集合和点集合, G = (T, V) 用来表示还没有着色的团集和点集。

(3) 构造数组Color = ( c1 , c2 , ..., cm ) 初始值为0, 表示每种颜色已着色顶点的权值之和, m为可提供的颜色总数。

(4) 对于每个团都构造一个数组c[m+1]为布尔型, 初始值为false, c[i] (其中i>=1&&i<=m) 的值为false表示该颜色i可用, true表示该颜色i不可用。

3.2算法的设计

该算法是基于团集的图着色算法, 算法描述为:

(1) 首先令已着色的团集合和点集合分别为空, 即T'=θ, V'=θ。未着色的团集合T={ T1, T2, T3, ……, Tk }, k为图中团的个数, 点集合V={V1, V2, V3, ……, Vn}, n为图中顶点的总数。

(2) 找出T中包含顶点最多的一个团Ti 即最大团, 计算出该最大团中顶点个数vnum, 如果m>=vnum, 即所给颜色数不少于最大团的顶点个数, 则将该最大团Ti的顶点集合Vi着为不同的颜色;否则, 即所给颜色数少于最大团的顶点个数, 也就是颜色数不够用的情况, 这时着色过程中必然会产生冲突, 那么找出包含最大原始团的那个团Tj, 将该最大团Tj的顶点集合Vj着为不同的颜色。

对最大团中顶点着色后计算V'=Vi, V=V-Vi, T=T-{Ti}, T'={Ti}, Color=Color+u, 即将已着色的团和顶点加入到G'= (T', V') 中, 并从G= (T, V) 中删除, 同时更新数组C。

(3) 对T中每一个团计算ai=|{u|u∈Ti, u∉V}| , 即计算T中每个团尚未着色顶点的个数ai。若ai = 0, 则该团中的所有点都已经着色, 运行T=T-{Ti}, T'=T'∪{Ti} , 若ai=|Ti|, 则该团中的所有点都尚未着色, 说明V'与V是不相连的, 返回第2步。若ai <|Ti|, 则该团中有部分点已经着色, 找出一个ai值最小的团Ti。

(4) 对于Ti中的顶点u, 若u∈V, 那么必有u∉V', 在V'中遍历该团已着色点的颜色值, 对应将c[colorsize+1]中的值设为true, 如果可用颜色数多于未着色的顶点数则在选择颜色数的时候也要尽量产生一定的间隔;如果可用颜色数等于未着色的顶点数, 则依次将这些顶点着色为所剩颜色数;如果可用颜色数小于未着色的顶点数, 即颜色不够用的情况, 则优先安排顶点权值大的顶点着色, 对于当前一个权值较小的顶点v, 依次和已安排着色的顶点之间的边权值进行比较, 将v着色为与之相连的边权值最小的那个顶点颜色。

对u着色后运行V=V-{u}, V'=V'∪{u}, 对T中所有顶点着色结束后运行T=T-{Ti}, T'=T'∪{Ti}。Color=Color+u。

(5) 判断T=ϕ吗, 如果为空则计算结束返回着色结果G, 否则返回第3步。

3.3考试时间间隔的优化

算法中的颜色值与实际的时间段是对应的, 为使同一年级甚至是同一个学生所参考的课程在时间安排上有所间隔, 就必须在着色时注意颜色的选取。因此在给同一个团中的每个顶点进行着色时, 按照一定的算法来完成。

当一个团中的所有顶点都还没有着色时, 则所提供的颜色数m对于当前团可能是全部可用, 也可能是部分可用。

如果m种颜色全部可用, 则对于团中顶点着色时的可选空间很大, 这时应尽量使得该团中的顶点着色均衡分布, 即产生一定的间隔。产生间隔的方法是:

(1) 当前总颜色数为m, 团中共有vnum个顶点, 首先令团中第一个顶点着色为1, 记为k=1, 令vnum--;

(2) 判断当前团中是否还有未着色点, 如果有就转到第3步, 如果没有就停止;

(3) 计算k+= (m-k) /vnum;使得当前顶点着色为k。令vnum--;转到第2步。

如:所提供的颜色数目总数为m=16, 1-16为16种颜色代号, 如图2所示, 当前待着色团为Ti={ABCDE}, 根据算法, 将Ti中的顶点ABCDE分别着色为:

A——1, B——4, C——8, D——12, E——16, 如图3所示:

这样就使得团Ti中的顶点均衡分布在整个区间中, 也就相当于将课程均匀分布在考试时间段中了。

如果m种颜色只有部分可用, 则对于团中顶点着色时的可选空间相对减少, 这时也要尽量使得该团中的顶点着色均衡分布, 但不能用以上的方法来实现, 所以设计一个算法, 该算法每次都能够找到最大可用区间, 将当前顶点放到该区间中。

最大可用区间的查找方法:

(1) 初始化颜色值为i=1, 可用颜色区间中包含的颜色总数为max=0

(2) 如果i小于m+1, 则转到第3步, 否则停止。

(3) 初始化当前可用颜色区间中包含的颜色总数为count=0

(4) 当前的颜色i是否可用?如果能用则转到第5步;如果不能用则i=i+1, 转到第2步。

(5) 执行count++, 令j=i+1, j为颜色i的下一个颜色

(6) 如果j小于m+1, 则转到第7步, 否则停止。

(7) 判断当前颜色j可用吗?如果可用则令count++, j++, 转到第6步, 如果不可用则转到第8步

(8) 判断count>max吗?如果是, 则令max=count, 用end=j-1, beg=end-count+1, 否则另i=i+count并转到第2步。

算法结束后用beg和end记住的分别是区间的起始位置和结束位置。

如:当前需着色团为Tj=BDFGH, 因BD在团Ti中已经被着色, 所以颜色4和颜色12不能用, 如图4所示:

这就使得当前可用颜色共有3个可用区间, 分别是[1,2,3]、[5,6,7]和[13-16], 通过以上算法能够找到最大可用区间为[5,6,7], 那么将把Tj的顶点F放在该区间中, 放置的位置由beg+ (end-beg+1) /2的值来决定。

对F着色后, 着色表如图5所示:

对G着色后, 着色表如图6所示:

对H着色后, 着色表如图7所示:

这样也能够保证团Tj中的顶点均衡分布在整个区间中。

3.4算法改进

以上算法在考试时间安排上还考虑到考场场地的限制问题。如果考场有限, 一个考场只能容纳30人, 而某一场考试时间安排的考试人数有可能会超出了考场限制, 解决的办法是在算法中引入一个阈值, 该阈值就是所有考场最多可容纳人数。构造方法check ( c, u) 为布尔性, 功能是如果u着色为c, 将u的权值加到数组Color[c]中后, 如果Color[c]的值低于阈值就返回true, 表示u可以着色为c;否则返回false, 表示u不可着色为c。

这样就可以防止某一场安排人数超标的情况, 同时, 可将阈值设的小一些, 保证每个时间段的考试人数基本持平, 可见阈值的引入也可做到协调监考人员工作量的作用。

4算法测试

该算法的测试工作是通过一个基于该算法实现的考试时间安排系统完成的。测试需要输入的主要数据包括专业信息、课程信息、学生报考信息、时间段、每场考试最多容纳的人数。下面是对6个专业、116门课程、647个学生数据分类进行测试。

根据前面讲述的算法, 在班级属性中加上一个clash值, 表示此次安排方案产生的冲突系数, 各课之间的时间间隔为0、1、2、3、4、大于4时该项冲突系数分别累加100000、20、5、2、1、0。计算clash值, clash的值越小, 则同一班级的考试课程之间的时间间隔越大, 由此可通过判断比较clash值得到较为合理的时间安排方案。

下面是不同时间段进行考试时间安排的比较, 如表1所示:

可见, 在考场可容纳人数不变的情况下, 时间段越多, 各个年级的考试科目所在的时间段之间的间隔越大。管理人员可通过以上的数据表, 分析找出合理的时间段安排, 既能保证不产生冲突, 也能在集中的时间内完成所有考试。但是当考场可容纳人数较小时, 必须通过增加考试时间段来解决考试时间安排问题。

5结束语

由于算法在设计上考虑到冲突问题, 在安排时间时, 充分利用顶点权值、边权值的判断, 可以使得发生冲突的考试人数降到最低, 同时使得多数学生的考试时间间隔尽量大。而由于报考学生人数庞大、报补考科目种类繁多, 手工安排不可能解决这一问题。

以该算法为核心设计的考试时间管理系统不但能将教务人员从繁重的考务工作中解放出来, 还能自动形成科学、合理的考试安排时间, 对于促进办公自动化的发展具有重要意义。

参考文献

[1]Tim B.Cooper, Jeffrey H.Kingston.The Complexity of Timetable Construction Problems.Proc.ICPTAT95, 1995, 183～295

[2]MW Carter, G Laporte, and Chinneck.A general examination scheduling system.INTERFACES, May-June1994, 24 (3) :109～120

[3]Fred Buckley, Marty Lewinter著.李慧霸, 王凤芹译.图论简明教程.清华大学出版社, 2004.117～119

[4]王晓东编著.算法设计与分析.北京:清华大学出版社, 2003.

[5]陈卫东.求图着色问题的新算法.微计算机应用, 2004, 25 (4) :

[6]程泉, 朱大铭.用图的着色方法求解考试时间安排问题.计算机应用, 2005, 12

时间网络图 篇4

我国环境监测总站公布各大主要城市空气质量日报已有多年的历史, 它是认识和研究大气环境质量的一种方法, 它不仅仅给人们的生活带来了很大的便利, 同时也给各相关部门制定相关的环境政策提供了参考依据。而今, 随着工业化和商业化的加剧, 大气环境质量也越来越差, 这就亟需对城市大气环境质量进行客观、实时的评价。目前, 我国的城市质量日报常规检测的几种空气污染物为SOx、NOx、PM10浓度, 监测数据的取位主要依据所使用仪器的精度和分析方法的最低检出浓度的有效数字所能达到的位数确定[1,2]。

到现在为止, 许多统计方法和计算机应用技术应用于大气环境质量评价中, 如模糊数学的综合评价方法[3], 找到了影响空气质量的主要污染因子, 并为降低和防治大气污染提供建议;GIS技术[4], 实现了大气环境模拟与评价结果的可视化管理;灰色系统预测模型[5], 通过实例的运用表明模型具有实用价值等, 而文献[4]采用时间序列分析方法[6], 对西安市2004~2008年PM10月平均浓度时间序列数据建立自回归滑动平均模型模拟实测的PM10浓度, 并对模拟结果进行了检验。文献[6]绘制多元自相关[7]过程的残差T2控制图, 并且通过蒙特卡洛模拟得出残差T2控制图能有效控制出现大偏移的多元自相关过程。但是, 几乎没有人将环境空气质量数据用于自相关残差控制图的绘制。包头市环境质量年报公布的2012年1月1日~2012年12月31日的市环境监测站的SOx、NOx、PM10浓度随时间的推进发生改变, 并且存在自相关的现象, 通过相关监测值建立时间序列模型, 以历史资料进行参数估值后便可以计算该监测指标的残差, 从而建立残差T方控制图[8,9]。时间序列模型分为:自回归 (AR) 模型、移动平均 (MA) 模型、自回归移动平均 (ARMA) 模型、自回归综合移动平均 (ARIMA) 模型等。

1 ARIMA时间序列模型

ARIMA是自回归移动平均结合 (Auto Regressive Integrated Moving Average) 模型的简写形式, 其应用范围很广泛, 但它只限于考虑平稳的时间序列或者是经过差分后平稳的时间序列。

(1) 自回归模型 (autoregressive, AR)

一个p阶自回归模型AR (p) 可表示如下:

其中准i, i=1, …p是自回归参数, ut是白噪声序列, Xt是由它的p个滞后变量的加权和以及ut相加而成。

(2) 移动平均模型 (moving average, MA)

一个q阶移动平均过程模型MA (q) 可表示如下:

其中θ1, θ2, …, θq是回归参数, ut为白噪声序列, 之所以称"移动平均", 是因为Xt是由q+1个ut和ut滞后项的加权和构造而成。"移动"指t的变化, "平均"指加权和。

(3) 自回归移动平均模型 (autoregressive moving average, ARMA)

由自回归和移动平均两部分共同构成的随机时间序列模型就成了自回归移动平均模型, 记为ARMA (p, q) , 其中p, q分别表示自回归和移动平均部分的最大阶数。ARMA (p, q) 的一般表达式是

自回归移动平均模型 (ARMA) 是随机时间序列分析模型的普遍形式, 自回归模型 (AR) 和移动平均模型 (MA) 是它的特殊情况。

当然, 这些模型只适合于平稳的时间序列, 如果一个时间序列是不平稳的, 那么首先应该把它转换成一个平稳的时间序列, 常用的转换方法是差分, 用公式表示就是:

把上面三个方法结合在一个模型中就成了ARIMA (p, d, q) 模型。其中p表示被回归项的滞后期数, q表示随机干扰项的滞后期数, 而d表示差分的阶数。

2 SOx、NOx、PM10浓度时间序列数据的模型拟合及控制图分析

本文选取了内蒙古包头市五个监测站的SOx、NOx、PM10浓度数据进行模型拟合以及控制图的绘制。每个监测站的每个监测项目都是从2012年1月1日~2012年12月31日的日浓度数据, 共366个观测值。下面主要以市环境监测站的SOx、NOx、PM10的浓度数据进行分析。

图1是内蒙古包头市SOx日观测浓度的时间序列, 基本可以看出其是一个非平稳的序列。利用EVIEWS7.0软件对原序列进行ADF单位根检验, ADF值为-2.318584大于1%的置信度水平, 接受原假设, 得知该时间序列含单位根, 也即该序列是一个非平稳的时间序列。为了消除非平稳性, 对原序列进行一阶差分处理, 并对差分后的数据进行ADF单位根检验, ADF值为-9.474383小于1%的置信度水平, 拒绝原假设, 得出一阶差分后的时间序列不含单位根, 是一个平稳的序列。因此初步断定为ARIMA模型, 并且模型的参数d=1。

接下来我们需要做SOx一阶差分数据模型的识别和检验, 即确定模型的类型以及相应的阶数。绘制这个序列的ACF和PACF图, 如图2所示, 从图中可以看出, 自相关函数在滞后2阶处截尾, 偏自相关函数呈指数衰减, 并且衰减的速度比较快, 符合拖尾的特征, 根据AIC准则和其他如参数显著性检验, 本文选取了ARIMA (0, 1, 2) 模型。

对SOx浓度时间序列ARIMA (0, 1, 2) 模型进行最大概似估计, 估计结果为:模型的标准误差比较低, 模型的精度较高, 且模型的两个因素MA1、MA2均能在0.05的显著水平下通过检验。

对此模型的残差进行检验, 模型的残差都在置信区间范围内, 可认为与0无明显差异, 已基本上消除了自相关和偏自相关, 表明残差序列是白噪声, 也即残差序列是服从正态分布并且独立的。

综合上述分析可以得出结论, 利用ARIMA (0, 1, 2) 模型对SOx浓度时间序列建模是合适的。

通过建立上述模型, 可以计算出SOx浓度时间序列模型的残差值, 暂且存储在minitab软件中。

内蒙古包头市环境监测站的NOx、PM10的浓度数据的模型拟合方法、步骤和上面对SOx浓度数据的时间序列分析基本一样, 在此不再详细的分析过程, 仅将最后的残差计算同SOx浓度时间序列模型的残差计算结果存储在minitab16软件中, 由于篇幅所限, 在此仅提供部分残差值数据如表1所示。

由于SOx、NOx、PM10浓度时间序列残差数据是白噪声序列, 各自浓度数据独立且服从正态分布, 并且两两之间通过SPSS17.0软件做残差变量间的相关性分析得知存在相关性, 符合传统统计过程控制理论中统计量彼此独立的基本假设, 也同时满足多元T2控制图的变量间相关的条件, 由于篇幅所限, 在此不列出残差T2控制图的统计量、上控制限以及判断过程是否出现异常的准则, 直接绘制SOx、NOx、PM10浓度时间序列模型的残差控制图, 如下图所示:

由以上的残差控制图我们可以看出出界点有5个, 分别为:12.4.26、12.10.11、12.12.2、12.12.12、12.12.26这5个日期。

3 结论

本文选取内蒙古包头市五个监测站中的市环境监测站的SOx、NOx、PM10浓度的日观测资料时间序列, 应用最大概似估计, 进行ARIMA模型的拟合和控制图的绘制, 结果表明在模型的拟合方面取得了较好的效果。

由于选取的是内蒙古包头市市环境监测站的日观测SOx、NOx、PM10浓度时间序列数据进行估计, 并且每个浓度的分析结果都令人满意, 因此应该可以说明其余监测站的SOx、NOx、PM10浓度资料都适合这种ARIMA模型的拟合。只是在进行拟合时, 应对SOx、NOx、PM10浓度资料进行详细地分析以得到最好的效果。因为虽然都是SOx、NOx、PM10浓度资料, 但是每个监测的每个浓度的ARIMA模型的参数或许会不一样, 即其中的参数p、d、q可能完全不一样。

值得说明的是, 时间序列ARIMA模型所描述的是时间序列的短期变化关系, 而不是长期变化关系, 因此, 利用时间序列模型可以进行对监测站日观测SOx、NOx、PM10浓度数据的短期预测。

摘要：利用统计学软件, 对内蒙古包头市2012年1月1日2012年12月31日市环境监测站的SOx、NOx、PM10日浓度数据, 进行了时间序列分析, 并建立了时间序列模型 (ARIMA) 。然后对模型进行识别、估计, 并对估计后的残差进行检验, 经检验后的SOx、NOx、PM10浓度的残差值均为白噪声序列, 则计算出相应的SOx、NOx、PM10日浓度的残差值。由于残差值满足传统的统计过程质量控制理论中的统计量彼此独立的基本假设, 因此我们绘制出多元自相关过程的残差T2控制图。实例应用表明, 该方法是合理科学的。

关键词：ARIMA模型,时间序列,残差T2控制图

参考文献

[1]瞿德业, 周围, 陈雷华, 汪君, 鹿晨昱.兰州市城区空气气溶胶中PM2.5和PM10污染状况分析[J].干旱区资源与环境, 2013, 27 (1) :70-74.

[2]郭勇涛, 佘峰, 王氏功, 刘炳杰, 李江萍, 王金艳.兰州市空气质量状况及与常规气象条件的关系[J].干旱区资源与环境, 2011, 25 (11) :100-105.

[3]郑健.2001-2011年乌鲁木齐市大气环境质量模糊数学综合评价[J].环境污染与防治, 2014, 1 (36) :28-33.

[4]郭东恩, 沈燕, 张峰.GIS技术在大气环境模拟与评价系统中的应用探讨[J].测绘科学, 2011, 36 (5) :100-102.

[5]戴华炜, 陈小旋, 孙晓通.基于GM (1, 1) 模型群的深圳市大气污染物灰色预测[J].数学的实践与认识, 2014, 44 (1) :131-136.

[6]樊敏, 顾兆林.时间序列分析在大气环境中的应用[J].资源环境与发展, 2010, 1:19-22.

[7]Seoung Bum Kim, Weerawat Jitpitaklert, Sun-Kyong Park, SeungJune Hwang.Data mining model-based control charts for multivariate and autocorrelated processes[J].Expert Systems with Applications, 2012, 39:2073-2081.

[8]孙静, 杨穆尔.多元自相关过程的残差T2控制图[J].清华大学学报 (自然科学版) , 2007, 47 (12) :2184-2187.