caa a22 4500 465774598 CHVBK 20180323111938.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF02248587 doi (NATIONALLICENCE)springer-10.1007/BF02248587 Steiner George Management Science and Information Systems Area, Faculty of Business, McMaster University, L8S 4M4, Hamilton, Ontario, Canada aut On the complexity of dynamic programming for sequencing problems with precedence constraints [Elektronische Daten] [George Steiner] Dynamic programming has been successfully used in the past to solve a large class of precedence constrained sequencing problems including for example, the assembly line balancing problem and the total tardiness problem on a single machine. The main limitation of this method has been the amount of storage required, which is directly related to the number of ideals in the precedence structure. In this paper, we present classes for which this number can be efficiently computed, enabling us to decide, in advance, whether the storage requirements of dynamic programming would be excessive for the problem. We develop regression equations based on large-scale computational experiments, which lead to surprisingly good approximations for the number of ideals. We also report on a computational study, comparing the relative effectiveness of various implementations of dynamic programming. A common theme throughout the paper is that the width of the precedence constraints plays the most important role in determining the storage requirements of dynamic programming for a sequencing problem. J.C. Baltzer AG, Scientific Publishing Company, 1990 Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 26/1(1990-12-01), 103-123 0254-5330 26:1<103 1990 26 10479 https://doi.org/10.1007/BF02248587 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02248587 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Steiner George Management Science and Information Systems Area, Faculty of Business, McMaster University, L8S 4M4, Hamilton, Ontario, Canada aut NATIONALLICENCE 773 0- Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 26/1(1990-12-01), 103-123 0254-5330 26:1<103 1990 26 10479 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer