On the complexity of preemptive open-shop scheduling problems (Q1058969)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the complexity of preemptive open-shop scheduling problems
scientific article

    Statements

    On the complexity of preemptive open-shop scheduling problems (English)
    0 references
    0 references
    0 references
    1985
    0 references
    The problem of preemptively scheduling a set of n independent jobs on an m-machine open shop is studied, and two results are obtained. The first indicates that constructing optimal flow-time schedules is NP-hard for m larger than two. The second result shows that the problem remains NP-hard for the two-processor case when all jobs must be completed by their respective deadlines.
    0 references
    preemptive open-shop scheduling
    0 references
    m-machine open shop
    0 references
    optimal flow-time schedules
    0 references
    NP-hard
    0 references

    Identifiers