| Article ID: | iaor20101578 |
| Volume: | 13 |
| Issue: | 1 |
| Start Page Number: | 3 |
| End Page Number: | 16 |
| Publication Date: | Feb 2010 |
| Journal: | Journal of Scheduling |
| Authors: | Yang Jaehwan, Posner Marc E |
| Keywords: | flowshop |
A new deterministic flow shop problem is studied where the objective is to minimize the total WIP (work-in-process) 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.