Flow shops with WIP and value added costs

A new deterministic flow shop problem is studied where the objective is to minimize the total WIP (work-inprocess) cost. Based on a value added model, the unit time WIP cost increases as a job passes through various stages in the production process. The recognition version is unary NP-Complete even for two machines. Several simple and intuitive heuristics are presented. For each heuristic, we determine asymptotically attainable upper bounds on the relative error. Finally, the heuristics are empirically evaluated.