Scheduling Network Traffic for Grid Purposes

This thesis concerns scheduling of network traffic in grid context. Grid computing consists of a number of geographically distributed computers, which work together for solving large problems. The computers are connected through a network. When scheduling job execution in grid computing, data transmission has so far not been taken into account. This causes stability problems, because data transmission takes time and thus causes delays to the execution plan. This thesis proposes the integration of job scheduling and network routing. The scientific contribution is based on methods from operations research and consists of six papers. The first four considers data transmission in grid context. The last two solves the data transmission problem, where the number of paths per data connection is bounded from above. The thesis shows that it is possible to solve the integrated job scheduling and network routing problem to optimality for a grid, where computers are connected through a packet-switched network. When the network topology is optical, the routing problem becomes significantly more complex and the problem should thus be solved heuristically. Furthermore, the thesis proposes a number of new exact methods for the data transmission problem, where the number of paths is bounded from above. The new exact solution methods outperform existing methods from the literature.