Article ID: | iaor2005174 |
Country: | Netherlands |
Volume: | 90 |
Issue: | 3 |
Start Page Number: | 421 |
End Page Number: | 434 |
Publication Date: | Jan 2004 |
Journal: | International Journal of Production Economics |
Authors: | Cheng T.C. Edwin, Yeung W.K., Ceyda Ouz |
This paper studies a non-preemptive two-stage flowshop scheduling problem to minimize the earliness and tardiness under the environment of a common due window. The window size and the window location are considered to be given parameters. The just-in-time problem exists naturally and has many practical applications. The problem is shown to be NP-complete in the strong sense. We develop a branch and bound algorithm and a heuristic to solve the problems. We conduct the computational experiments to test the performances of the algorithm. A strong lower bound is derived for the branch and bound algorithm that can efficiently solve 15 jobs problem for about 5 minutes. The heuristic is shown to be efficient and effective, which can solve the problem of 150 jobs for about 20 seconds and provide near-optimal solution. We justify that the heuristic is an excellent solution approach for large problem instances. We also show that four special cases are either polynomial solvable or NP-complete in the ordinary sense.