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 one 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.

  • Corporate Authors:

    North-Holland Publishing Company

    P.O. Box 211
    1000 AE Amsterdam,   Netherlands 
  • Authors:
    • Cherniavsky, A L
  • Publication Date: 1972

Media Info

  • Features: References;
  • Pagination: p. 61-76
  • Serial:

Subject/Index Terms

Filing Info

  • Accession Number: 00056843
  • Record Type: Publication
  • Source Agency: Engineering Index
  • Files: TRIS
  • Created Date: Jul 31 1976 12:00AM