A new lower bound for the job-shop scheduling problem (Q2366077): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q439606 |
||
Property / reviewed by | |||
Property / reviewed by: Irina N. Lushchakova / rank | |||
Revision as of 22:39, 14 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new lower bound for the job-shop scheduling problem |
scientific article |
Statements
A new lower bound for the job-shop scheduling problem (English)
0 references
29 June 1993
0 references
The best known exact algorithms for solving the general job-shop scheduling problem are branch-and-bound methods. A natural way to get lower bounds for branch-and-bound algorithms is to solve relaxations of the general job-shop problem. The classical method is based on one- machine relaxations. In the article a new lower bound is developed. This lower bound is based on a two-job relaxation which can be solved efficiently by using geometric methods. Computational experiments show that the new lower bound improves the one-machine relaxation bound if the ratio between the number of machines and the number of jobs is large.
0 references
shortest path
0 references
obstacles
0 references
job-shop scheduling
0 references
lower bounds
0 references
branch-and- bound algorithms
0 references