Exact and heuristic solution approaches for the Integrated Job Scheduling and Constrained Network Routing Problem

Publication: Research - peer-reviewJournal article – Annual report year: 2014

Without internal affiliation

View graph of relations

This paper examines the problem of scheduling a number of jobs on a finite set of machines such that the overall profit of executed jobs is maximized. Each job has a certain demand, which must be sent to the executing machine via constrained paths. A job cannot start before all its demands have arrived at the machine. Furthermore, two resource demand transmissions cannot use the same edge in the same time period. The problem has application in grid computing, where a number of geographically distributed machines work together for solving large problems. The machines are connected through an optical network.
The problem is formulated as an IP problem and is shown to be NP-hard. An exact solution approach based on Dantzig–Wolfe decomposition is proposed. Also, several heuristic methods are developed by combining heuristics for the job scheduling problem and for the constrained network routing problem.
The methods are computationally evaluated on test instances arising from telecommunications with up to 500 jobs and 500 machines. Results show that solving the integrated job scheduling and constrained network routing problem to optimality is very difficult. The exact solution approach performs better than using a standard IP-solver; however, it is still unable to solve several instances. The proposed heuristics generally have good performance. Especially, the First Come First Serve scheduling heuristic combined with a routing strategy, which proposes several good routes for each demand, has good performance with an average solution value gap of 3%. All heuristics have very small running times.
© 2011 Elsevier B.V. All rights reserved.
Original languageEnglish
JournalDiscrete Applied Mathematics
Publication date2014
Volume164
IssuePart 1
Pages121–137
ISSN0166-218X
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 0
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 12366909