It depends on the context.

For the standard term "flow shop", the complexity maybe refers to the scheduling problem. However, when considering other factors, e.g. choice complexity, it turns to others.

Ref :

http://www.researchgate.net/publication/235978030_Modeling_impact_of_choice_complexity_on_production_rate_in_mixed-model_assembly_system

Article Modeling impact of choice complexity on production rate in m...

F2||Csum is NP-complete, you may want to check the paper by Lenstra et al. (1977).

http://oai.cwi.nl/oai/asset/18051/18051A.pdf

Dear Tsung,

Thanks for your answer. I know the problem is NP complete. Do you know any pseudo polynomial algorithm or polynomial approx. algorithm for this problem

Hi Palakiti, I am sorry that I am not familiar with exact algorithms. Do heuristics (e.g., the NEH heuristic for PFSP) or metaheuristics (e.g. GA) fit your definition of "polynomial approx. algorithm"?

Thanks...

I am looking into reducing bottlenecks in a flow shop setting. A heuristic for flow optimisation is the shifting bottleneck heuristic. http://en.wikipedia.org/wiki/Shifting_bottleneck_heuristic