A program for timetable compilation by a look-ahead method

✍ Scribed by A.L Cherniavsky

• Publisher: Elsevier Science
• Year: 1972
• Tongue: English
• Weight: 905 KB
• Volume: 3
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(72)90042-2

✦ Synopsis

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 al.qorithm is thor a feasible solution is obtained by successive resolving of"conflicts" between trains, this process being interpreted as the generotion of some tree 7", The way to resolve a conflict is selected by a Iookahead method which enables us to obtain good er~Juqh solulions 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 ~" and T'. When it reaches a cul-de-sac, the algorithm a,~lgments the tree with additioncl nodes.