Integrating job scheduling and constrained network routing

Mette Gamst

    Research output: Contribution to journalJournal articleResearchpeer-review


    This paper examines the NP-hard problem of scheduling jobs on resources such that the overall profit of executed jobs is maximized. Job demand must be sent through a constrained network to the resource before execution can begin. The problem has application in grid computing, where a number of geographically distributed resources connected through an optical network work together for solving large problems. A number of heuristics are proposed along with an exact solution approach based on Dantzig-Wolfe decomposition. The latter has some performance difficulties while the heuristics solve all instances within minutes and with an average solution value gap as low as 3%.
    Original languageEnglish
    JournalElectronic Notes in Discrete Mathematics
    Pages (from-to)57-64
    Publication statusPublished - 2010


    • Network Routing
    • Grid Computing
    • Job Scheduling
    • branch-and-price
    • heuristic

    Fingerprint Dive into the research topics of 'Integrating job scheduling and constrained network routing'. Together they form a unique fingerprint.

    Cite this