Constraint-based job shop scheduling with ILOG SCHEDULER

W.P.M. Nuijten, C. Le Pape

    Research output: Contribution to journalArticleAcademicpeer-review

    48 Citations (Scopus)

    Abstract

    We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.
    Original languageEnglish
    Pages (from-to)271-286
    Number of pages16
    JournalJournal of Heuristics
    Volume3
    Issue number4
    DOIs
    Publication statusPublished - 1998

    Fingerprint

    Job Shop Scheduling
    Job Shop Scheduling Problem
    Scheduling
    Trees (mathematics)
    Search Trees
    Empirical Analysis
    Approximation algorithms
    Performance Analysis
    Scheduling Problem
    Approximation Algorithms
    Lower bound
    Job shop scheduling

    Cite this

    @article{5389a6f776a3409e8321816dc08c4721,
    title = "Constraint-based job shop scheduling with ILOG SCHEDULER",
    abstract = "We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.",
    author = "W.P.M. Nuijten and {Le Pape}, C.",
    year = "1998",
    doi = "10.1023/A:1009687210594",
    language = "English",
    volume = "3",
    pages = "271--286",
    journal = "Journal of Heuristics",
    issn = "1381-1231",
    publisher = "Springer",
    number = "4",

    }

    Constraint-based job shop scheduling with ILOG SCHEDULER. / Nuijten, W.P.M.; Le Pape, C.

    In: Journal of Heuristics, Vol. 3, No. 4, 1998, p. 271-286.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Constraint-based job shop scheduling with ILOG SCHEDULER

    AU - Nuijten, W.P.M.

    AU - Le Pape, C.

    PY - 1998

    Y1 - 1998

    N2 - We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.

    AB - We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.

    U2 - 10.1023/A:1009687210594

    DO - 10.1023/A:1009687210594

    M3 - Article

    VL - 3

    SP - 271

    EP - 286

    JO - Journal of Heuristics

    JF - Journal of Heuristics

    SN - 1381-1231

    IS - 4

    ER -