A particular timetable problem: terminal scheduling.

*(English)*Zbl 0629.60010This paper considers the problem of constructing an optimal time table for m users of \(\ell\) identical machines (terminals of a computer) in n disjoint hours (a week) under the following conditions: a) Each user has the number of hours he would like to work and also the subset of hours he is able to work on a machine. b) The users have some other wishes: Some of them would like long intervals of time, some others may want their times to be uniformly distributed within n hours.

Firstly this paper points out that the problem of finding a feasible time table meeting condition a) (if exists) reduces to the well known max flow problem and hence can efficiently be solved by using alternating paths and minimal path algorithm. Secondly this paper proposes a fair reduction of user’s requests for the case that no feasible time table exists. The fair reduction of the request means that n disjoint hours are fairly distributed to each user in the ligth of the “favourized” function \(p_ u(d)\) user u has for d assigned hours. An efficient algorithm for a fair time table is given. Thirdly, this paper proposes a heuristic algorithm for a good time table in the light of condition b). Lastly, this paper discusses the complexity of some extensions of this problem.

Firstly this paper points out that the problem of finding a feasible time table meeting condition a) (if exists) reduces to the well known max flow problem and hence can efficiently be solved by using alternating paths and minimal path algorithm. Secondly this paper proposes a fair reduction of user’s requests for the case that no feasible time table exists. The fair reduction of the request means that n disjoint hours are fairly distributed to each user in the ligth of the “favourized” function \(p_ u(d)\) user u has for d assigned hours. An efficient algorithm for a fair time table is given. Thirdly, this paper proposes a heuristic algorithm for a good time table in the light of condition b). Lastly, this paper discusses the complexity of some extensions of this problem.

Reviewer: H.Kise

##### Keywords:

Hungarian method; shortest path; optimal time table; alternating paths; minimal path algorithm; heuristic algorithm
Full Text:
DOI

##### References:

[1] | Even S., STAM J. Comput 5 pp 691– (1976) |

[2] | Ford L.R., Flows in Networks (1962) · Zbl 0106.34802 |

[3] | Garey Johnson, Computers and intractability (1979) |

[4] | DOI: 10.1016/S0167-5060(08)70356-X · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |

[5] | DOI: 10.1002/nav.3800210113 · Zbl 0276.90024 · doi:10.1002/nav.3800210113 |

[6] | Lawler E.L., Combinatorial optimization: Networks and matroids (1976) · Zbl 0413.90040 |

[7] | Z L., Combinatorial problems and exercises (1979) |

[8] | DOI: 10.1016/0377-2217(82)90012-1 · Zbl 0471.90061 · doi:10.1016/0377-2217(82)90012-1 |

[9] | DOI: 10.1093/comjnl/23.4.307 · doi:10.1093/comjnl/23.4.307 |

[10] | De Werra D., Infor-Canad. J. Operational Res. and Information Processing 9 pp 12– (1971) |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.