No label defined (Q4336213)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1008459
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1008459

      Statements

      22 April 1998
      0 references
      open shop
      0 references
      flow shop
      0 references
      job shop
      0 references
      super shop
      0 references
      makespan
      0 references
      precedence constraints
      0 references
      NP-hard
      0 references
      polynomial-time algorithms
      0 references
      0 references
      The paper considers a scheduling model that generalizes the well-known open shop, flow shop and job shop models. For that model, called the super shop, we study the complexity of minimizing the makespan in both preemptive and nonpreemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence constraints are considered. For the precedence relations of the first type, job \(J_i\) precedes job \(J_k\) if \(J_k\) may not start on any machine until \(J_i\) is completed on all machines. For the relations of the second type, job \(J_i\) precedes job \(J_k\) if \(J_k\) may not start on any machine until \(J_i\) is completed on that machines. Most of the studied problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented. For the entire collection see [Zbl 0861.00010].
      0 references

      Identifiers