TY - JOUR
T1 - Solving the job-shop scheduling problem optimally by dynamic programming
AU - Gromicho Dos Santos, J.A.
AU - van Hoorn, J.J.
AU - Saldanha da Gama, F.
AU - Timmer, G.T.
PY - 2012
Y1 - 2012
N2 - Scheduling problems received substantial attention during the last decennia. The job-shop problem is a very important scheduling problem, which is NP-hard in the strong sense and with well-known benchmark instances of relatively small size which attest the practical difficulty in solving it. The literature on the job-shop scheduling problem includes several approximation and exact algorithms. So far, no algorithm is known which solves the job-shop scheduling problem optimally with a lower complexity than the exhaustive enumeration of all feasible solutions. We propose such an algorithm, based on the well-known Bellman equation designed by Held and Karp to find optimal sequences and which offers the best complexity to solve the Traveling Salesman Problem known to this date. For the TSP this means O(
AB - Scheduling problems received substantial attention during the last decennia. The job-shop problem is a very important scheduling problem, which is NP-hard in the strong sense and with well-known benchmark instances of relatively small size which attest the practical difficulty in solving it. The literature on the job-shop scheduling problem includes several approximation and exact algorithms. So far, no algorithm is known which solves the job-shop scheduling problem optimally with a lower complexity than the exhaustive enumeration of all feasible solutions. We propose such an algorithm, based on the well-known Bellman equation designed by Held and Karp to find optimal sequences and which offers the best complexity to solve the Traveling Salesman Problem known to this date. For the TSP this means O(
U2 - 10.1016/j.cor.2012.02.024
DO - 10.1016/j.cor.2012.02.024
M3 - Article
VL - 39
SP - 2968
EP - 2977
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
IS - 12
ER -
