Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A generalized class-teacher model for some timetabling problems
Luleå University of Technology.
École Polytechnique Fédérale de Lausanne.
2002 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 143, no 3, p. 531-542Article in journal (Refereed) Published
Abstract [en]

We consider a theoretical model which extends the basic "class-teacher model" of timetabling and which corresponds to some situations which occur frequently in the basic training programs of universities and schools. We are given m teachers T1, ..., Tm and n classes C1, ..., Cn. The set of classes is partitioned into p disjoint subsets G1, ..., Gp in such a way that in addition to the lectures given by one teacher to one class, there are some lectures given by one teacher to the students of all classes in group Gl, 1 ≤ l ≤ p. Such lectures will be called group-lectures. The number alj of one hour group-lectures which teacher Tj must deliver to group Gl and the number bij of one hour class-teaching which Tj must give to class Ci are given. Is there a timetable of t hours (or length t), so that each class Ci and each group Gl receive all their lectures, but no student is scheduled to be taught by more than one teacher in each hour, and no teacher must teach to more than one group or class in each hour? We show that this problem is NP-complete and find some sufficient conditions for the existence of a timetable of length t. We also describe an algorithm for constructing a timetable corresponding to the requirement matrices A = (alj) and B = (bij) and show that under a natural assumption on A and B this algorithm finds a timetable within 7/6 of the optimum length

Place, publisher, year, edition, pages
Elsevier, 2002. Vol. 143, no 3, p. 531-542
National Category
Mathematical Analysis
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:ltu:diva-4395DOI: 10.1016/S0377-2217(01)00342-3ISI: 000178746500004Scopus ID: 2-s2.0-0037121476Local ID: 257de1c0-ac8b-11db-aeba-000ea68e967bOAI: oai:DiVA.org:ltu-4395DiVA, id: diva2:977268
Note

Validerad; 2002; 20070125 (kani)

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2022-10-21Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Asratian, Armen

Search in DiVA

By author/editor
Asratian, Armen
By organisation
Luleå University of Technology
In the same journal
European Journal of Operational Research
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 56 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf