Search

A Thesis Submitted to the Faculty of Graduate Studies and Research in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Computer Science, University of Regina. xii, 204 l. University timetabling is a well-known problem and much research has been done about it. This is an interesting subject to study because neither modeling nor solving it is straightforward. It has different variants ranging from teaching assignment to course timetabling to examination timetabling. Constructing any of these problems as a conflict-free timetable is a challenging task encountered every year by many educational institutions and universities across the world. Most of the current research in timetabling concentrates on exploring how the level of generalization of algorithms applied can be advanced, so that a broader range of problems can be addressed. In this thesis, we pay special attention to two of these timetabling problems, first, the teaching assignment and second, the examination timetabling in a university environment. Two different methodologies that make use of two generic solvers to solve the aforementioned problems are proposed. We propose an extension approach to the backtracking with look-ahead technique to solve the teaching assignment problem that adopts weighted partial satisfaction of soft constraints. Determining the optimal solution for a teaching assignment problem is a challenging task. The optimized look-ahead backtracking method applied to the solution is proposed and discussed along with computational results of evaluation tests conducted on datasets collected from the Computer Science department at the University of Regina. A multi-phase parallel hybrid metaheuristics approach integrating Tabu Search, Hill Climbing, Simulated Annealing and a modified version of Extended Great Deluge algorithms using metaheuristics techniques is proposed in relation to solve Large Examination Timetabling Problem. We present a pre-processing phase that includes a number of pre-construction procedures that does collections ordering and detecting some of the hidden constraints for a fast easy construction. We also propose a range of experiments on benchmark problem instances conducted to evaluate the proposed approach. In this regard, our method was capable of producing reasonable results in comparison to the best results published so far on the well-known benchmark data sets. A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy *, University of Regina. *, * p. Student yes

Ankara : The Department of Industrial Engineering and the Graduate School of Engineering and Science of Bilkent University, 2013. Thesis (Master's) -- Bilkent University, 2013. Includes bibliographical references leaves 91-96. This study considers a scheduling problem with position-dependent deteriorating jobs and a maintenance activity in a single machine. Even in the absence of maintenance activity and deterioration problem is NP-hard. A solution comprises the following: (i) positions of jobs, (ii) the position of the maintenance activity, (iii) starting time of the first job in the schedule. After the maintenance activity, machine will revert to its initial condition and deterioration will start anew. The objective is to minimize the total weighted earliness and tardiness costs. Jobs scheduled before (after) the due-date are penalized according to their earliness (tardiness) value. Polynomial (O(n log n)) time solutions are provided for some special cases. No polynomial solution exists for instances with tight due-dates. We propose a mixed integer programming model and efficient algorithms for the cases where mathematical formulation is not efficient in terms of computational time requirements. Computational results show that the proposed algorithms perform well in terms of both solution quality and computation time. Şirvan, Fatma M.S.

ÖZET BİR DERS ÇIZELGELEME PROBLEMİ: KISIT VE MATEMATİKSEL PROGRAMLAMA UYGULAMASI Ahmet Reha Botsalı Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doç. Dr. Ömer S. Benli Haziran 2000 Kısıt programlaması kombinatoryal optimizasyon problemlerinin çözümünde kullanılan oldukça yeni bir yöntemdir. Bu yöntem, özellikle yan kısıtları olan büyük ölçekli çizelgeleme problemlerinde çok etkin olmaktadır. Üniversite ders çizelgelemesi problemi kombinatoryal optimizasyon problemlerinin en zorlarından biridir. Ek olarak, her kurumun özel gereksinimleri, bu problem için genel bir model ve çözüm algoritması önermeyi olanaksız kılmaktadır. Bu çalışmanın amacı, Bilkent Üniversitesi için ders çizelgelemesi oluşturan bir sistem tasarlamaktır. Bu sistem hem kısıt programlaması hem de matem atiksel programlama tekniklerinden yararlanmaktadır. Problem, üç aşamada çözülmektedir, ilk iki aşamada kısıt programlaması teknikleri kullanılarak bir ders çizelgesi oluşturulmakta, son aşamada ise sınıflar derslere tam sayı program laması kullanılarak atanmaktadır. Önerilen sistemin uygulanabilirliği, Bilkent Üniversitesi'nin geçmiş dönemlere ait verileri kullanılarak gösterilmiştir.VI Anahtar Kelimeler. Üniversite ders çizelgelemesi, kısıt programlaması, mate matiksel programlama ABSTRACT A TIMETABLING PROBLEM: CONSTRAINT AND MATHEMATICAL PROGRAMMING APPROACHES Ahmet Reha Botsalı M.S. in Industrial Engineering Supervisor: Assoc. Prof. Dr. Ömer S. Benli June 2000 Constraint programming is a relatively new approach for solving combinatorial optimization problems. This approach is especially effective for large scale scheduling problems with side conditions. University course scheduling problem is one of the hard problems in combinatorial optimization. Furthermore, the specific requirements of each institution make it very difficult to suggest a generalized model and a solution algorithm for this problem. The purpose of this study is to design a system for scheduling courses at Bilkent University. This system utilizes both constraint programming and mathematical programming techniques. The problem is solved in three stages. The first two stages, in tandem, generate a course schedule using constraint programming techniques, and in the last stage classrooms are assigned to courses by means of a mixed integer programming model. The proposed system is validated by experimental runs using Bilkent University course offerings and classroom data from past semesters. mIV Keywords: Timetabling, university course scheduling, constraint programming, mathematical programming. 91

Περίληψη: Μη διαθέσιμο