Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. © 2016 Elsevier Ltd

Registro:

Documento: Artículo
Título: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))
Autor:van Hoorn, J.J.; Nogueira, A.; Ojea, I.; Gromicho, J.A.S.
Filiación:Department of Econometrics and OR, VU University, Amsterdam, Netherlands
ORTEC, Zoetermeer, Netherlands
Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Año:2017
Volumen:78
Página de inicio:381
DOI: http://dx.doi.org/10.1016/j.cor.2016.09.001
Título revista:Computers and Operations Research
Título revista abreviado:Comp. Oper. Res.
ISSN:03050548
CODEN:CMORA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v78_n_p381_vanHoorn

Referencias:

  • Gromicho, J., van Hoorn, J., Saldanha da, G.F., Timmer, G., Solving the job-shop scheduling problem optimally by dynamic programming (2012) Comput Oper Res, , http://dx.doi.org/10.1016/j.cor.2012.02.024
  • van Hoorn, J., Nogueira, A., Ojea, I., Gromicho, J., A note on the paper: solving the job-shop scheduling problem optimally by dynamic programming (2015) Research Memorandum 2015-9, , http://hdl.handle.net/1871/53531, Vrije Universiteit Amsterdam
  • van Hoorn, J., Dynamic programming for routing and scheduling: optimizing sequences of decisions (2016) Ph.D. thesis, , http://jobshop.jjvh.nl/dissertation, VU University Amsterdam

Citas:

---------- APA ----------
van Hoorn, J.J., Nogueira, A., Ojea, I. & Gromicho, J.A.S. (2017) . 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)). Computers and Operations Research, 78, 381.
http://dx.doi.org/10.1016/j.cor.2016.09.001
---------- CHICAGO ----------
van Hoorn, J.J., Nogueira, A., Ojea, I., Gromicho, J.A.S. "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))" . Computers and Operations Research 78 (2017) : 381.
http://dx.doi.org/10.1016/j.cor.2016.09.001
---------- MLA ----------
van Hoorn, J.J., Nogueira, A., Ojea, I., Gromicho, J.A.S. "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))" . Computers and Operations Research, vol. 78, 2017, pp. 381.
http://dx.doi.org/10.1016/j.cor.2016.09.001
---------- VANCOUVER ----------
van Hoorn, J.J., Nogueira, A., Ojea, I., Gromicho, J.A.S. 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)). Comp. Oper. Res. 2017;78:381.
http://dx.doi.org/10.1016/j.cor.2016.09.001