A particular timetable problem: Terminal scheduling

DOI10.1016/0898-1221(91)90239-ZMaRDI QIDQ2276867zbMATH OpenOpenAlexFDO

Authors András Sebö

Publication date 1991

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(91)90239-z

zbMATH Keywords

bipartite graphscomputer center workload planningHungarian methodpolynomial-time algorithmtime-tabling

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic scheduling theory in operations research (90B35)

Review text

The paper considers a time-tabling problem arising in the computer center workload planning. A mathematical model is presented and its connections to some related problems, including the classical school time-tabling problem, are mentioned. Necessary and sufficient conditions for the existence of a complete time-table which meets the users' demands are established. A polynomial-time algorithm for checking whether such a time-table exists is described. The algorithm is based on the ideas of Hungarian method for the assignment problem. If the algorithm terminates with a negative answer, it is suggested making what the author calls ``a fair reduction of the users' demands. To do that, another algorithm is developed. Some generalizations of the basic model are also discussed. Unfortunately, a considerable amount of misprints makes the reading of the paper rather difficult.

Recommendations

• A particular timetable problem: terminal scheduling
• scientific article; zbMATH DE number 4020833
• A generalized class-teacher model for some timetabling problems
• Tests on a computer method for constructing school timetables
• Time-Tabling Problems: Should They Be Canonical?

Cites work

• A classroom/time assignment model
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3564698 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• scientific article; zbMATH DE number 3363329 (Why is no real title available?)
• On the Complexity of Timetable and Multicommodity Flow Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Some simple scheduling algorithms

Cited in

(3)

• Time-Tabling Problems: Should They Be Canonical?
• scientific article; zbMATH DE number 4020833 (Why is no real title available?)
• A particular timetable problem: terminal scheduling

This page was built for publication: A particular timetable problem: Terminal scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2276867)