| Article ID: | iaor19961178 |
| Country: | Netherlands |
| Volume: | 64 |
| Issue: | 2 |
| Start Page Number: | 156 |
| End Page Number: | 167 |
| Publication Date: | Jan 1993 |
| Journal: | European Journal of Operational Research |
| Authors: | Brucker Peter, Jurisch Bernd |
| Keywords: | job shop |
A new lower bound for the job-shop scheduling problem is developed. This lower bound is based on a two-job relaxation which can be solved efficiently by using geometeric methods. Computational experiments show that the new lower bound improves the classical lower bound if the ratio between the number of machines and the number of jobs is large.