Decomposition Algorithms For The Interval Scheduling Problem

Scheduling track lines at a marshalling station where the objective is to determine the maximal weighted number of trains on the track lines can be modeled as an interval scheduling problem: each job has a fixed starting and finishing time and can only be carried out by an arbitrarily given subset of machines. This scheduling problem is formulated as an integer program, which is NP-Complete when the number of machines and jobs are unfixed and the computational effort to solve large scale test problems is prohibitively large. Heuristic algorithms (HAs) based on the decomposition of original problem have been developed and the benefits lie in both conceptual simplicity and computational efficiency. Genetic algorithm (GA) to address the scheduling problem is also proposed. Computational experiments on low and high utilization rates of machines are carried out to compare the performance of the proposed algorithms with Cplex. Computational results show that the HAs and GA perform well in most condition, especially HA2 with the maximum of average percentage deviation on average 3.5% less than the optimal solutions found by Cplex in small-scale problem. Our methodologies are capable of producing improved solutions to large-scale problems with reasonable computing resources, too.