资源优化调度问题研究

2011年第31期科技冒向导<>高教论述<资源优化调度问题研究胡3(空军勤务学院后勤指挥系江苏徐州21000)[摘要]资源优化调度问题是 一个广泛存在的复杂系统问题.以物流配递和排课问题等的一奥资源优化调度的典型问题,由其难解性引起了较为广泛的关注。本文以排课问题为例,提出了基于不等式方法的多目标遗传算法解决方案,对排课问题的研究具有重要的现实意义。[关键词]资源优化调度问题;排课问题1.资源优化调度问题概述不等式特征。由于排课问题存在目标和约束的复杂性。相对于一般多资源优化调度问题是工程领域的一个普遍问题,在T程实践中，目标问题， 排课问题在处理约束函数时表现为更复杂的关联约束关资源的优化调度关系到整体的效率和效益.具有很高的研究和应用价系 ,进一步增加了排课问题的复朵度。因此,把排课问题作为这类资源值。资源优化调度般涉及的变量较多,属于带约束的多月标优化问优化调度问题的典 型例子具有一定的代表性。题,而物流配送等的- 类问题区别于-般的多目标优化问题,具有以3.排课问题概述排课问题是学校教务管理中最重要，也是最复杂的问题之一。课(1)这类资源优化调度问题是带约束的多月标优化向题并且这程 表编排主要分为两个部分, -是根据各专业、不同年级授课任务确些约東既包含常规约束，也包含动态约東.常规约束确定解的可行区定各班课程, 二是根据每周的课时数、课室进行课程表的编排.班级的城,动态约束则确定解的折中与妥协空间。课表由班主任或主管老师根据教学大纲进行编持,这个过程通过手工(2)这类资源优化调度问题在求解过程中,可行解不- -定是合理操作也可以完成。 教务管理部( 1的工作人员通过提前收集各校区,二的,最后寻求的更多是满意解。如在排课问题中,有一门课是一一周上两 级学院系的开课情况.然后统- -进行处理,确定哪此课是- -定要开次的,在解中.两次课刚好连在-一起,这也是不合理的。的,那些课叮以做机动处理.然后统- -安排学校的开课计划,再按照开(3)这类资瓯优化调度问题在应用遗传算法求解的过程中.其基课计划进行排课。 所以对于第二阶段的课程编排，涉及到的变量主要因存在唯.一性,X别于一般的遗传算法应用问题。如货物配送地点与包括时间 .教师，班级、课室.课程校区院系.课室类型,以及一些其货物需求量的组合，课程与教师班级的组合,这些都是唯一的。它特殊要求等要求。在课室和教师资源极大充分的条件下.学校的课(4)这类资源优化调度问题在资源的组合优化方而具有一-定的可程安排 叮以交由各院系进行，各院系直接统筹本院系的教师和课室资调整空间。因为这类问题涉及时间和人员等,所以在资源调度过界中，源， 进行统一调度 就可以完成，这样，排课的复杂性也就相对降低了。可以通过适当地增加或减少少量的时间或人员方面的资濒达到资源但是 .大多数情况下,由于学校招生规模的扩大,课室很多情况下都成的充分和有效利用.从而提高效率和效益。为排课问题中的紧缺资源.所以,争收课室资源的最大利用率就成为2.资源优化调动问题的描述排课问题的关键。这种情况下,学校资源的统安排通常是手I难以多目标优化问题(MOP)-般采用如下定义:很好地完成，需要协调各个内素.实现资源的优化配置。目前,在资源一般MOP由n个决策变量参数.k个日标雨数和m个约束条件组优化问题 t.本要采用的万法有贪婪算法，规划论和遗传算法。成,目标函數约束条件与决策变量满足-定的关系。 最优化问题如下:4.现有排课问题的解决方寨Minimize =(=()=()(...(x))在现行高校的排课问题上,主要有两种模式, -种是沿用全校性.(ax(.()+e...(.)-O的统-排课,另.种是分权排课统管理。 各个学校可以根据实际问其中，xx,而...x)eX题,采用不同的模式。如果学校规模比较小，可以考虑仝校性的统一排课方法如果学校规模比较大,涉及的学生班级.课程教师等因索比y=0rjx..*y.)eY这里,x表示决策变量,y表示目标向量,X表示决策向量x形成较多,而且有较多的约束条件.则可以考虑采用分权的模式进行排课。的决策空间,Y表示日标向量y形成的目标空间.约束条件e∞)≤0确全校性的统一排课 也就是我们前面讲到的由学校统- -管理的院系统一上.报教学计划.然后由教务管理部( ]统-安排教学任务和课种。而定决策向量的可行取俏范围。分权排课模式就是首先对学校有限的资源进行划分,根据院系的教学通常多目标优化问题的日标隔数具有线性或者非线性性质,优化规模分配一定的教学资源，然后由院系根据所分配的资源安排本院系函数是将决策向量X映射到日标向量y.记作FA- +A的课程,教务管理部1 ]可以随时查看排课情况。并进行统一调度。 这样物流配送 和排课等类资源优化满度问题作为多目标问题,在其 的好处 就是把问题化简,分而治之。特别是对于动态约束条件比较多定义中也包括了日标向量,决策向量和约束条件,这类资源优化调度的情况，这种排课模式是比较叮取的。在实际的排课过程中,这种系统问题是在多准则决策中寻求相互冲突的多月标闻的折衷与平衡，敏终虽然能实现分而治之的效果.但是实际君来，大部分学校采用此系统获得叫题的满意解。结合多日标优化问题的措述,对于由。个决策变进行排课时，由 于院系规模比较小.动态约束比较多.所以大部分的院量參数、个目标商数和m个约束条件组成。目标函数约束条件与决系实际 上:都是采用人工排课的方法实现。策变量满足- -定的 关系的资源优化调度问题, -般情况可以用以下的5.小结数学公式进行描述:本文在阐述物流配送，排课等-类资源优化调度问题的特点的基y-中(闲)≥0础上,结合多日标优化问题的描述,对这类资源优化调度问题作了-3.C(x)≤0般描述,并把相应的排课问题-般描述作 了介绍。在此基础上对现有中(中比1(:(...0”CGaxEflE.B...... .xeF。排课问题的解决方案进行综述,特别是广东省大部分高校所采用的排山)为目标函数向量C(x)为约束条件,，为决策向量,F为所有资课系统作 了比较详细的分析.为后面提出基于不等式方法的多目标遗源组合n的集合。相应地,在排课问题中,中()即为排课问题必须满足的多个月标，传算法的应用提供了现实依据。G()确定排课问题决策间量的叮行范围,x为决策向量,F为所有课程[参考文献]n的集合。[1]马永，基于遗传算法求解排课问题的研究州建电脑2008.排课问题是求约束条件C()确定的可行范围内满足月标函敷φ [2朝文件中国煤化工系统应用2008.()的排课方案,排课问题的描述充分体现了排课问题的多日标特性及[3]辛延4出版社,2006.YHCNMHG作者简介:胡丑(1986- -), 男,研究生学员,江苏省徐州市空军勤务学院研究生管理大队41队学员。32