Masalah penjadwalan kereta dapat dipandang sebagai salah satu masalah penjadwalan yang disebut job-shop scheduling problem (JSP), yaitu suatu masalah untuk menyelesaikan sejumlah pekerjaan pada sejumlah mesin yang berbeda. Dalam JSP, kereta dipandang sebagai pekerjaan yang melalui segmen rel tertentu (block section) yang dipandang sebagai mesin. Konflik terjadi saat dua atau lebih kereta membutuhkan block section yang sama pada saat yang sama sehingga harus diputuskan kereta mana yang akan mendahului kereta lainnya. Untuk merepresentasikan keputusan tersebut digunakan suatu pemodelan graf yang disebut formulasi graf alternatif. Masalah ini kemudian disebut sebagai conflict resolution problem (CRP). Diberikan jadwal awal dari sejumlah kereta pada jaringan. Tujuan penyelesaian CRP adalah untuk menemukan jadwal baru yang bebas dari konflik sehingga kereta datang dan berangkat dengan kemungkinan keterlambatan terkecil saat terjadi gangguan pada jadwal awal. Inisialisasi solusi yang dilakukan pada tugas akhir ini dilakukan dengan metode greedy avoid most critical completion time (AMCC) dan untuk memperbaiki solusi tersebut digunakan metode branch and bound.

---

Train scheduling problem can be considered as a job-shop scheduling problem (JSP), i.e. a problem to complete a set of jobs which passes through a set of machines. In JSP, a set of trains is considered as a set of jobs which successively passes through a set of railway segments (called block sections) which is considered as a set of machines. A conflict occurs whenever two or more trains require the same block section at the same time and the decision to be taken is to determine the sequence of each conflicting train. To achieve this, an alternative graph formulation is applied. The problem is then called conflict resolution problem (CRP). Given the initial schedule of the trains in a railway network. The object of CRP is to determine a new conflict-free schedule such that trains arrive and depart with the smallest possible delay when the initial schedule is perturbed. Initial solution is constructed by greedy heuristic method called avoid most critical completion time (AMCC) method and to improve this solution, branch and bound method is subsequently applied.