Timetabling Markup Language - Dr. Ender ÖZCAN

Timetabling Markup Language - TTML

Timetabling Markup Language (TTML) is an XML based data format for timetabling problems based on MathML content markup.

Timetabling problems can be formulized using set theory, where a constraint is a function operating on the sets. Hence, MathML provides a basis for the representation of timetabling components. For example, MathML allows users to define completely new content symbols that represent a function or a type or another content markup element. This is an important feature that can be used to standardize some timetabling constraints, providing flexibility for users to define their own constraints as well.

Timetabling problems consist in feasible assignment of time-slots to a set of events, subject to a set of constraints. The timetabling problem is an NP complete problem. There are a growing number of solutions to different types of timetabling problems having different types of constraints. Since there is no common standard on specifying a timetabling problem instance and its solution proposed by a researcher, most of the results cannot be compared and benchmarking becomes almost impossible. Proposal for a common data format for timetabling is initiated by Andrew Cumming at ICPTAT'95. Studies in the area yield a language named SSTL. SSTL interpreter developed by Kingston is freely available on the Internet. SSTL has not become a common format as expected, possibly because; it is not that easy to convert existing data to SSTL. Furthermore, most of the research in timetabling is due to some practical need, making the researchers concentrate on solving the problem at their hand, ignoring the data format.

Publication will be available soon:
E. Ozcan, Towards an XML based standard for Timetabling Problems: TTML.

View an example TTML document in the publication.
A general validator for XML documents.

Tools

A common data format for timetabling, TTML is a recent study, hence applications are still under development.

The first application based on TTML is a parser that allows users to covert final exam timetabling text data into a TTML document. The tool is named as CONFETI, available via Internet.
The second application, named FES is still under development. It is a full TTML processor (parser+solver+viewer) based on a memetic algorithm for final exam scheduling. The results will be reported soon.

Data Repository

Data repository will consist of different timetabling problem instances in TTML and textual format.

Please let us know about your timetabling problem instances. Either you can send your data in TTML format or we can do it for you. Please send an email to arti@cse.yeditepe.edu.tr with "TTML data" as the subject.

Final Exam Timetabling
[TTML]

Carter's Benchmark: cars91, carf92, tres92, earf83, hecs92, kfus93, lsef91, ryes93, staf83, utas92, utes92, yorf83.
Our Benchmark: yue20011, yue20012, yue20013, yue20021, yue20022, yue20023, yue20031, yue20032.

University Exam Preparation School Course Timetabling (This data is derived from a Sybase database and provided as is. For details, please contact Alpay Alkan)

Modified problems as a single textual database: fdm1-fd11
Raw data as a single textual database: f1-f11

Employee Shift Timetabling

Our Nurse Rostering Benchmark: rnd1-rnd9, mhtr

Related Publications

E. Ozcan, A. Alkan, "A Memetic Algorithm for Solving a Timetabling Problem: An Incremental Strategy", Proc. of the 3rd Multidisciplinary Int. Conf. On Scheduling: Theory and Applications, P. Baptiste, G. Kendall, A. M. Kordon, F. Sourd (ed.), 394-401, 28-31 August 2007, Paris, France.

E. Ozcan, Memetic Algorithms for Nurse Rostering, Lecture Notes in Computer Science, Springer-Verlag, The 20th International Symposium on Computer and Information Sciences, vol. 3733, 482-492, 2005.
E. Ozcan, "An Empirical Investigation on Memes, Self-generation and Nurse Rostering", Proc. of the 6th Int. Conf. on the Practice and Theory of Automated Timetabling, 246-263, 2006. [Data Set]
E. Ozcan, E. Ersoy, "Final Exam Scheduler - FES", Proc. of 2005 IEEE Congress on Evolutionary Computation, vol. 2, 1356-1363, 2005.
E. Ozcan, Towards an XML based standard for Timetabling Problems: TTML, Multidisciplinary Scheduling: Theory and Applications, Springer Verlag, 163 (24), May 2005.
E. Ozcan, Towards an XML based standard for Timetabling Problems: TTML, Proc. of the First Multidisciplinary International Conference on Scheduling: Theory and Applications, pp.566-569, August 2003.
P. D. Causmaecker, P. Demeester, Y. Lu and G. Vanden, Using Web Standards for Timetabling, PATAT'02, pp.238-258, 2002.
J.H. Kingston, Modeling timetabling problems with STTL, Springer Lecture Notes in Computer Science, 2079:309, 2001.
E. K. Burke, P. A. Pepper and J. H. Kingston, A Standard Data Format for Timetabling Instances, Springer Lecture Notes in Computer Science, 1408:213-222, 1997.