论文部分内容阅读
排课问题是一个涉及多因素约束的、多目标的、结构复杂的典型组合优化问题,并且已被证明为一个NP完全类,其问题求解的时间复杂度呈指数函数增长。分布式环境下的排课所面临的突出问题是:排课信息分布、排课人员分布、排课的规则知识难以动态获取与有效组织。因此,需要探索运用新的软件技术Agent来降低分布式环境下排课问题的复杂度。
基于移动多Agent的远程排课模型与传统的基于C/S方式的排课模型相比,最大的区别在于计算实体不再是静止和被动的,而是可以自主迁移计算的Agent。通过将排课任务封装在Agent内部,并将其派遣到多个地理位置分散的远程主机上,再由多个Agent的交互和协作共同完成排课。该模型的主要优点有:一是能以最小的代价将排课系统集成进全院教务管理信息系统中;二是能利用多Agent的协商合作的机制来加快教务秘书与任课教师之间的沟通;三是可以利用Agent积极地扮演排课人员的角色。
基于移动多Agent的排课算法针对部分属于人文范畴的排课问题,利用Agent来模拟人类的排课过程,能够按照一定的分配策略选择上课的教师、时间和教室,通过Agent的反复协商,解决时间与空间的冲突问题,最终排出满足所有基本硬约束条件和大致满足软约束条件的课表。由于多Agent能够更好地模拟人工排课情况,扩展形形色色的约束条件与偏好要求,而且在多Agent的合作过程中不需人工干预,能察觉到执行环境的改变而自主性地响应改变,因此,可以简化排课算法的计算步骤,降低系统复杂性,同时也减少了程序开发工作量。
采用流行的移动Agent开发工具IBMAglets初步实现基于移动多Agent的排课系统MMACTS。该系统能快速实现与现有的信息系统的集成,操作界面简单,具有现有排课系统不具备的功能,既能够编制独具特色的日期课表,又可编排每周固定的周课表,表现出良好的伸缩性与灵活性。对系统进行模拟测试的结果表明,在一定的排课规模下,排课算法的时间复杂度呈线性增长而不是呈指数增长。