Optimization Techniques in University Timetabling Problem:Constraints,Methodologies,Benchmarks,and Open Issues

University timetabling problems are a yearly challenging task and are faced repeatedly each semester.The problems are considered nonpolynomial time(NP)and combinatorial optimization problems(COP),which means that they can be solved through optimization algorithms to produce the aspired optimal timetable.Several techniques have been used to solve university timetabling problems,and most of them use optimization techniques.This paper provides a comprehensive review of the most recent studies dealing with concepts,methodologies,optimization,benchmarks,and open issues of university timetabling problems.The comprehensive review starts by presenting the essence of university timetabling as NP-COP,defining and clarifying the two formed classes of university timetabling:University Course Timetabling and University Examination Timetabling,illustrating the adopted algorithms for solving such a problem,elaborating the university timetabling constraints to be considered achieving the optimal timetable,and explaining how to analyze and measure the performance of the optimization algorithms by demonstrating the commonly used benchmark datasets for the evaluation.It is noted that meta-heuristic methodologies are widely used in the literature.Additionally,recently,multi-objective optimization has been increasingly used in solving such a problem that can identify robust university timetabling solutions.Finally,trends and future directions in university timetabling problems are provided.This paper provides good information for students,researchers,and specialists interested in this area of research.The challenges and possibilities for future research prospects are also explored.

Transformer-Based Macroscopic Regulation for High-Speed Railway Timetable Rescheduling

Unexpected delays in train operations can cause a cascade of negative consequences in a high-speed railway system.In such cases,train timetables need to be rescheduled.However,timely and efficient train timetable rescheduling is still a challenging problem due to its modeling difficulties and low optimization efficiency.This paper presents a Transformer-based macroscopic regulation approach which consists of two stages including Transformer-based modeling and policy-based decisionmaking.Firstly,the relationship between various train schedules and operations is described by creating a macroscopic model with the Transformer,providing the better understanding of overall operation in the high-speed railway system.Then,a policy-based approach is used to solve a continuous decision problem after macro-modeling for fast convergence.Extensive experiments on various delay scenarios are conducted.The results demonstrate the effectiveness of the proposed method in comparison to other popular methods.

Last train timetable optimization for metro network to maximize the passenger accessibility over the end-of-service period

Purpose-This study aims to improve the passenger accessibility of passenger demands in the end-ofoperation period.Design/methodology/approach-A mixed integer nonlinear programming model for last train timetable optimization of the metro was proposed considering the constraints such as the maximum headway,the minimum headway and the latest end-of-operation time.The objective of the model is to maximize the number of reachable passengers in the end-of-operation period.A solution method based on a preset train service is proposed,which significantly reduces the variables of deciding train services in the original model and reformulates it into a mixed integer linear programming model.Findings-The results of the case study of Wuhan Metro show that the solution method can obtain highquality solutions in a shorter time;and the shorter the time interval of passenger flow data,the more obvious the advantage of solution speed;after optimization,the number of passengers reaching the destination among the passengers who need to take the last train during the end-of-operation period can be increased by 10%.Originality/value-Existing research results only consider the passengers who take the last train.Compared with previous research,considering the overall passenger demand during the end-of-operation period can make more passengers arrive at their destination.Appropriately delaying the end-of-operation time can increase the proportion of passengers who can reach the destination in the metro network,but due to the decrease in passenger demand,postponing the end-of-operation time has a bottleneck in increasing the proportion of passengers who can reach the destination.

A train timetable rescheduling approach based on multi-train tracking optimization of high-speed railways

Purpose–This paper aims to propose a train timetable rescheduling(TTR)approach from the perspective of multi-train tracking optimization based on the mutual spatiotemporal information in the high-speed railway signaling system.Design/methodology/approach–Firstly,a single-train trajectory optimization(STTO)model is constructed based on train dynamics and operating conditions.The train kinematics parameters,including acceleration,speed and time at each position,are calculated to predict the arrival times in the train timetable.A STTO algorithm is developed to optimize a single-train time-efficient driving strategy.Then,a TTR approach based on multi-train tracking optimization(TTR-MTTO)is proposed with mutual information.The constraints of temporary speed restriction(TSR)and end of authority are decoupled to calculate the tracking trajectory of the backward tracking train.The multi-train trajectories at each position are optimized to generate a timeefficient train timetable.Findings–The numerical experiment is performed on the Beijing-Tianjin high-speed railway line and CR400AF.The STTO algorithm predicts the train’s planned arrival time to calculate the total train delay(TTD).As for the TSR scenario,the proposed TTR-MTTO can reduce TTD by 60.60%compared with the traditional TTR approach with dispatchers’experience.Moreover,TTR-MTTO can optimize a time-efficient train timetable to help dispatchers reschedule trains more reasonably.Originality/value–With the cooperative relationship and mutual information between train rescheduling and control,the proposed TTR-MTTO approach can automatically generate a time-efficient train timetable to reduce the total train delay and the work intensity of dispatchers.

High-Speed Railway Train Timetable Conflict Prediction Based on Fuzzy Temporal Knowledge Reasoning

Trains are prone to delays and deviations from train operation plans during their operation because of internal or external disturbances. Delays may develop into operational conflicts between adjacent trains as a result of delay propagation, which may disturb the arrangement of the train operation plan and threaten the operational safety of trains. Therefore, reliable conflict prediction results can be valuable references for dispatchers in making more efficient train operation adjustments when conflicts occur. In contrast to the traditional approach to conflict prediction that involves introducing random disturbances, this study addresses the issue of the fuzzification of time intervals in a train timetable based on historical statistics and the modeling of a high-speed railway train timetable based on the concept of a timed Petri net. To measure conflict prediction results more comprehensively, we divided conflicts into potential conflicts and certain conflicts and defined the judgment conditions for both. Two evaluation indexes, one for the deviation of a single train and one for the possibility of conflicts between adjacent train operations, were developed using a formalized computation method. Based on the temporal fuzzy reasoning method, with some adjustment, a new conflict prediction method is proposed, and the results of a simulation example for two scenarios are presented. The results prove that conflict prediction after fuzzy processing of the time intervals of a train timetable is more reliable and practical and can provide helpful information for use in train operation adjustment, train timetable improvement, and other purposes.

Combined Timetabling Procedure and Complete Local Search for No-Wait Job Shop Scheduling with Total Tardiness

The strong non-deterministic polynomial-hard( NP-hard)character of job shop scheduling problem( JSSP) has been acknowledged widely and it becomes stronger when attaches the nowait constraint,which widely exists in many production processes,such as chemistry process, metallurgical process. However,compared with the massive research on traditional job shop problem,little attention has been paid on the no-wait constraint.Therefore,in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems,in traditional frame work. A new efficient combined non-order timetabling method,coordinated with objective of total tardiness,is proposed for the timetabling problems. As for the sequencing one,we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms.Computational experiments showed that our proposed algorithm performed both effectively and efficiently.

COMMENTS ON THE THERAPEUTIC TIMETABLE OF ISCHEMIC APOPLEXY AND SUPER-EARLY INTERVENTION OF ACUPUNCTURE

According to the pathological process of ischemic apoplexy, which involves its onset and development, this paper expounds the great significance of adopting various active and effective measures within the therapeutic timetable for favorable prognosis and improvement of apoplexy. The author’s viewpoints differ from the conventional thinking towards the management of apoplexy, stressing super early intervention with acupuncture.

新的低成本钛合金——TIMETAL 62S

水流携带的固体磨粒的碰撞引起的水力磨蚀可导致材料表面损坏，为了改善磨蚀部件的设计，很多水力机械制造厂主要依靠试验和经验数据来预估有可能由靡起的损坏，确定技术检查间隔，估计部件的耐磨强度。本文介绍的数值分析法可以使人更尽地了解磨蚀机理，并了一种改善机器在磨蚀环境中运行的设计方法。

A Multiple-Neighborhood-Based Parallel Composite Local Search Algorithm for Timetable Problem

This paper presents a parallel composite local search algorithm based on multiple search neighborhoods to solve a special kind of timetable problem. The new algorithm can also effectively solve those problems that can be solved by general local search algorithms. Experimental results show that the new algorithm can generate better solutions than general local search algorithms.

A simulation-based optimization approach for passenger train timetabling with periodic track maintenance and stops for praying

This paper presents two optimization methods for solving the passenger train timetabling problem to minimize the total delay time in the single track railway networks. The goal of the train timetable problem is to determine departure and arrival times to or from each station in order to prevent collisions between trains and effective utilization of resources. The two proposed methods are based on integration of a simulation and an optimization method to simulate train traffic flow and generate near optimal train timetable under realistic con- straints including stops for track maintenance and praying. The first proposed method integrates a cellular automata （CA） simulation model with genetic algorithm optimiza- tion method. In the second proposed approach, a CA simulation model combines with dynamically dimensioned search optimization method. The proposed models are applied to hypothetical case study to demonstrate the merit of them. The Islamic Republic of Iran Railways （IRIR） data and regulations have been used to optimize train timetable. The results show the first method is more effi- cient than the second method to obtain near optimal train timetabling.

An Enhanced Particle Swarm Optimization for ITC2021 Sports Timetabling

Timetabling problem is among the most difficult operational tasks and is an important step in raising industrial productivity,capability,and capacity.Such tasks are usually tackled using metaheuristics techniques that provide an intelligent way of suggesting solutions or decision-making.Swarm intelligence techniques including Particle Swarm Optimization(PSO)have proved to be effective examples.Different recent experiments showed that the PSO algorithm is reliable for timetabling in many applications such as educational and personnel timetabling,machine scheduling,etc.However,having an optimal solution is extremely challenging but having a sub-optimal solution using heuristics or metaheuristics is guaranteed.This research paper seeks the enhancement of the PSO algorithm for an efficient timetabling task.This algorithm aims at generating a feasible timetable within a reasonable time.This enhanced version is a hybrid dynamic adaptive PSO algorithm that is tested on a round-robin tournament known as ITC2021 which is dedicated to sports timetabling.The competition includes several soft and hard constraints to be satisfied in order to build a feasible or sub-optimal timetable.It consists of three categories of complexities,namely early,test,and middle instances.Results showed that the proposed dynamic adaptive PSO has obtained feasible timetables for almost all of the instances.The feasibility is measured by minimizing the violation of hard constraints to zero.The performance of the dynamic adaptive PSO is evaluated by the consumed computational time to produce a solution of feasible timetable,consistency,and robustness.The dynamic adaptive PSO showed a robust and consistent performance in producing a diversity of timetables in a reasonable computational time.

基于关系着色图的Timetabling算法研究及其应用

考试自动安排系统在高校教务管理中处于重要位置,也是一个难题。提出一种基于关系着色图RCC(Relationship Colo-ring Chart)的Timetabling算法,探讨了该算法在考试时间安排中的应用,开发了某高校业余大学考试自动安排系统,并解决了较大数量学生补考的复杂安排问题。

Pareto-Based Complete Local Search and Combined Timetabling for Multi-objective Job Shop Scheduling Problem with No-Wait Constraint

Job shop scheduling has become the basis and core of advanced manufacturing technology. Various differences exist between academic research and practical production. The majority of previous researches on job shop scheduling problem (JSSP)describe the basic production environment, which have a single objective and limited constraints. However,a practical process of production is characterized by having multiple objectives,no-wait constraint,and limited storage. Thus this research focused on multiobjective,no-wait JSSP. To analyze the problem,it was further divided into two sub-problems, namely, sequencing and timetabling. Hybrid non-order strategy and modified complete local search with memory were used to solve each problem individually. A Pareto-based strategy for performing fitness assessment was presented in this study. Various experiments on benchmark problems proved the feasibility and effectiveness of the proposed algorithm.

Timetabling optimization of classrooms and self-study rooms in university teaching buildings based on the building controls virtual test bed platform considering energy efficiency

The energy consumption of a teaching building can be effectively reduced by timetable optimization.However,in most studies that explore methods to reduce building energy consumption by course timetable optimization,self-study activities are not considered.In this study,an MATLAB-EnergyPlus joint simulation model was constructed based on the Building Controls Virtual Test Bed platform to reduce building energy consumption by optimizing the course schedule and opening strategy of self-study rooms in a holistic way.The following results were obtained by taking a university in Xi’an as an example:(1)The energy saving percentages obtained by timetabling optimization during the heating season examination week,heating season non-examination week,cooling season examination week,and cooling season non-examination week are 35%,29.4%,13.4%,and 13.4%,respectively.(2)Regarding the temporal arrangement,most courses are scheduled in the morning during the cooling season and afternoon during the heating season.Regarding the spatial arrangement,most courses are arranged in the central section of the middle floors of the building.(3)During the heating season,the additional building energy consumption incurred by the opening of self-study rooms decreases when duty heating temperature increases.

考虑Pareto最优的列车运行图与维修天窗协调优化

列车运行图与维修天窗之间的冲突始终无法避免,且维修天窗开设时间的长短显著影响列车总运行时间。针对此问题,综合考虑维修天窗对列车运行造成的限速约束、车站到发线数量约束等,建立列车总运行时间最小,以及维修天窗实际开设时长与理想时长总偏差最小的双目标混合整数规划模型;对困难约束设置中间辅助变量将模型线性化以提高求解效率,并设计约束转换算法求解双目标模型的Pareto最优;微观化处理铁路线,将站内资源和站间资源细化为一系列行车资源单元,得到更加符合实际旅客运输需求的运行图。以某地区铁路线夜间开行列车及维修天窗开设计划为研究背景,调用商业软件求解双目标函数模型的Pareto最优,并对双目标模型的最小支配解和最优支配解进行对比分析;针对最优支配解下的列车进入、离开行车资源单元的时间、停站作业时间及维修天窗的开始时间及开设时长,绘制列车运行图。求解结果表明:模型在满足维修天窗最小开设时长的同时,能够兼顾列车运行总时间最小和维修天窗开设时长更充裕。基于最优支配解绘制的列车运行图表明:微观路网下的列车运行时刻表优化结果更符合实际旅客运输生产作业需要。研究结果可为铁路运营管理部门进一步优化列车运行图编制与维修天窗开设提供参考。

前继列车晚点条件下换乘客流的接续方案优化

针对列车运行受到干扰下运行图调整问题,对前继列车晚点条件下换乘客流的接续方案进行研究,将换乘客流和在车客流影响最小化作为优化目标对列车运行图进行相应调整.在前继列车晚点条件下,假定换乘客流既可以换乘到原接续列车,也可以选择其他符合换乘条件的列车,建立所有列车上的旅客延误时间最小和换乘失败旅客数量最少的多目标模型,以期在保证换乘成功的前提下最小化列车运行计划调整.以京沪高铁和郑徐高铁上行部分区段为例验证模型的有效性.研究结果表明:当考虑列车总调整时间和换乘客流失败成本相互制约关系时,可以通过增加列车运行调整时间来提高换乘成功客流量;当考虑所有列车上的旅客延误时间和换乘旅客失败成本相互制约关系时,可以通过牺牲部分换乘旅客来减少在车旅客的总延误时间;当其他接续列车空余席位大幅减少时,接续方案倾向于调整原接续列车的到发时刻,避免换乘失败的旅客量大幅增加.

考虑动态随机客流的城市轨道交通列车时刻表仿真优化

为更加精准刻画动态随机客流与列车时刻表编制间的复杂匹配过程,综合考虑乘客动态随机到达过程、列车容量限制、车内拥挤度对乘客上下车速率影响、停站时间动态调整和列车运行安全防护等重要运营特征,构建城市轨道交通列车运行离散仿真模型。在此基础上,建立以最小化乘客平均候车时间为目标的随机非线性优化模型,并设计一种基于仿真的有限差分随机逼近算法,用于优化城市轨道交通发车方案。以国内某条线路的实际运营数据为例验证仿真模型及优化方法,结果表明所构建模型及算法具有较好的优化效果和计算效率,优化后的列车实绩运行时刻能更好地适应客流需求的动态随机性,且在不增加发车频次的前提下有效降低乘客平均候车时间,提升城市轨道交通运营管理水平。

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.