A particular timetable problem: Terminal scheduling (Q2276867)

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.