Heuristic Algorithm for a Military Training Timetabling Problem

Si-Young Lee ； Yeong-Dae Kim ； Ho-Joo Lee

《Asia Pacific Management Review》 14卷3期 (2009/09) Pp. 289-299

https://doi.org/10.6126/APMR.2009.14.3.04

並列摘要

This paper focuses on a military training timetabling problem (MTTP) that occurs in the Korea army. The MTTP can be considered a generalized version of the professor-lecturer model composed of classes, groups of classes, professors for group lectures and lecturers for class lectures. Unlike the typical professor-lecturer model, we need to consider additional constraints to reflect real situations, such as those for lunch time, duration of each lecture (2 hours and 4 hours), and set-up time required between the lectures if places (indoor and outdoor) for two consecutive lectures are different. We suggest a heuristic algorithm for the MTTP with the objective of minimizing the makespan and the number of setups. This algorithm employs solution methods for the edge-coloring problem, in which solutions are found by edge-ordering rules. Results of computational experiments show that the suggested algorithm gives good schedules in a reasonably short time.

並列關鍵字

Military training ； timetabling ； edge coloring ； bipartite graph

參考文獻

de Werra, D.(1970).On some combinatorial problems arising in scheduling.CORS Journal.8(3),165-175.

Asratian, A.S.,de Werra, D.(2002).A generalized class-teacher model for some timetabling problems.European Journal of Operational Research.143(3),531-543.

Asratian, A.S.,Kamalian, R.R.(1994).Investigation on interval edge-colorings of graphs.Journal of Combinatorial Theory, Series B.62(1),34-43.

Burke, E.K.,Petrovic, S.(2002).Recent research directions in automated timetabling.European Journal of Operational Research.140(2),266-280.

Caragiannis, I.,Kaklamanis, C.,Persiano, P.(2002).Edge-coloring of bipartite graphs with constraints.Theoretical Computer Science.270(1-2),361-399.