A hybrid self-adaptive bees algorithm for examination timetabling problems

A hybrid self-adaptive bees algorithm is proposed for the examination timetabling problems. The bees algorithm (BA) is a population-based algorithm inspired by the way that honey bees forage for food. The algorithm presents a type of neighbourhood search that includes a random search that can be used for optimisation problems. In the BA, the bees search randomly for food sites and return back to the hive carrying the information about the food sites (fitness values); then, other bees will select the sites based on their information (more bees are recruited to the best sites) and will start a random search. We propose three techniques (i.e. disruptive, tournament and rank selection strategies) for selecting the sites, rather than using the fitness value, to improve the diversity of the population. Additionally, a self-adaptive strategy for directing the neighbourhood search is added to further enhance the local intensification capability. Finally, a modified bees algorithm is combined with a local search (i.e. simulated annealing, late acceptance hill climbing) to quickly descend to the optimum solution. Experimental results comparing our proposed modifications with each other and with the basic BA show that all of the modifications outperform the basic BA; an overall comparison has been made with the best known results on two examination timetabling benchmark datasets, which shows that our approach is competitive and works well across all of the problem instances.     

A graph coloring constructive hyper-heuristic for examination timetabling problems

In this work we investigate a new graph coloring constructive hyper-heuristic for solving examination timetabling problems. We utilize the hierarchical hybridizations of four low level graph coloring heuristics, these being largest degree, saturation degree, largest colored degree and largest enrollment. These are hybridized to produce four ordered lists. For each list, the difficulty index of scheduling the first exam is calculated by considering its order in all lists to obtain a combined evaluation of its difficulty. The most difficult exam to be scheduled is scheduled first (i.e. the one with the minimum difficulty index). To improve the effectiveness of timeslot selection, a?roulette wheel selection mechanism is included in the algorithm to probabilistically select an appropriate timeslot for the chosen exam. We test our proposed approach on the most widely used un-capacitated Carter benchmarks and also on the recently introduced examination timetable dataset from the 2007 International Timetabling Competition. Compared against other methodologies, our results demonstrate that the graph coloring constructive hyper-heuristic produces good results and outperforms other approaches on some of the benchmark instances.     

A mixed-integer programming approach for solving university course timetabling problems

Journal of Scheduling - This article presents a mixed-integer programming model for solving the university timetabling problem which considers the allocation of students to classes and the...     

A new numerical approach to a non-steady filtration problem

A free-boundary transient problem of seepage flow is studied from a numerical standpoint. From a suitable formulation of the problem in terms of variational inequality we introduce a new numerical approach of the implicit type and based on the finite element method. In this approach the problem is solved on a fixed region and the position of the free boundary is automatically found as part of the solution of the problem; so it is not necessary to solve a succession of problems with different positions of the free boundary. We prove stability and convergence for the approximate solution and we give several numerical results. Work supported by C. N. R. of Italy through the Laboratorio di Analisi Numerica of Pavia.     

A heuristic approach to simultaneous course/student timetabling

Many approaches have been taken in academic environments to address the problem of student and course timetabling. Typically, student scheduling and course scheduling have been treated as separate tasks. Our approach is to build the schedule and place the students into classes simultaneously. That is, to collect all constraints and requirements, quantify them, and build a schedule based on heuristic functions, as we populate it with students. Heuristic functions are also used to order the processing of students. After the schedule is built, we endeavour to further optimise it using additional heuristic-based operations. An initial parallel implementation of the system was performed alongside the manual system followed by live runs in recent semesters. The system has been successfully adopted by the United Arab Emirates University's University General Requirements Unit since the semester starting February 2001. The schedules created have been well accepted by the students and the administration as they have made good use of the students’ time while making near-optimal use of the University's physical and human resources. The scheduling system is written in Visual Basic with embedded SQL.     

A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation

This paper introduces the multi-activity combined timetabling and crew scheduling problem. The goal of this problem is to schedule the minimum number of workers required in order to successfully visit a set of customers characterized by services needed matched against schedule availability. Two solution strategies are proposed. The first is based on mathematical programming whilst the second uses a heuristic procedure in order to reduce computational time. The proposed model combines timetabling with crew scheduling decisions in one mixed integer programming model which considers multiple activities. The algorithms are tested on randomly generated and real instances provided by the Health to School Initiative, a program based at Bogotá’s local Health Department. The results show that the Initiative can increase its coverage by up to 68% using the proposed heuristic approach as a planning process tool.     

A new approach to fuzzy initial value problem

In this paper, we consider a high-order linear differential equation with fuzzy initial values. We present solution as a fuzzy set of real functions such that each real function satisfies the initial value problem by some membership degree. Also we propose a method based on properties of linear transformations to find the fuzzy solution. We find out the solution determined by our method coincides with one of the solutions obtained by the extension principle method. Some examples are presented to illustrate applicability of the proposed method.     

A new approach to partial constraint satisfaction problems

A finite binary Constraint Satisfaction Problem (CSPs) is defined as consisting of a set of n problem variables, a domain of d potential values for each variable and a set of m binary constraints involving only two variables at a time. A solution to such a CSP is specified by assignment of a value to each variable that does not violate any of the constraints. The CSPs belong to the class of NP-Complete Problems. Backtracking and its variants have been generally used for solving CSPs. The class of Partial Constraint Satisfaction Problems (PCSPs) is a subclass of CSPs that are either too difficult to solve or are unsolvable. Near optimal solutions are always desired to these problems.

In this article, we have considered only finite binary CSPs or PCSPs and developed a method of time complexity O(n ² d ²) to obtain a near optimal solution for them. The performance of the method in terms of the average number of consistency checks and the average number of constraint violations is measured on various randomly generated binary CSPs and compared with the Branch and Bound (BB) method used to obtain the same solution. The BB method is a widely used optimization technique that may be viewed as a variation of backtracking. Thus, it was a natural choice in seeking an analog of backtracking to find optimal partial solutions for PCSPs. The proposed method moves much faster to the solution. The performance results indicate that in terms of the number of consistency checks, the proposed method has much less consistency checks than BB whereas in terms of average number of constraint violations both methods are same. An upper bound on the distance of the solution from the optimal solution is obtained analytically as ?n(n???2)(d???2)/(d???1)?.     

An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach

In this paper we consider the no-wait job shop problem with a makespan objective. This problem has usually been addressed by its decomposition into a sequencing and a timetabling problem. Here, first we focus on the timetabling problem and take advantage of the symmetry of the problem in order to suggest a new timetabling procedure. Secondly, we suggest embedding this timetabling into a recent metaheuristic named complete local search with memory.     

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.     

A new mathematical programming approach to multi-group classification problems

In this paper we introduce a goal programming formulation for the multi-group classification problem. Although a great number of mathematical programming models for two-group classification problems have been proposed in the literature, there are few mathematical programming models for multi-group classification problems. Newly proposed multi-group mathematical programming model is compared with other conventional multi-group methods by using different real data sets taken from the literature and simulation data. A comparative analysis on the real data sets and simulation data shows that our goal programming formulation may suggest efficient alternative to traditional statistical methods and mathematical programming formulations for the multi-group classification problem.     

A decision support approach to automatic timetabling in higher education institutions

At a time when the need to reduce costs has become part of the day-to-day reality of all educational institutions, it is unthinkable to continue to manually perform those tasks (i.e., the creation of timetables) that can be automated and optimized. The automatic creation of timetables for educational institutions is one of the most studied problems by the scientific community. However, almost all studies have been based on very simplified models of reality that have no practical application. A realistic model of the problem, robust algorithms that are able to find valid solutions in highly restricted environments, and optimization methods that are able to quickly provide quality results are key factors to consider when attempting to solve this (real) problem faced by educational institutions. This paper presents a summary of the work performed by Bullet Solutions over the last few years, from the first stage of understanding and modelling the problem to the final analysis of the results obtained using the developed software under real conditions.     

Iwasawa decomposition: a new approach to 2D affine registration problem

In this paper, 2D affine registration problem was studied. First, combining with the procedure of traditional iterative closest point method, the registration problem was modeled as an optimization problem on Lie group $GL(2,{\mathfrak{R}})$ . To assure the registration non-degenerate, some reasonable constraints were introduced into the model by Iwasawa decomposition. Then, a series of quadratic programming were used to approximate the registration problem and a novel affine registration algorithm was proposed. At last, several illustration and comparison experiments were presented to demonstrate the performance and efficiency of the proposed algorithm. Particularly, a way of selecting a good initial registration based on ICA method to achieve the global minimum was suggested.     

Applying evolutionary computation to the school timetabling problem: The Greek case

In this contribution, an adaptive algorithm based on evolutionary computation techniques is designed, developed and applied to the timetabling problem of educational organizations. Specifically, the proposed algorithm has been used in order to create feasible and efficient timetables for high schools in Greece. The algorithm has been tested exhaustively with real-world input data coming from many different high schools and has been compared with several other effective techniques in order to demonstrate its efficiency and superior performance. Simulation results showed that the algorithm is able to construct a feasible and very efficient timetable more quickly and easily compared to other techniques, thus preventing disagreements and arguments among teachers and assisting each school to operate with its full resources from the beginning of the academic year. Except from that, due to its inherent adaptive behavior it can be used each time satisfying different specific constraints, in order to lead to timetables, thus meeting the different needs that each school may have.     

A new evolutionary approach to the degree-constrained minimumspanning tree problem

Finding the degree-constrained minimum spanning tree (d-MST) of a graph is a well-studied NP-hard problem of importance in communications network design and other network-related problems. In this paper we describe some previously proposed algorithms for solving the problem, and then introduce a novel tree construction algorithm called the randomized primal method (RPM) which builds degree-constrained trees of low cost from solution vectors taken as input. RPM is applied in three stochastic iterative search methods: simulated annealing, multistart hillclimbing, and a genetic algorithm. While other researchers have mainly concentrated on finding spanning trees in Euclidean graphs, we consider the more general case of random graph problems. We describe two random graph generators which produce particularly challenging d-MST problems. On these and other problems we find that the genetic algorithm employing RPM outperforms simulated annealing and multistart hillclimbing. Our experimental results provide strong evidence that the genetic algorithm employing RPM finds significantly lower-cost solutions to random graph d-MST problems than rival methods     

A linear programming approach to max-sum problem: a review

The max-sum labeling problem, defined as maximizing a sum of binary (i.e., pairwise) functions of discrete variables, is a general NP-hard optimization problem with many applications, such as computing the MAP configuration of a Markov random field. We review a not widely known approach to the problem, developed by Ukrainian researchers Schlesinger et al. in 1976, and show how it contributes to recent results, most importantly, those on the convex combination of trees and tree-reweighted max-product. In particular, we review Schlesinger et al.'s upper bound on the max-sum criterion, its minimization by equivalent transformations, its relation to the constraint satisfaction problem, the fact that this minimization is dual to a linear programming relaxation of the original problem, and the three kinds of consistency necessary for optimality of the upper bound. We revisit problems with Boolean variables and supermodular problems. We describe two algorithms for decreasing the upper bound. We present an example application for structural image analysis.     

A new approach to synthesis problems in timed discrete-event systems

This paper presents a novel approach to the systematic construction of feedback solutions to some important control problems in timed discrete-event systems (TDES) with a global digital clock. Specifically, it deals with those systems which can be modelled by the framework described in the paper, and tackles the intended control problems formulated as a main problem (MP). MP is concerned with finding solutions under which the controlled behaviour of the system can satisfy the intended system specifications: the avoidance of certain forbidden conditions. A sufficient condition for the existence of solutions to MP is derived from the introduction of notions such as critical states and tolerable states as well as an analysis of event trajectories of a TDES in combination with a strategy for manipulating control mechanisms. On the basis of the solvability condition, a synthesis method is established. As the proposed synthesis method can solve the intended control problems systematically without relying on the exact information of event trajectories of a TDES, it provides an alternative for generating solutions efficiently. Finally, the applicability of the proposed method is demonstrated by an example of moderate complexity in a manufacturing system.