| Article ID: | iaor19992316 |
| Country: | Netherlands |
| Volume: | 106 |
| Issue: | 1 |
| Start Page Number: | 95 |
| End Page Number: | 100 |
| Publication Date: | Apr 1998 |
| Journal: | European Journal of Operational Research |
| Authors: | Koulamas Christos |
| Keywords: | computational analysis |
The complexity of two-machine flowshop problems with due date related criteria is investigated. It is shown that when certain restrictions are imposed on the job processing times and their due dates these problems become polynomially solvable while when these restrictions are slightly weakened the problems remain NP-complete.