An corrigendum on the paper: Solving the job-shop scheduling problem optimally by dynamic programming (Computers and Operations Research (2012) 39(12) (2968–2977) (S0305054812000500) (10.1016/j.cor.2012.02.024))

Jelke J. van Hoorn, Agustín Nogueira, Ignacio Ojea, Joaquim Antonio Gromicho Dos Santos

Research output: Contribution to JournalErratumAcademic

Abstract

In [1] an algorithm is proposed for solving the job-shop scheduling problem optimally using a dynamic programming strategy. This is, according to our knowledge, the first exact algorithm for the Job Shop problem which is not based on integer linear programming and branch and bound. Despite the correctness of the dynamic programming algorithm presented in [1], the proof of correctness given there is unfortunately flawed. The contribution of the present note is to point out that flaw, and refer the reader to [2], where the flaw is corrected. Particularly, in [2], we recall the main idea of the proof proposed in [1] and present a counterexample that shows where the problem of that proof lies. Taking into account the nature of the problem, we propose a new approach for proving the correctness of the algorithm. This requires the introduction of new concepts and notation. It is important to remark that the new proof modifies our understanding of the algorithm that, in fact, works in a different way than the one explained in the original article. We also recommend [3], where all the elements for understanding the algorithm, the new proof of its correctness and the estimations of its complexity are fully developed.

Original languageEnglish
Pages (from-to)381
Number of pages1
JournalComputers and Operations Research
Volume78
DOIs
Publication statusPublished - 1 Feb 2017

Fingerprint

Operations research
Job Shop Scheduling Problem
Operations Research
Dynamic programming
Dynamic Programming
Proof of correctness
Correctness
Job Shop
Integer Linear Programming
Branch-and-bound
Exact Algorithms
Defects
Notation
Counterexample
Linear programming
Job shop scheduling

Cite this

@article{7f958525e4a2433dbf5a6a08ef3f1b25,
title = "An corrigendum on the paper: Solving the job-shop scheduling problem optimally by dynamic programming (Computers and Operations Research (2012) 39(12) (2968–2977) (S0305054812000500) (10.1016/j.cor.2012.02.024))",
abstract = "In [1] an algorithm is proposed for solving the job-shop scheduling problem optimally using a dynamic programming strategy. This is, according to our knowledge, the first exact algorithm for the Job Shop problem which is not based on integer linear programming and branch and bound. Despite the correctness of the dynamic programming algorithm presented in [1], the proof of correctness given there is unfortunately flawed. The contribution of the present note is to point out that flaw, and refer the reader to [2], where the flaw is corrected. Particularly, in [2], we recall the main idea of the proof proposed in [1] and present a counterexample that shows where the problem of that proof lies. Taking into account the nature of the problem, we propose a new approach for proving the correctness of the algorithm. This requires the introduction of new concepts and notation. It is important to remark that the new proof modifies our understanding of the algorithm that, in fact, works in a different way than the one explained in the original article. We also recommend [3], where all the elements for understanding the algorithm, the new proof of its correctness and the estimations of its complexity are fully developed.",
author = "{van Hoorn}, {Jelke J.} and Agust{\'i}n Nogueira and Ignacio Ojea and {Gromicho Dos Santos}, {Joaquim Antonio}",
year = "2017",
month = "2",
day = "1",
doi = "10.1016/j.cor.2016.09.001",
language = "English",
volume = "78",
pages = "381",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Limited",

}

TY - JOUR

T1 - An corrigendum on the paper

T2 - Solving the job-shop scheduling problem optimally by dynamic programming (Computers and Operations Research (2012) 39(12) (2968–2977) (S0305054812000500) (10.1016/j.cor.2012.02.024))

AU - van Hoorn, Jelke J.

AU - Nogueira, Agustín

AU - Ojea, Ignacio

AU - Gromicho Dos Santos, Joaquim Antonio

PY - 2017/2/1

Y1 - 2017/2/1

N2 - In [1] an algorithm is proposed for solving the job-shop scheduling problem optimally using a dynamic programming strategy. This is, according to our knowledge, the first exact algorithm for the Job Shop problem which is not based on integer linear programming and branch and bound. Despite the correctness of the dynamic programming algorithm presented in [1], the proof of correctness given there is unfortunately flawed. The contribution of the present note is to point out that flaw, and refer the reader to [2], where the flaw is corrected. Particularly, in [2], we recall the main idea of the proof proposed in [1] and present a counterexample that shows where the problem of that proof lies. Taking into account the nature of the problem, we propose a new approach for proving the correctness of the algorithm. This requires the introduction of new concepts and notation. It is important to remark that the new proof modifies our understanding of the algorithm that, in fact, works in a different way than the one explained in the original article. We also recommend [3], where all the elements for understanding the algorithm, the new proof of its correctness and the estimations of its complexity are fully developed.

AB - In [1] an algorithm is proposed for solving the job-shop scheduling problem optimally using a dynamic programming strategy. This is, according to our knowledge, the first exact algorithm for the Job Shop problem which is not based on integer linear programming and branch and bound. Despite the correctness of the dynamic programming algorithm presented in [1], the proof of correctness given there is unfortunately flawed. The contribution of the present note is to point out that flaw, and refer the reader to [2], where the flaw is corrected. Particularly, in [2], we recall the main idea of the proof proposed in [1] and present a counterexample that shows where the problem of that proof lies. Taking into account the nature of the problem, we propose a new approach for proving the correctness of the algorithm. This requires the introduction of new concepts and notation. It is important to remark that the new proof modifies our understanding of the algorithm that, in fact, works in a different way than the one explained in the original article. We also recommend [3], where all the elements for understanding the algorithm, the new proof of its correctness and the estimations of its complexity are fully developed.

UR - http://www.scopus.com/inward/record.url?scp=85006990679&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85006990679&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2016.09.001

DO - 10.1016/j.cor.2016.09.001

M3 - Erratum

VL - 78

SP - 381

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -