Loading...
4 results
Search Results
Now showing 1 - 4 of 4
- A shuffled complex evolution algorithm for the examination timetabling problemPublication . Leite, Nuno; Melicio, Fernando; Rosa, Agostinho C.In this work two instances of the examination timetabling problem are studied and solved using memetic algorithms. The first is the uncapacitated single-epoch problem instance. In the second problem instance two examination epochs are considered, with different durations. The memetic algorithm, named Shuffled Complex Evolution Algorithm, uses a population organized into sets called complexes which evolve independently using a recombination and local search operators. Population diversity is preserved by means of the recombination operator and a special solution update mechanism. Experimental evaluation was carried out on the public uncapacitated Toronto benchmarks (single epoch) and on the ISEL-DEETC department examination benchmark (two epochs). Results show that the algorithm is competitive on the Toronto benchmarks, attaining a new lower bound on one benchmark. In the ISEL-DEETC benchmark, the algorithm attains a lower cost when compared with the manual solution.
- A hybrid shuffled frog-leaping algorithm for the university examination timetabling problemPublication . Leite, Nuno; Melicio, Fernando; Rosa, Agostinho C.The problem of examination timetabling is studied in this work. We propose a hybrid solution heuristic based on the Shuffled Frog-Leaping Algorithm (SFLA) for minimising the conflicts in the students's exams. The hybrid algorithm, named Hybrid SFLA (HSFLA), improves a population of frogs (solutions) by iteratively optimising each memeplex, and then shuffling the memeplexes in order to distribute the best performing frogs by the memeplexes. In each iteration the frogs are improved based on three operators: crossover and mutation operators, and a local search operator based on the Simulated Annealing metaheuristic. For the mutation and local search, we use two well known neighbourhood structures. The performance of the proposed method is evaluated on the 13 instances of the Toronto datasets from the literature. Computational results show that the HSFLA is competitive with state-of-the-art methods, obtaining the best results on average in seven of the 13 instances.
- A fast simulated annealing algorithm for the examination timetabling problemPublication . Leite, Nuno; Melicio, Fernando; Rosa, AgostinhoThe timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a new variant of the simulated annealing (SA) algorithm, named FastSA, is proposed for solving the examination timetabling problem. In the FastSA's acceptance criterion, each exam selected for scheduling is only moved (and the associated move is evaluated) if that exam had any accepted moves in the immediately preceding temperature bin. Ten temperature bins were formed, ensuring that an equal number of evaluations is performed by the FastSA, in each bin. It was observed empirically that if an exam had zero accepted movements in the preceding temperature bin, it is likely to have few or zero accepted movements in the future, as it is becoming crystallised. Hence, the moves of all exams that are fixed along the way are not evaluated no more, yielding a lower number of evaluations compared to the reference algorithm, the standard SA. A saturation degree-based heuristic, coupled with Conflict-Based Statistics in order to avoid any exam assignment looping effect, is used to construct the initial solution. The proposed FastSA and the standard SA approaches were tested on the 2nd International Timetabling Competition (ITC 2007) benchmark set. Compared to the SA, the FastSA uses 17% less evaluations, on average, and a maximum of 41% less evaluations on one instance. In terms of solution cost, the FastSA is competitive with the SA algorithm attaining the best average fitness value in four out of twelve instances, while requiring less time to execute. In terms of average comparison with the state-of-the-art approaches, the FastSA improves on one out of twelve instances, and ranks third among the five best algorithms. The article's main impact comprises the points: (i) proposal of a new algorithm (FastSA) which is able to attain a reduced computation time (and number of evaluations computed) compared to the standard SA, (ii) demonstration of the FastSA capabilities on a NP-Complete timetabling problem, (iii) comparison with state-of-the-art approaches where the FastSA is able to improve the best known result on a benchmark instance. Due to the variety of problems solved by expert and intelligent systems using SA-based algorithms, we believe that the proposed approach will open new research paths with the creation of new algorithms that explore the space in a more efficient way.
- A cellular memetic algorithm for the examination timetabling problemPublication . Leite, Nuno; Fernandes, Carlos M.; Melicio, Fernando; Rosa, AgostinhoThe timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a given set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a cellular memetic algorithm is proposed for solving the examination timetabling problem. Cellular evolutionary algorithms are population-based metaheuristics. They differ from non-cellular algorithms in that the population is organised in a cellular structure, providing for a smooth actualisation of the populations that contributes to improving the population diversity. The proposed cellular evolutionary algorithm is hybridised with the threshold acceptance local search metaheuristic. The implemented algorithm uses feasible genetic recombination and local search operators, thus limiting the exploration to the feasible solution space. The effect of the threshold acceptance used in the hybrid algorithm for the examination timetabling problem is studied. It is shown that a low threshold decreasing rate is needed in order to rearrange the most difficult exams in better periods, allowing for the easy set of exams to be placed in good periods as well. The approach was tested on the public Toronto and ITC 2007 benchmark sets. The proposed hybrid is able to attain four and three new upper bounds for the Toronto and ITC 2007 benchmark sets, respectively.