关于大学课程表问题的研究

大学课程表问题可以表述为：如何为给定的一组课程编排一个时间表，以使得所有的学生选课要求都得到满足，并且这些课程所用的不同课时段数目最少。在本中我们首先证明了即使每位学生最多选两门课程，该问题仍然是NP-难解的，然后我们提出了求解该问题一般情形的一个启发式算法。     

求解课程表问题的分支定界算法

本通过对中学排课程表问题的特征分析，给出了基于分支定界法的优化算法，数值试验表明这是解决一般编排中学课程表问题的有效算法。     

基于层次分析法的课程表的模糊综合评价

建立了高校课程表的评价指标体系,在此基础上提出了基于层次分析法的课程表的模糊综合评价方法,并用方根法简化模糊评价的权重集求解过程.通过对具体课程表的模糊综合评价,验证了该方法是科学的、可行的.     

用整体思想求解数学问题的若干形式

整体思想是一种重要的解题思想,是思维深刻性的体现,根据问题的不同特点,可以展现出多种思考模式.本文介绍整体思想求解数学问题的若干形式.     

约束非线性l_1问题的光滑近似算法

针对约束非线性l_1问题不可微的特点,提出了一种光滑近似算法.该方法利用" "函数的光滑近似函数和罚函数技术将非线性l_1问题转化为无约束可微问题,并在适当的假设下,该算法是全局收敛的.初步的数值试验表明算法的有效性.     

约束非线性ι1问题的光滑近似算法

针对约束非线性ι1问题不可微的特点,提出了一种光滑近似算法.该方法利用“ “函数的光滑近似函数和罚函数技术将非线性ι1问题转化为无约束可微问题,并在适当的假设下,该算法是全局收敛的.初步的数值试验表明算法的有效性.     

调剂问题的Vague指派方法研究

调剂工作是硕士研究生招生录取过程中一项非常重要的工作.论文以硕士研究生调剂工作为例,通过分析基本特征,将其转化为指派问题进行研究.并借助于Vague集思想,运用面试投票的方法获得效益矩阵.根据评价者的不同偏好特征采用记分函数将Vague值转化为实数,得到了实数满意度矩阵.进而不仅实现了学生和录取单位的共赢,也实现了资源的优化配置.该方法一方面为此类问题的解决提供了一种有效途径,另一方面也在理论上找到了Vague指派的一般步骤,通过数据计算保证了该方法在问题解决上的有效性和可行性.     

求解无容量设施选址问题的拉格朗日蝙蝠算法

无容量设施选址问题(Uncapacitated Facility Location Problem,UFLP)是一类经典的组合优化问题,被证明是一种NP-hard问题,易于描述却难于求解.首先根据UFLP的数学模型及其具体特征,重新设计了蝙蝠算法的操作算子,给出了求解UFLP的蝙蝠算法.其次构建出三种可行化方法,并将其与求解UFLP的蝙蝠算法和拉格朗日松弛算法相结合,设计了求解该问题的拉格朗日蝙蝠算法.最后通过仿真实例和与其他算法进行比较的方式,验证了该混合算法用来求解UFLP的可行性,是解决离散型问题的一种有效方式.     

一种调查敏感性问题的随机化方法

根据已有的调查定性敏感性问题的方法,本文提出了一种新的随机化调查方法,该方法得到的估计量在一定条件下具有较小的方差.     

对数学文化课程的若干思考

在大学开设数学文化选修课已经逐步成为人们的共识,但在开设该课程的过程中还存在一系列的问题.本文根据多年的教学实践研究了数学文化的内涵,提出了数学文化课程的一种教学理念,分析了数学文化课程中存在的若干问题,并探讨了解决这些问题的设想.     

周期列车运行图的多目标模型及基于Job-shop的遗传算法研究

计算机编制客运专线周期列车运行图问题已成为国内外研究的热点问题之一.在充分研究国内外周期与非周期列车运行图的规划理论与方法的基础上,构建了我国客运专线周期列车运行图的多目标模型,并将之转化为具有优先级结构的单目标模型;然后结合运行图的数学本质与周期性,设计了基于Job-shop的遗传算法,弥补了国外基于PESP理论所开发的周期列车运行图的算法不足.最后结合京津客运专线实例来验证算法的有效性.     

Metaheuristics for High School Timetabling

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simu lated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu search based on temporary problem relaxations both outperform simulated annealing and handmade timetables.     

A polynomial-time algorithm to find an equitable home-away assignment

We propose a polynomial-time algorithm to find an equitable home-away assignment for a given timetable of a round-robin tournament. Our results give an answer to a problem raised by Elf et al. (Oper. Res. Lett. 31 (2003) 343), which concerns the computational complexity of the break minimization problem in sports timetabling.     

Conference Seminar Timetabling

Participants at a conference held in 1985 were asked to select seminars that they wished to attend, before the schedule of seminars was constructed. The conference organizers were then faced with the problem of finding a timetable that would allow participants to attend the seminars they had chosen. This interesting combinatorial optimization problem is investigated here. A heuristic method, incorporating an annealing algorithm, is developed to help the organizers timetable similar conferences in the future.     

利用平面上的黄金分割法求全局最优解

给出了无约束全局最优问题的一种解法 ,该方法是一维搜索中的 0 .61 8法的推广 ,不仅使其适用范围由一维扩展到平面上 ,并且将原方法只适用于单峰函数的局部搜索改进为可适用于多峰函数的全局最优解的搜索 .给出了收敛性证明 .本法突出的优点在于 :适用性强、算法简单、可以在任意精度内寻得最优解并且克服了以往直接解法所共有的要求大量计算机内存的缺点 .仿真结果表明算法是有效的 .     

连锁—遗传算法中的一种启发式方法

１引言遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ,简称ＧＡ）是由美国密执安大学教授ＪｏｈｎＨｏｌｌａｎｄ提出的,其依据为达尔文的进化论和盂德尔的遗传学说．该算法效法自然界中各物种的进化过程,是一种随机搜索算法,广泛应用于解决各种优化问题．２生物遗传学中的连锁生物遗传学中的连锁现象是Ｂａｔｅｓｏｎ和Ｐｕｎｎｅｔｔ在１９０６年发现的,他们在研究香豌豆的两对性状的遗传时,观察到同一亲体遗传来的基因较多地联在一起,这就是基因的连锁（ｌｉｎｋａｇｅ）现象．这里应给玉米的例子来说明遗传学上的连锁现象．设基…     

车辆路径问题的改进遗传算法

提出一种基于遗传算法的求解车辆路径问题的新算法,避免传统遗传算法处理不可行约束条件中惩罚项系数选取不当所出现的问题.同时,通过现实例子分析该算法的优劣性,实验结果表明该算法是一种有效的算法.     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

An alternative approach for unbalanced assignment problem via genetic algorithm

This paper presents an alternative approach using genetic algorithm to a new variant of the unbalanced assignment problem that dealing with an additional constraint on the maximum number of jobs that can be assigned to some agent(s). In this approach, genetic algorithm is also improved by introducing newly proposed initialization, crossover and mutation in such a way that the developed algorithm is capable to assign optimally all the jobs to agents. Computational results with comparative performance of the algorithm are reported for four test problems.