The combinatorics of timetabling

被引：41

作者：

deWerra, D

机构：

[1] Ecl. Polytech. Federale de Lausanne, Dept. de Mathématiques, Chaire de Rech. Operationnelle

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1997年 / 96卷 / 03期

关键词：

chromatic scheduling; graph coloring; timetabling; course scheduling; hypergraph; Latin squares;

D O I：

10.1016/S0377-2217(96)00111-7

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Various formulations of timetabling problems are given in terms of coloring problems in graphs. We consider a collection of simple class-teacher timetabling problems and review complexity issues for these formulations. This tutorial presentation (which is not claimed to be an exhaustive review nor a research contribution) includes a brief sketch of a tabu search procedure which handles many specific requirements and provides an efficient heuristic technique.

引用

页码：504 / 513

页数：10

共 21 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Berge C., 1983, Graphes

[3] PRECOLORING EXTENSION .1. INTERVAL-GRAPHS [J].