Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem

We consider the university course timetabling problem, which is one of the most studied problems in educational timetabling. In particular, we focus our attention on the formulation known as the curriculum-based course timetabling problem (CB-CTT), which has been tackled by many researchers and for which there are many available benchmarks.The contribution of this paper is twofold. First, we propose an effective and robust single-stage simulated annealing method for solving the problem. Second, we design and apply an extensive and statistically-principled methodology for the parameter tuning procedure. The outcome of this analysis is a methodology for modeling the relationship between search method parameters and instance features that allows us to set the parameters for unseen instances on the basis of a simple inspection of the instance itself. Using this methodology, our algorithm, despite its apparent simplicity, has been able to achieve high quality results on a set of popular benchmarks.A final contribution of the paper is a novel set of real-world instances, which could be used as a benchmark for future comparison.     

A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem

This paper describes a timetabling problem at universities, where a master course timetable is given extrinsically and conflicts due to students' course enrollment do not need to be considered. A solver for the problem, which integrates both teacher assignment and course scheduling, is described. An initial solution is obtained by a mathematical programming approach based on Lagrangian relaxation. This solution is further improved by a simulated annealing algorithm. The proposed method has been tested on instances from a university in Indonesia, as well as on several randomly generated datasets, and the corresponding computational results are reported.     

A new lower bound for curriculum-based course timetabling

In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (CTT), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing up the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones).     

Algorithm selection and instance space analysis for curriculum-based course timetabling

Journal of Scheduling - We propose an algorithm selection approach and an instance space analysis for the well-known curriculum-based course timetabling problem (CB-CTT), which is an important...     

Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem

The post-enrolment course timetabling (PE-CTT) is one of the most studied timetabling problems, for which many instances and results are available. In this work we design a metaheuristic approach based on simulated annealing to solve the PE-CTT. We consider all the different variants of the problem that have been proposed in the literature and we perform a comprehensive experimental analysis on all the available public instances. The outcome is that our solver, properly engineered and tuned, performs very well on all cases, providing the new best known results on many instances and state-of-the-art values for the others.     

Solution approaches to the course timetabling problem

University course timetabling is one of the most important administrative activities that take place in all academic institutions. In this work, we go over the main points of recent papers on the timetabling problem. We concentrate on university timetabling and introduce hard and soft constraints as well as most currently used objective functions. We also discuss some solution methods that have been applied by researchers. Finally, we raise more questions to be explored in future studies. We hope the directions lead to new researches that cover all aspects of the problem and result in high-quality timetables.     

A survey of approaches for university course timetabling problem

Scheduling is one of the problems which so many researches have been conducted on it over the years. The university course timetabling problem which is an NP-hard problem is a type of scheduling problem. Timetabling process must be done for each semester frequently, which is an exhausting and time consuming task. The allocation of whole of events in timeslots and rooms performs by the university course timetabling process considering the list of hard and soft constraints presented in one semester, so that no conflict is created in such allocations. In the university course timetabling problem (UCTTP), the hard constraints should not be violated under any conditions; soft constraints also should not be violated as much as possible. The aim of the present paper is to analyze available approaches in the study of university course timetabling problems, including operational researches, metaheuristic methods and intelligent novel methods; also the distributed multi agent systems based approach (Cooperative Search method) is investigated due to its scalability which enables the timetabling of common events between departments. In addition, in this work a complete introduction of reliable datasets has been given to test and evaluation of the structure of considered algorithms.     

A simulated annealing heuristic for the open location-routing problem

This paper introduces the open location-routing problem (OLRP) that is a variant of the capacitated location-routing problem (CLRP). OLRP is motivated from the rise in contracting with third-party logistic (TPL) companies and is different from CLRP in that vehicles do not return to the distribution center after servicing all customers. The goal of OLRP is to minimize the total cost, consisting of facility operation costs, vehicle fixed costs, and traveling costs. We propose a simulated annealing (SA)-based heuristic for solving OLRP, which is tested on OLRP instances that have been adopted from three sets of well-known CLRP benchmark instances with up to 318 customers and 4 potential depots. The computational results indicate that the proposed heuristic efficiently solves OLRP.     

A simulated annealing algorithm for dynamic layout problem

Increased level of volatility in today's manufacturing world demanded new approaches for modelling and solving many of its well-known problems like the facility layout problem. Over a decade ago Rosenblatt published a key paper on modelling and solving dynamic version of the facility layout problems. Since then, various other researchers proposed new and improved models and algorithms to solve the problem. Balakrishnan and Cheng have recently published a comprehensive review of the literature about this subject. The problem was defined as a complex combinatorial optimisation problem. The efficiency of SA in solving combinatorial optimisation problems is very well known. However, it has recently not been applied to DLP based on the review of the available literature. In this research paper a SA-based procedure for DLP is developed and results for test problems are reported.

Scope and purpose

One of the characteristic of today's manufacturing environments is volatility. Under a volatile environment (or dynamic manufacturing environment) demand is not stable. To operate efficiently under such environments facilities must be adaptive to changing demand conditions. This requires solution of the dynamic layout problem (DLP). DLP is a complex combinatorial optimisation problem for which optimal solutions can be found for small size problems. This research paper makes use of a SA algorithm to solve the DLP. Simulated annealing (SA) is a well-established stochastic neighbourhood search technique. It has a potential to solve complex combinatorial optimisation problems. The paper presents in detail how to apply SA to solve DLP and an extensive computational study. The computational study shows that SA is quite effective in solving dynamic layout problems.     

Flow-shop调度问题的自适应模拟退火算法

为求得一个强NP-难问题——flow-shop调度问题的最优解或近优解, 提出一种自适应模拟退火算法. 本算法采用一种基于区段特性的特殊邻域结构、简便的目标函数计算方法和自适应退火策略. 通过Flow-shop调度问题的基准测试问题的实验, 数值结果证实了该方法的有效性.     

求解VRPSDP问题的改进模拟退火遗传算法

配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题,设计了一种改进的模拟退火遗传算法ISAGA,采用非零自然数编码机制和弱可行解到强可行解的解码机制,将3PM交叉算子和退火选择相结合,形成贪心3PM交叉算子,引进insert 、swap和2-opt分别对解进行迭代优化,并将模拟退火算法和遗传算法巧妙地结合,使得遗传算法在前期发挥着全局搜索的强大功能;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证,ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。     

A simulated annealing heuristic for the dynamic layout problem with budget constraint

Facility layout problem has been extensively studied in the literature because the total material handling cost can be a significant portion in the operational costs for a company and in the manufacturing cost of a product. Today’s severe global competition, rapid changes in technology and shortening life cycle of products force companies to evaluate and modify their facility layout in a periodic fashion. This type of layout problems is categorized as the dynamic facility layout problem (DFLP). As a realistic dimension of the problem, one has to consider also the limited budget to cover the cost of changing the layout. In this study, we propose a simulated annealing heuristic for the DFLP with budget constraint, and show the effectiveness of this heuristic on a set of numerical experiments.     

An ILP based heuristic for a generalization of the post-enrollment course timetabling problem

We consider a new timetabling problem arising from a real-world application in a private university in Buenos Aires, Argentina. In this paper we describe the problem in detail, which generalizes the Post-Enrollment Course Timetabling Problem (PECTP), propose an ILP model and a heuristic approach based on this formulation. This algorithm has been implemented and tested on instances obtained from real data, showing that the approach is feasible in practice and produces good quality solutions.     

混合模拟退火及分散搜索优化过道布置问题

针对过道布置问题的求解复杂性,提出了一种混合模拟退火及分散搜索算法。该算法通过引入模拟退火操作进一步优化参考集中的解,以提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集,扩大了搜索范围,避免算法陷入局部最优。同时采用动态参考集更新方法,及时替换参考集中质量或多样性较差的解,加快算法的收敛速度,并改进子集产生方法,避免产生重复的解,从而提高算法的求解效率。应用所提算法对24个不同规模的测试问题进行验算与对比,结果表明所提算法的求解质量与平稳性均优于基本模拟退火算法和分散搜索算法,且较已有的4种方法更具求解优势。     

A simulated annealing heuristic for the capacitated location routing problem

The location routing problem (LRP) is a relatively new research direction within location analysis that takes into account vehicle routing aspects. The goal of LRP is to solve a facility location problem and a vehicle routing problem simultaneously. We propose a simulated annealing (SA) based heuristic for solving the LRP. The proposed SALRP heuristic is tested on three sets of well-known benchmark instances and the results are compared with other heuristics in the literature. The computational study indicates that the proposed SALRP heuristic is competitive with other well-known algorithms.     

A simple simulated annealing algorithm for the maximum clique problem

Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.     

求解旅行商问题的波动温控模拟退火算法

针对传统模拟退火算法在求解旅行商问题时运行时间长,易陷入局部最优,且随着问题规模的增大缺陷愈发明显的问题,对传统算法的内循环过程和退火机制进行改进,使得内循环的搜索强度根据温度的变化自适应调整,同时提出波动温度控制机制,使得算法在保持温度幅值递减的总趋势下实现多次升温过程,增强求解效果,缩短求解时间,并通过TSPLIB数据库提供的大量实例得以验证.     

Mathematical model and simulated annealing algorithm for Chinese high school timetabling problems under the new curriculum innovation

As the first attempt,this paper proposes a model for the Chinese high school timetabling problems(CHSTPs)under the new curriculum innovation which was launched in 2011 by the Chine6e government.Aooording 10 the new our riculum innovation,students in high school can choose subjects that they are interested in instead of being forced to select one of the two study directions,namely,Science and Liberal Arts.Meanwhile,they also need to attend compulsory subjects as traditions.CHSTPs are student-oriented and involve more student constraints that make them more complex than the typi-cal"Class-Teacher model",in which the element"Teacher"is the primary constraint.In this paper,we first describe in detail the mathematical model of CHSTPs and then design a new two-part representation for the candidate solution.Based on the new representation,we adopt a two-phase simulated annealing(SA)algorithm to solve CHSTPs.A total number of 45 synthetic instances with different amounts of classes,teachers,and levels of student constraints are generated and used to ilustrate the characteristics of the CHSTP model and the effectiveness of the designed representation and algorithm.Finally,we apply the proposed model,the designed two-part representation and the two-phase SA on10 real high schools.     

应用遗传模拟退火算法实现资源受限项目调度

针对以最小化项目工期为目标的资源受限项目调度问题（RCPSP）,提出将模拟退火算法融合到遗传算法中,以改善遗传算法局部搜索性能,增强进化能力的遗传模拟退火算法——RCPSPGSA。在每次进化迭代过程中,下一代种群的个体需经过模拟退火算法改进,并通过在每次迭代结束前进行降温操作保证遗传算法和模拟退火算法具有相同的收敛方向和速度。算法在RCPSP标准测试问题库PSPLIB上进行数值仿真实验,并采用正交实验分析法解决参数选择问题。实验结果证明选择的参数组合具有突出的性能,RCPSPGSA是求解RCPSP的有效算法。     

解决车辆路径问题的混合模拟退火算法

构造了车辆路径问题的双目标数学模型,据此提出了混合模拟退火算法.该算法主要将模拟退火算法和2-opt优化算法有机地融合,从而使混合后的算法不但具有这两种算法的优点,而且还克服了他们相应的缺点.针对车辆路径问题,重点阐述了混合模拟退火算法的设计思路.实验结果表明,混合模拟退火算法不仅可以取得很好的计算结果,而且还具有收敛速度快等优点.