A program for timetable compilation by a look-ahead method

摘要

The problem of timetable compilation for a single-track railway is a job-shop scheduling problem but with differences that handicap the generation of feasible solutions. The paper states the problem and describes the algorithm and the experimental results. The idea of the algorithm is that a feasible solution is obtained by successive resolving of “conflicts” between trains, this process being interpreted as the generation of some tree T. The way to resolve a conflict is selected by a lookahead method which enables us to obtain good enough solutions by using a very rough estimate function. One specific feature of the algorithm is that the lookahead tree T′ is not a subtree of T; the other is the culs-de-sac on trees T and T′. When it reaches a cul-de-sac, the algorithm augments the tree with additional nodes.