Scheduling

A 3/2-Approximation algorithm for two-machine flow-shop sequencing subject to release dates

  • C.N. Potts
  • S.V. Sevastianov
    • Categories Scheduling

    The two-machine flow shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best known approximation algorithms are those of Potts (1985) with a worst-case performance ratio of 5/3 and running time $O(n^3 \log n)$, and a polynomial time approximation … Read more

    Geometrical Heuristics for Multiprocessor Flowshop Scheduling with Uniform Machines at Each Stage

  • S.V. Sevastianov
    • Categories Scheduling Tags , , ,

    We consider the multi-stage multiprocessor flowshop scheduling problem with uniform machines at each stage and the minimum makespan objective. Using a vector summation technique, three polynomial-time heuristics are developed with absolute worst-case performance guarantees. As a direct corollary, in the special case of the ordinary flowshop problem we come to the best approximation algorithms (both … Read more