SS15 M INIMUM F LOW -S HOP S CHEDULING

   
• I NSTANCE : Number of processors, set J of jobs, each consisting of m operations with (with to be executed by processor i ), and for each operation a length .
• S OLUTION : An open-shop schedule for J (see M INIMUM O PEN -S HOP S CHEDULING ) such that, for each and , .
• M EASURE : The completion time of the schedule, i.e., .

• Good News: Approximable within m/2 if m is even and within m/2 + 1/6 if m is odd [ 68 ].
• Bad News: Not approximable within 5/4 for any [ 345 ].
• Comment: Approximable within 5/3 if m=3 [ 68 ]. Variation in which m=2 , but the two processors are replaced by respectively and identical parallel processors, is approximable within [ 67 ].
• Garey and Johnson: SS15