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))

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 corre...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Ojea, Ignacio
Publicado:	2017
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v78_n_p381_vanHoorn http://hdl.handle.net/20.500.12110/paper_03050548_v78_n_p381_vanHoorn
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03050548_v78_n_p381_vanHoorn
record_format	dspace
spelling	paper:paper_03050548_v78_n_p381_vanHoorn2023-06-08T15:30:26Z 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)) Ojea, Ignacio 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. © 2016 Elsevier Ltd Fil:Ojea, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v78_n_p381_vanHoorn http://hdl.handle.net/20.500.12110/paper_03050548_v78_n_p381_vanHoorn
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
description	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. © 2016 Elsevier Ltd
author	Ojea, Ignacio
spellingShingle	Ojea, Ignacio 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))
author_facet	Ojea, Ignacio
author_sort	Ojea, Ignacio
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))
title_short	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))
title_full	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))
title_fullStr	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))
title_full_unstemmed	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))
title_sort	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))
publishDate	2017
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v78_n_p381_vanHoorn http://hdl.handle.net/20.500.12110/paper_03050548_v78_n_p381_vanHoorn
work_keys_str_mv	AT ojeaignacio ancorrigendumonthepapersolvingthejobshopschedulingproblemoptimallybydynamicprogrammingcomputersandoperationsresearch2012391229682977s0305054812000500101016jcor201202024 AT ojeaignacio corrigendumonthepapersolvingthejobshopschedulingproblemoptimallybydynamicprogrammingcomputersandoperationsresearch2012391229682977s0305054812000500101016jcor201202024
_version_	1768543229319315456

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))

Ejemplares similares