Finding a feasible course schedule using Tabu search(3)

文章地址Finding a feasible course schedule using Tabu search翻译进度 [#] 介绍 [#] 问题描述 [#] 禁忌搜索技术 [#] 修改禁忌搜索 [ ] 数字化结果 [ ] 扩展 [ ] 结束语 上一篇链接 Adaptation of Tabu searchMany authors have formulated the course scheduling problem as an assignmentproblem [3,4,9,12]. Guidelines for adapting Tabu search to assignment problemshave been described in [12]; the same paper contains a description of the algorithmTAT1 which is an example of such an adaptation to a course scheduling problemwhere starting times have to be assigned to courses. For our timetabling problemwe cannot use the algorithm TAT1 since the number of courses and their length arenot known in advance.Let us however formulate our course scheduling problem as an assignment problemwhere each element from a set S of conflicting objects is assigned to exactly oneelement of a set P.The daily quantums of a static topic are fixed in advance. They induce coursesof given length. These courses are defined to be s-objects.     继续阅读
MXlwq's avatar
MXlwq 3月 27, 2016
 | 

禁忌搜索算法

启发式搜索算法与传统的方法Tabu Search是由美国科罗拉多州大学的Fred Glover教授在1977年左右提出来的,是一个用来跳出局部最优的搜寻方法。在解决最优问题上,一般区分为两种方式,一种是传统的方法,就是穷举法、贪婪法、分治法、动态规划等等;而另一种方法则是一些启发式搜索算法。     继续阅读
MXlwq's avatar
MXlwq 3月 17, 2016
 | 

Finding a feasible course schedule using Tabu search(2)

文章地址Finding a feasible course schedule using Tabu search翻译进度 [#] 介绍 [#] 问题描述 [#] 禁忌搜索技术 [ ] 修改禁忌搜索 [ ] 数字化结果 [ ] 扩展 [ ] 结束语 上一篇链接 Tabu search techniquesTabu search is a metaheuristic designed for getting a global optimum to a combinatorial optimization problem. It has been first suggested by Glover [lo] and independently by Hansen et al. [l 11 for a specific application, and later developed in a more general framework. A description of the method can be found in [6, 10]. Tabu search has already been efficiently adapted to a large collection of applications [6,11-14,16] We shall sketch here the basic ideas of the technique.An objective function f has to be minimized on a set X of feasible solutions. A neighborhood N(s) is defined for each solution s in X. The set X and the definition of the neighborhood induce a state-space graph G (which may by the way be infinite). Tabu search is basically an iterative procedure which starts from an initial feasible solution and tries to reach an optimal solution by moving step by step in the state-space graph G. Each step consists in first generating a collection V of solutions in the neighborhood N(s) of the current solution s, and then moving to the best solution s’ in V, even if f (s?> f (s). Let us write s’=s⊕m with the meaning that s’ is obtained by applying a modification m to s. The solutions consecutively visited in the iterative process induce an oriented path in G. Finding the best solution in V may sometimes be a nontrivial matter. It may be necessary to solve the optimization problem min(_f(si) 1 Si E V} by a heuristic procedure.A risk of cycling exists as soon as a solution s’ worse than s is accepted. In order to prevent cycling to some extent, modifications which would bring us back to a previously visited solution should be forbidden. But it may sometimes be useful to come back to an already visited solution and continue the search in another direction from there. This is realized in Tabu search by keeping a list T containing the last k modifications (k may be fixed or variable). Whenever a modification m is made for moving from s to s’, m is introduced in T and its reverse is considered as tabu.Deciding that some moves are tabu moves may be too absolute: it is shown in [6] that moves to solutions which have not been visited may be tabu. For this reason, it should be possible to cancel the tabu status of a move if it seems desirable to do so. This is realized as follows. Let s be the current solution and m a modification which we want to apply to s. A penalization a(s, m) and a threshold value A(s, m) are computed: if a(s, m)     继续阅读
MXlwq's avatar
MXlwq 3月 16, 2016
 | 

Finding a feasible course schedule using Tabu search(1)

文章地址Finding a feasible course schedule using Tabu search翻译进度 [#] 介绍 [#] 问题描述 [ ] 禁忌搜索技术 [ ] 修改禁忌搜索 [ ] 数字化结果 [ ] 扩展 [ ] 结束语 作者和期刊相关期刊:Discrete Applied MathematicsTHE JOURNAL OF COMBINATORIAL ALGORITHMS, INFORMATICS AND COMPUTATIONAL SCIENCES组合算法,信息与计算科学期刊     继续阅读
MXlwq's avatar
MXlwq 3月 12, 2016
 | 

DMDSS集成模型开发需求的灾难决策分类

文章地址CATEGORIZATION OF DISASTER DECISION SUPPORT NEEDS FOR THE DEVELOPMENT OF AN INTEGRATED MODEL FOR DMDSS翻译进度 [x] 引言 [x] 进行了决策支持系统的概述。 [x] 定义了一个特定的灾害管理决策支持系统 [x] 点明了在开发DMDSS中出现的问题。 [x] 概述了我们DMDSS开发和模型集成的方法。 [x] 对模块化子程序选择的概述。 [x] 描述的选择过程。 [x] 提出决策支持的概念需要。 [x] 提出了模块化子程序选择需求的分类方案。 [x] 用一个例子来支持需求分类方案。 [x] 实验结果 [x] 实验结论。 作者SOHAIL ASGHAR,DAMMINDA ALAHAKOON,LEONID CHURILOV 摘要The wide variety of disasters and the large number of activities involved have resulted in the demand for separate Decision Support System (DSS) models to manage different requirements. The modular approach to model management is to provide a framework in which to focus multidisciplinary research and model integration. A broader view of our approach is to provide the flexibility to organize and adapt a tailored DSS model (or existing modular subroutines) according to the dynamic needs of a disaster. For this purpose, the existing modular subroutines of DSS models are selected and integrated to produce a dynamic integrated model focussed on a given disaster scenario. In order to facilitate the effective integration of these subroutines, it is necessary to select the appropriate modular subroutine beforehand. Therefore, subroutine selection is an important preliminary step towards model integration in developing Disaster Management Decision Support Systems (DMDSS). The ability to identify a modular subroutine for a problem is an important feature before performing model integration. Generally, decision support needs are combined, and encapsulate different requirements of decision-making in the disaster management area. Categorization of decision support needs can provide the basis for such model selection to facilitate effective and efficient decision-making in disaster management. Therefore, our focus in this paper is on developing a methodology to help identify subroutines from existing DSS models developed for disaster management on the basis of needs categorization. The problem of the formulation and execution of such modular subroutines are not addressed here. Since the focus is on the selection of the modular subroutines from the existing DMDSS models on basis of a proposed needs classification scheme.     继续阅读
MXlwq's avatar
MXlwq 4月 30, 2015
 |