×

Exchanges procedures for timetabling problems. (English) Zbl 0745.90037

Summary: Timetabling problems appear in several practical applications, and they can be formulated as 0-1 programming problems to determine an optimal assignment of items to resources minimizing total cost and satisfying \(K\) additional side constraints. The proposed approach to deal with this problem is a heuristic iterative procedure where the assignment of one item is modified at each iteration. This exchange procedure is applied first to determine a feasible solution satisfying the side constraints, and then to improve the objective function. A geometric interpretation of an exchange is first given to induce a theoretical framework for the procedure. Furthermore, two other procedures are introduced to prevent jamming situations outside the feasible domain or at a local optimum. The first procedure uses inductively more than one exchange per iteration, and the second one relies on Lagrangean relaxation.

MSC:

90B35 Deterministic scheduling theory in operations research
90C09 Boolean programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aubin, J., Une approche heuristique pour la confection d’horaires de CECEP, (Master Thesis (1985), Département d’Informatique et de Recherche Opérationnelle, Université de Montréal: Département d’Informatique et de Recherche Opérationnelle, Université de Montréal Montréal, Qué)
[2] Aubin, J.; Ferland, J. A., A large scale timetabling problem, Comput. Oper. Res., 16, 67-77 (1989) · Zbl 0659.90056
[3] Carter, M., A survey of practical applications on examination timetabling, Oper. Res., 34, 193-202 (1986)
[4] Ferland, J. A., CAT: Computer aided timetabling, (Publication no. 668 (1988), Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal: Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal Montréal, Qué)
[5] Ferland, J. A.; Fleurent, C., Computer aided scheduling for sport league, Infor., 29, 14-25 (1991)
[6] Ferland, J. A.; Roy, S., Timetabling problem for universities as assignment of activities to resources, Comput. Oper. Res., 12, 207-218 (1985) · Zbl 0608.90042
[7] Fisher, M. L., An applications oriented guide to Lagrangean relaxation, Interfaces, 15, 10-21 (1985)
[8] Fisher, M. L.; Jaikumar, R.; van Wassenhove, L. N., A multiplier adjustment method for the generalized assignment problem, (Working paper no. 81-07-06 (1981), The Wharton School, University of Pennsylvania: The Wharton School, University of Pennsylvania Philadelphia, PA) · Zbl 0626.90036
[9] Fleurent, C., Méthodes heuristiques pour la conception de calendriers sportifs, (Master Thesis (1987), Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal: Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal Montréal, Qué)
[10] Geoffrion, A. M., Lagrangean relaxation for integer programming, Math. Programming Stud., 2, 82-114 (1974) · Zbl 0395.90056
[11] Glover, F., Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13, 533-549 (1986) · Zbl 0615.90083
[12] Glover, F., The general employee scheduling problem: an integration of MS and AI, Comput. Oper. Res., 13, 563-573 (1986)
[13] Glover, F., Tabu search, CAAI Rep. 88-3, (Center for Applied Artificial Intelligence (1988), University of Colorado: University of Colorado Boulder, CO)
[14] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math. Programming, 6, 62-88 (1974) · Zbl 0284.90057
[15] Hertz, A.; de Werra, D., Using tabu search techniques for graph coloring, Computing, 39, 345-351 (1987) · Zbl 0626.68051
[16] Laporte, C.; Desroches, S., Examination timetabling by computer, Comput. Oper. Res., 11, 351-360 (1984)
[17] Lavoie, A., Méthode d’échanges pour problémes d’affectation, (Master Thesis (1989), Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal: Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal Montréal Qué)
[18] Mazzola, J. B.; Neebe, A. W., Resource-constrained assignment scheduling, Oper. Res., 34, 560-572 (1986) · Zbl 0609.90087
[19] Ross, C. T.; Soland, R. M., A branch and bound algorithm for the generalized assignment problem, Math. Programming, 8, 91-103 (1975) · Zbl 0308.90028
[20] Roy, S., Problème d’affectation généralisée avec conflicts: application au problème de confection d’horaires de cours, (Master Thesis (1982), Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal: Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal Montréal, Qué)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.