DECOMPOSITION ALGORITHMS FOR THE INTERVAL SCHEDULING PROBLEM

Shidong Wang (), Li Zheng () and Zhihai Zhang ()
Additional contact information
Shidong Wang: Department of Industrial Engineering Tsinghua University, Beijing, China
Li Zheng: Department of Industrial Engineering Tsinghua University, Beijing, China
Zhihai Zhang: Department of Industrial Engineering Tsinghua University, Beijing, China

Asia-Pacific Journal of Operational Research (APJOR), 2010, vol. 27, issue 04, 517-537

Abstract: 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.

Keywords: Scheduling track lines; interval scheduling; heuristic algorithm; genetic algorithm (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595910002831
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:27:y:2010:i:04:n:s0217595910002831

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595910002831

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().