Solving the job-shop scheduling problem optimally by dynamic programming

J.A. Gromicho Dos Santos, J.J. van Hoorn, F. Saldanha da Gama, G.T. Timmer

Research output: Contribution to JournalArticleAcademicpeer-review


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(
Original languageEnglish
Pages (from-to)2968-2977
JournalComputers and Operations Research
Issue number12
Early online date3 Aug 2012
Publication statusPublished - 2012


Dive into the research topics of 'Solving the job-shop scheduling problem optimally by dynamic programming'. Together they form a unique fingerprint.

Cite this