Masalah Penjadwalan Kereta Api Jalur Ganda Menggunakan Model Job-Shop

Abstract

Train scheduling problem can be modeled as a special case of job-shop scheduling problems. Based on the job-shop scheduling concept, the train trip can be considered as a job, which will be scheduled on tracks as resources. In this paper, train scheduling model is formulated under common rules in railroad system, e.g. crossing, overtaking and headway rules. The crossing rule is not implemented for double track, because there are two tracks that can be used by two trains with different directions. The train scheduling model is expressed in the form of integer linear programming and solved by branch and bound algorithm to minimize the total makespan. The model is then implemented for double track case of Mass Rapid Transit (MRT) Lebak Bulus- Sisingamangaraja route, which involves 11 MRT Economy and 7 MRT Express trains using hypothetical data. The train time-space diagrams show that there is no conflicts occurred and the total makespan is 1502 minutes. The result, in particular, indicates that there is an 11 minutes delay for MRT Express. The length of the delay can be reduced by employing an additional delay constraint. But, of course, this will deteriorate the makespan.