Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops (Q4033755)

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 166199
Language Label Description Also known as
default for all languages
No label defined
    English
    Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops
    scientific article; zbMATH DE number 166199

      Statements

      Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops (English)
      0 references
      0 references
      0 references
      16 May 1993
      0 references
      fixed completion time
      0 references
      open shop
      0 references
      flow shop
      0 references
      mean job completion time
      0 references
      job preemption
      0 references
      polynomial algorithms
      0 references
      NP-hardness
      0 references
      The authors analyse two machine open shop and flow shop scheduling problems. The objective is to minimize the mean job completion time and job preemption is possible. Whereas these two problems on three machines are known to be NP-hard in the strong sense, the complexity status of the two machine problems has been unsolved. In this article, the authors prove that the two machine open shop problem is NP-hard in the ordinary sense and the flow shop problem is NP-hard in the strong sense. Moreover, for a fixed sequence of job completion times, polynomial algorithms are developed to compute the associated optimal schedule. The complexities of these two algorithms are \(O(n)\) for the open shop and \(O(n\cdot\log n)\) for the flow shop problem, respectively; here \(n\) denotes the number of jobs. It is interesting that the NP-hardness proof for the two machine flow shop problem provides an alternative proof for the NP-hardness (in the strong sense) of the associated non-preemptive problem.
      0 references

      Identifiers