Article ID: | iaor20083048 |
Country: | United Kingdom |
Volume: | 10 |
Issue: | 4/5 |
Start Page Number: | 237 |
End Page Number: | 243 |
Publication Date: | Oct 2007 |
Journal: | Journal of Scheduling |
Authors: | Yoon Suk-Hun, Choi Byung-Cheon |
Keywords: | production: JIT |
In this paper we consider the maximization of the weighted number of just-in-time jobs that should be completed exactly on their due dates in n-job, m-machine flow shop problems. We show that a two-machine flow shop problem is NP-complete. When job weights are all identical, we show that the problem can be solved in polynomial time. We also show that a three-machine flow shop problem with identical job weights is NP-hard in the strong sense by reduction of the 3-partition problem.