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

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.