On the Integrated Job Scheduling and Constrained Network Routing Problem

Mette Gamst

    Research output: Book/ReportReportResearch

    42 Downloads (Pure)

    Abstract

    This paper examines the NP-hard 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 demands a number of resources, which must be sent to the executing machine via constrained paths. Furthermore, two resource demand transmissions cannot use the same edge in the same time period. An exact solution approach based on Dantzig-Wolfe decomposition is proposed along with several heuristics. The methods are computationally evaluated on test instances arising from telecommunications with up to 500 jobs and 500 machines. Results show that solving the problem to optimality is very difficult. The proposed heuristics have good performance with an average solution value gap of 3% and with very small running times.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages21
    ISBN (Print)978-87-90855-67-3
    Publication statusPublished - 2010
    SeriesDTU Management 2010
    Number3

    Keywords

    • grid computing
    • job scheduling
    • branch-and-bound
    • routing and wavelength assignment
    • heuristics
    • network routing

    Cite this