Special cases on two machine flow shop scheduling with weighted WIP (work-in-progress) costs

Special cases on two machine flow shop scheduling with weighted WIP (work-in-progress) costs

0.00 Avg rating0 Votes
Article ID: iaor20103018
Volume: 15
Issue: 2
Start Page Number: 31
End Page Number: 40
Publication Date: Jun 2009
Journal: International Journal of Management Science
Authors:
Keywords: flowshop
Abstract:

In this paper, we consider a relatively new two-machine flow shop scheduling problem where the unit time WIP cost increases as a job passes through various stages in the production process, and the objective is to minimize the total WIP (work-in-process) cost. Specifically, we study three special cases of the problem. First, we consider the problem where processing times on machine 1 are identical. Second, the problem with identical processing times on machine 2 is examined. The recognition version of the both problems is unary NP-complete (or NP-complete in strong sense). For each problem, we suggest two simple and intuitive heuristics and find the worst case bound on relative error. Third, we consider the problem where the processing time of a job on each machine is proportional to a base processing time. For this problem, we show that a known heuristic finds an optimal schedule.

Reviews

Required fields are marked *. Your email address will not be published.