Abstract: This paper presents a perturbation based search method
to solve the unconstrained binary quadratic programming problem.
The proposed algorithm was tested with some of the standard test
problems and the results are reported for 10 instances of 50, 100, 250,
& 500 variable problems. A comparison of the performance of the
proposed algorithm with other heuristics and optimization software is
made. Based on the results, it was found that the proposed algorithm
is computationally inexpensive and the solutions obtained match the
best known solutions for smaller sized problems. For larger instances,
the algorithm is capable of finding a solution within 0.11% of the
best known solution. Apart from being used as a stand-alone method,
this algorithm could also be incorporated with other heuristics to find
better solutions.
Abstract: This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.