排课程序时间片选择的安全决策调度算法

排课表程序中选择合适时间的问题,其本质上是寻找教室、教师和学生班级的公共有空集合,1975年Itai及Shamir证明了课程表问题也是一个NP-完全类问題。从而结束了该问题上很多学者之间的论争。可把排课表问题分成两个层次进行,首先选择合适时间,然后再根据这个时间进行教室调度。而教室调度在各类学校是大不相同的,本文着重讨论了根据安全决策准则来选择合适时间片。其出发点是在为每一门课程选择时间时,要考虑对后续课影响最小,如一位教师一学期讲两门课(相应有两个班级),选第一门课时间时,尽可能选第二门课这个班级在上别的课的时间,这样在选第二门课的时间时,其选择自由度不受第一门课的影响。如一个班级同时接受两位教师讲两门课,其考虑的出发点也同样。这样来选择时间,以后造成冲突的可能性大大减少。本文给出了安全决策调度算法的定量描述,为加快安全决策调度过程,在原始输入课元组时,把相同的教师及相同的班级的课元组放在一起,只要往下扫描几门课。根据这几门课便可进行决策,再以后的课全是无关联的。本文也给出了算法框图。经在IBM-PC机上运行,证明选择合适时间片是完全可行的。     

平行顺序生产的组合计算

本文从研究平行顺序移动方式的特点及其组合规律入手,引入组合算子(+)及其运算规则,讨论了(+)算子的运算性质。由此,可方便地解决在平行顺序移动生产方式下总生产期的计算及生产排序问题。给出了(+)算子进行实际计算的例子。     

具有禁用区间的平行机排序时间表长问题的全多项式近似方案

近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中。传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题。对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法。研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的。在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的。给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界。     

遗传算法在排课问题中的运用

遗传算法借鉴生物界自然选择和遗传机制,使用群体搜索技术,处理传统搜索方法难以解决的复杂的非线性问题.排课问题是一个多因素的优化决策问题,是组合规划中的典型问题,属于NP完全类问题.根据大学课表的特点,采用遗传算法,给出染色体编码和适应度函数,并采用了自适应的调整概率进行排课,数值试验证明了方法的有效性和可行性.     

An integrated DBP for streams with （m, k）-firm real-time guarantee

(m, k)-firm real-time or weakly hard real-time (WHRT) guarantee is becoming attractive as it closes the gap between hard and soft (or probabilistic) real-time guarantee, and enables finer granularity of real-time QoS through adjusting m and k. For multiple streams with (m, k)-firm constraint sharing a single server, an on-line priority assignment policy based on the most recent k-length history of each stream called distance based priority (DBP) has been proposed to assign priority. In case of priority equality among these head-of-queue instances, Earliest Deadline First (EDF) is used. Under the context of WHRT schedule theory, DBP is the most popular, gets much attention and has many applications due to its straightforward priority assignment policy and easy implementation. However, DBP combined with EDF cannot always provide good performance, mainly because the initial DBP does not underline the rich information on deadline met/missed distribution, specially streams in various failure states which will travel different distances to restore success states. Considering how to effectively restore the success state of each individual stream from a failure state, an integrated DBP utilizing deadline met/missed distribution is proposed in this paper. Simulation results validated the performance improvement of this proposal.     

谈新兴技术对本世纪图书馆事业的深远影响

自从利可里德（Licklidem J．C．R）于1965年出版他的《未来的图书馆》一书后，以电子计算机为代表的信息技术逐步发展，一些人对图书馆的未来表示悲观，“图书馆消亡论”开始常见于上世纪80年代及90年代初的各种图书馆学及情报学杂志，并被人为安排了图书馆的“消亡时间表”。最具代表性的人物乃属美国情报专家兰卡斯特（F．W．Lancaster）。他认为：“我们正在迅速地不可避免地走向无纸社会。”     

了解嚣官衰老时间表有助抗早衰

最近英国研究人员确认了人体一些器官的衰老退化时间表。     

时间表理论中LPT算法在装箱问题中的应用

本文利用二分搜索法和时间表理论中LPT算法求解装箱问题的近似最优解;给出了一个直观性算法,并研究这个算法的最坏情形,最后说明此算法在某些方面优于著名的FFD算法。     

时间表问题中的定额匹配算法

大学排课表是一个多因素优化决策问题。该文提出的最大定额匹配算法,给出了一大类课程的课表编排模型,定额匹配算法是图论中二分图最大匹配算法的推广（匹配常数Ｋ≥１）。清华大学的计算机自动排课表系统ＵＴＰＳ（ｕｎｉｖｅｒｓｉｔｙｔｉｍｅｔａｂｌｅｐｌａｎｎｉｎｇｓｙｓｔｅｍ）已使用１０年,该算法在计算机自动编排课表的过程中起到了重要作用。