Integrated Job Scheduling and Network Routing

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

Standard

Integrated Job Scheduling and Network Routing. / Gamst, Mette; Pisinger, David.

In: Networks (Washington), Vol. 61, No. 3, 2013, p. 248-262.

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

Harvard

APA

CBE

MLA

Vancouver

Author

Gamst, Mette; Pisinger, David / Integrated Job Scheduling and Network Routing.

In: Networks (Washington), Vol. 61, No. 3, 2013, p. 248-262.

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

Bibtex

@article{73526a11f58e49c580b84a4c45c9bf36,
title = "Integrated Job Scheduling and Network Routing",
keywords = "Scheduling, Network Routing, Multicommodity Flow, Stabilized column generation, Dantzig-Wolfe decomposition",
author = "Mette Gamst and David Pisinger",
year = "2013",
doi = "10.1002/net.21479",
volume = "61",
number = "3",
pages = "248--262",
journal = "Networks (Washington)",

}

RIS

TY - JOUR

T1 - Integrated Job Scheduling and Network Routing

A1 - Gamst,Mette

A1 - Pisinger,David

AU - Gamst,Mette

AU - Pisinger,David

PY - 2013

Y1 - 2013

N2 - We consider an integrated job scheduling and network routing problem which appears in Grid Computing and production planning. The problem is to schedule a number of jobs at a finite set of machines, such that the overall profit of the executed jobs is maximized. Each job demands a number of resources which must be sent to the executing machine through a network with limited capacity. A job cannot start before all of its resources have arrived at the machine. The scheduling problem is formulated as a Mixed Integer Program (MIP) and proved to be NP-hard. An exact solution approach using Dantzig-Wolfe decomposition is presented. The pricing problem is the linear multicommodity flow problem defined on a time-space network. Branching strategies are presented for the branchand-price algorithm and three heuristics and an exact solution method are implemented for finding a feasible start solution. Finally, interior point stabilization is used to decrease the number of columns generated in the branch-and-price algorithm.<br/>The algorithm is experimentally evaluated on job scheduling instances for a Grid network. The Dantzig- Wolfe algorithm with stabilization is clearly superior, being able to solve large instances with 1,000 jobs and 1,000 machines covering 24 hours of scheduling activity on a Grid network. The algorithm is also compared to simulations of a real-life Grid, and results show that the solution quality significantly increases when solving the problem to optimality. The promising results indicate that the algorithm can be used as an actual scheduling algorithm in the Grid or as a tool for analyzing Grid performance<br/>when adding extra machines or jobs. © 2012 Wiley Periodicals, Inc.

AB - We consider an integrated job scheduling and network routing problem which appears in Grid Computing and production planning. The problem is to schedule a number of jobs at a finite set of machines, such that the overall profit of the executed jobs is maximized. Each job demands a number of resources which must be sent to the executing machine through a network with limited capacity. A job cannot start before all of its resources have arrived at the machine. The scheduling problem is formulated as a Mixed Integer Program (MIP) and proved to be NP-hard. An exact solution approach using Dantzig-Wolfe decomposition is presented. The pricing problem is the linear multicommodity flow problem defined on a time-space network. Branching strategies are presented for the branchand-price algorithm and three heuristics and an exact solution method are implemented for finding a feasible start solution. Finally, interior point stabilization is used to decrease the number of columns generated in the branch-and-price algorithm.<br/>The algorithm is experimentally evaluated on job scheduling instances for a Grid network. The Dantzig- Wolfe algorithm with stabilization is clearly superior, being able to solve large instances with 1,000 jobs and 1,000 machines covering 24 hours of scheduling activity on a Grid network. The algorithm is also compared to simulations of a real-life Grid, and results show that the solution quality significantly increases when solving the problem to optimality. The promising results indicate that the algorithm can be used as an actual scheduling algorithm in the Grid or as a tool for analyzing Grid performance<br/>when adding extra machines or jobs. © 2012 Wiley Periodicals, Inc.

KW - Scheduling

KW - Network Routing

KW - Multicommodity Flow

KW - Stabilized column generation

KW - Dantzig-Wolfe decomposition

U2 - 10.1002/net.21479

DO - 10.1002/net.21479

JO - Networks (Washington)

JF - Networks (Washington)

IS - 3

VL - 61

SP - 248

EP - 262

ER -