排课程序时间片选择的安全决策调度算法
DOI:
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


The Safety Decision-Making Scheduling Algorithm of Selecting the Time Slice in Timetable Problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    To select a suitable time in the timetable of the university is in nature how to find a common free time set of classrooms, teachers and classes. In 1975 Itai and Shamir proved that the timetable problem also is a NP-Complete problem. There had been a lot of heated arguments among many scholars until then. We can divide the timetable problem into two layers to solve. At first we should select a suitable time slice, and then according to the time slice we proceed to schedule the classrooms. But classroom-schedulings are greatly different in various universities. Is this paper we will particularly deal with problem about how to select a suitable time-slice according to the safety decision-making principle. When we select a time slice for every course, we must consider the minimum influence upon successive courses. If a teacher will teach two courses which correspond two classes in a semester, when we select the time slice of the first course, we should try our best to select the time slice when the second class already has another course. In such a case when we select the time slice of the second course, the freedom of the selection would not be hindered by the first selection. If a class has two courses taught by two teachers in a semester, we must consider the problem in the similar way. As we select the slice in such a way, the possibility of collision would greatly decrease. Here we present the quantified description of the safety decision-making scheduling algorithm. In order to speed up scheuling process, when we input the course tuples, we put the course tuples with the same teacher and the same class together. We should only scan downward several courses, and then we can make our decision accordingly. Other courses are irrelevant In this paper we draw the algorithm flow-chart. The program has been run in the IBM-PC. It has turned out that to select a suitable time slice is fully probable.

    参考文献
    相似文献
    引证文献
引用本文

顾立尧,邓桂英.排课程序时间片选择的安全决策调度算法[J].上海理工大学学报,1986,(3).

复制
分享
相关视频

文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码