nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

1. Introduction

verfasst von : Michael Z. Zgurovsky, Alexander A. Pavlov

Erschienen in: Combinatorial Optimization Problems in Planning and Decision Making

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We formulate the research problems which are a generalization of our earlier results in the field of intractable combinatorial optimization problems. On the basis of these problems, we have created a hierarchical model of planning and decision making for objects with a network representation of technological processes and limited resources (Chap. 9). We say that the problem is intractable if it is NP-hard (NP-hard in the strong sense) or such for which an exact polynomial time solution algorithm has not been yet obtained. To solve such problems efficiently, we developed a methodology of PSC-algorithms construction meaning the algorithms which necessarily include the following: sufficient conditions (signs) of a feasible solution optimality, verification of which can be implemented only at the stage of a feasible solution construction by a polynomial algorithm (the first polynomial component of the PSC-algorithm). The second polynomial component of the PSC-algorithm is an approximation algorithm with polynomial complexity. For NP-hard (NP-hard in the strong sense) combinatorial optimization problems, a PSC-algorithm may include an exact algorithm for its solving in case if sufficient conditions were found, satisfying of which during this algorithm execution turns it into a polynomial complexity algorithm (Chaps. 4 and 5). We also give a brief overview of the monograph’s chapters content.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Optimal Scheduling for Two Criteria for a Single Machine with Arbitrary Due Dates of Tasks

Zgurovsky, M.Z., Pavlov, A.A.: Prinyatie Resheniy v Setevyh Sistemah s Ogranichennymi Resursami (Пpинятиe peшeний в ceтeвыx cиcтeмax c oгpaничeнными pecypcaми; Decision Making in Network Systems with Limited Resources). Naukova dumka, Kyiv (2010) (in Russian)

Pavlov, A.A. (ed.): Konstruktivnye Polinomialnye Algoritmy Resheniya Individualnyh Zadach iz Klassa NP (Кoнcтpyктивныe пoлинoмиaльныe aлгopитмы peшeния индивидyaльныx зaдaч из клacca NP; Constructive Polynomial Algorithms for Solving Individual Problems from the Class NP). Tehnika, Kyiv (1993) (in Russian)

Pavlov, A.A., Pavlova, L.A.: PDC-algorithms for intractable combinatorial problems. Theory and methodology of design. “Karpatskij region” shelf #15, Uzhhorod (1998)

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co, San Francisco (1979). https://doi.org/10.1137/1024022CrossRef

Jain, A.S., Meeran, S.: Deterministic job-shop scheduling: past, present and future. Eur. J. Oper. Res. 113, 390–434 (1999). https://doi.org/10.1016/S0377-2217(98)00113-1CrossRefMATH

Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-26580-3CrossRef

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Logistics of Production and Inventory. Handbook in Operations Research and Management Science, vol. 4, pp. 445–522. North-Holland, Amsterdam (1993). https://doi.org/10.1016/s0927-0507(05)80189-6CrossRef

Fisher, H., Thompson, G.L.: Probabilistic learning combinations of local job-shop scheduling rules. In: Muth, J.F., Thompson, G.L. (eds.) Industrial Scheduling, pp. 225–251. Prentice-Hall, Englewood Cliffs (1963)

Lawrence, S.: Supplement to resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. GSIA, Carnegie-Mellon University, Pittsburgh (1984)

10.

Panwalkar, S.S., Iskander, W.: A survey of scheduling rules. Oper. Res. 25(1), 45–61 (1977). https://doi.org/10.1287/opre.25.1.45MathSciNetCrossRefMATH

11.

Grabot, B., Geneste, L.: Dispatching rules in scheduling: a fuzzy approach. Int. J. Prod. Res. 32(4), 903–915 (1994). https://doi.org/10.1080/00207549408956978CrossRefMATH

12.

Werner, F., Winkler, A.: Insertion techniques for the heuristic solution of the job-shop problem. Discrete Appl. Math. 58(2), 191–211 (1995). https://doi.org/10.1016/0166-218X(93)E0127-KMathSciNetCrossRefMATH

13.

Morton, T.E., Pentico, D.W.: Heuristic Scheduling Systems: With Applications to Production Systems and Project Management. Wiley, New York (1993)

14.

Sabuncuoglu, I., Bayiz, M.: A beam search based algorithm for the job shop scheduling problem. Research Report IEOR-9705. Bilkent University, Bilkent (1997)

15.

Fisher, M.L., Rinnooy Kan, A.H.G.: The design, analysis and implementation of heuristics. Manag. Sci. 34(3), 263–265 (1988). https://doi.org/10.1287/mnsc.34.3.263MathSciNetCrossRef

16.

Glover, F., Greenberg, H.J.: New approaches for heuristic search: a bilateral linkage with artificial intelligence. Eur. J. Oper. Res. 39(2), 119–130 (1989). https://doi.org/10.1016/0377-2217(89)90185-9MathSciNetCrossRefMATH

17.

Rodammer, F.A., White, K.P., Jr.: A recent survey of production scheduling. IEEE Trans. Syst. Man Cybern. 18(6), 841–851 (1988). https://doi.org/10.1109/21.23085MathSciNetCrossRef

18.

Sergienko, I.V., Kapitonova, Y.V., Lebedeva, T.T.: Informatika v Ukraine: Stanovlenie, Razvitie, Problemy (Инфopмaтикa в Укpaинe: cтaнoвлeниe, paзвитиe, пpoблeмы; Informatics in Ukraine: Formation, Development, Problems). Naukova dumka, Kyiv (1999) (in Russian)

19.

Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79–100 (1988). https://doi.org/10.1016/0022-0000(88)90046-3MathSciNetCrossRefMATH

20.

Yannakakis, M.: The analysis of local search problems and their heuristics. In: Choffrut, C., Lengauer, T. (eds.) STACS 90. Lecture Notes in Computer Science, vol. 415, pp. 298–311. Springer, Berlin (1990). https://doi.org/10.1007/3-540-52282-4_52CrossRef

21.

Sergienko, I.V.: O primenenii metoda vektora spada dlya resheniya zadach optimizacii kombinatornogo tipa (O пpимeнeнии мeтoдa вeктopa cпaдa для peшeния зaдaч oптимизaции кoмбинaтopнoгo типa; On the application of the recession vector method to solve optimization problems of combinatorial type). Upravlyayuschie sistemy i mashiny 2, 86–94 (1975) (in Russian)

22.

Bykov, A.Y., Artamonova, A.Y.: Modifikaciya metoda vektora spada dlya optimizacionno-imitacionnogo podhoda k zadacham proektirovaniya sistem zaschity informacii (Moдификaция мeтoдa вeктopa cпaдa для oптимизaциoннo-имитaциoннoгo пoдxoдa к зaдaчaм пpoeктиpoвaния cиcтeм зaщиты инфopмaции; A modified recession vector method based on the optimization-simulation approach to design problems of information security systems). Nauka i Obrazovanie of Bauman MSTU, vol. 1, pp. 158–175 (2015). https://doi.org/10.7463/0115.0754845 (in Russian)

23.

Shilo, V.P.: Metod globalnogo ravnovesnogo poiska (Meтoд глoбaльнoгo paвнoвecнoгo пoиcкa; Global equilibrium search method). Cybern. Syst. Anal. 35(1), 74–81 (1999) (in Russian)

24.

Adams, J., Balas, E., Zawack, D.: The shifting bottleneck procedure for job-shop scheduling. Manag. Sci. 34(3), 391–401 (1988). https://doi.org/10.1287/mnsc.34.3.391MathSciNetCrossRefMATH

25.

Balas, E., Lancia, G., Serafini, P., et al.: Job-shop scheduling with deadlines. J. Comb. Optim. 1(4), 329–353 (1998). https://doi.org/10.1023/A:1009750409895MathSciNetCrossRefMATH

26.

Balas, E., Vazacopoulos, A.: Guided local search with shifting bottleneck for job-shop scheduling. Manag. Sci. 44(2), 262–275 (1998). https://doi.org/10.1287/mnsc.44.2.262CrossRefMATH

27.

Caseau, Y., Laburthe, F.: Disjunctive scheduling with task intervals. LIENS Technical Report 95-25. Laboratoire d’Informatique de l’ Ecole Normale Superieure, Paris (1995)

28.

Demirkol, E., Mehta, S., Uzsoy, R.: A computational study of shifting bottleneck procedures for shop scheduling problems. J. Heuristics 3(2), 111–137 (1997). https://doi.org/10.1023/A:1009627429878CrossRefMATH

29.

Yamada, T., Nakano, R.: Job-shop scheduling by simulated annealing combined with deterministic local search. In: Osman, I.H., Kelly, J.P. (eds.) Meta-Heuristics: Theory and Applications, pp. 237–248. Springer, Boston (1996). https://doi.org/10.1007/978-1-4613-1361-8_15CrossRef

30.

Falkenauer, E., Bouffouix, S.: A genetic algorithm for job-shop. In: Proceedings of the IEEE International Conference on Robotics and Automation, Sacramento, 9–11 April 1991. https://doi.org/10.1109/robot.1991.131689

31.

Nakano, R., Yamada, T.: Conventional genetic algorithm for job-shop problems. In: Kenneth, M.K., Booker, L.B. (eds.) Proceedings of the 4th International Conference on Genetic Algorithms and their Applications, San Diego (1991)

32.

Aarts, E.H.L., Van Laarhooven, P.J.M., Ulder, N.L.J.: Local search based algorithms for job-shop scheduling. Working Paper. University of Technology, Eindhoven (1991)

33.

Dorndorf, U., Pesch, E.: Evolution based learning in a job-shop scheduling environment. Comp. Oper. Res. 22(1), 25–40 (1995). https://doi.org/10.1016/0305-0548(93)E0016-MCrossRefMATH

34.

Grefenstette, J.J.: Incorporating problem specific knowledge into genetic algorithms. In: Davis, L. (ed.) Genetic Algorithms and Simulated Annealing, pp. 42–60. Pitman, London (1987)

35.

Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. C3P Report 826: Caltech Concurrent Computation Program, Caltech (1989)

36.

Ulder, N.L.J., Aarts, E.H.L., Bandelt, H.-J., et al.: Genetic local search algorithm for the travelling salesman problem. Lect. Notes Comput. Sci. 496, 109–116 (1991)CrossRef

37.

Fox, M.S.: Constraint-directed search: a case study of job shop scheduling. Dissertation, Carnegy Mellon University, Pittsburgh (1983)

38.

Nuijten, W.P.M., Le Pape, C.: Constraint-based job-shop scheduling with ILOG SCHEDULER. J. Heuristics 3(4), 271–286 (1998). https://doi.org/10.1023/A:1009687210594CrossRefMATH

39.

Pesch, E., Tetzlaff, U.A.W.: Constraint propagation based scheduling of job shops. INFORMS J. Comput. 8(2), 144–157 (1996). https://doi.org/10.1287/ijoc.8.2.144CrossRefMATH

40.

Sadeh, N.: Look-ahead techniques for micro-opportunistic job shop scheduling. Dissertation, Carnegie Mellon University, Pittsburgh (1991)

41.

Foo, S.Y., Takefuji, Y.: Integer linear programming neural networks for job-shop scheduling. In: IEEE International Conference on Neural Networks, San Diego, 24–27 July 1988

42.

Foo, S.Y., Takefuji, Y.: Stochastic neural networks for solving job-shop scheduling: Part 1. problem representation. In: IEEE International Conference on Neural Networks, San Diego, 24–27 July 1988

43.

Foo, S.Y., Takefuji, Y.: Stochastic neural networks for solving job-shop scheduling: part 2. Architecture and simulations. IEEE International Conference on Neural Networks, San Diego, 24–27 July 1988

44.

Sabuncuoglu, I., Gurgun, B.: A neural network model for scheduling problems. Eur. J. Oper. Res. 93(2), 288–299 (1996). https://doi.org/10.1016/0377-2217(96)00041-0CrossRefMATH

45.

Zhou, D.N., Cherkassky, V., Baldwin, T.R., et al.: Scaling neural networks for job-shop scheduling. In: Proceedings of International Joint Conference on Neural Networks (IJCNN’90), San Diego, 17–21 June 1990, pp. 889–894. https://doi.org/10.1109/ijcnn.1990.137947

46.

Zhou, D.N., Cherkassky, V., Baldwin, T.R., et al.: A neural network approach to job-shop scheduling. IEEE Trans. Neural. Netw. 2(1), 175–179 (1991). https://doi.org/10.1109/72.80311CrossRef

47.

Dorigo, M.: Optimization, learning and natural algorithms. Dissertation, Politecnico di Milano (1992)

48.

Donati, A.V., Darley, V., Ramachandran, B.: An ant-bidding algorithm for multistage flowshop scheduling problem: optimization and phase transitions. In: Siarry, P., Michalewicz, Z. (eds.) Advances in Metaheuristics for Hard Optimization, pp. 111–136. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-72960-0_6

49.

Prabhakar, B., Dektar, K.N., Gordon, D.M.: The regulation of ant colony foraging activity without spatial information. PLoS Comput. Biol. 8(8), e1002670 (2012). https://doi.org/10.1371/journal.pcbi.1002670MathSciNetCrossRef

50.

Brucker, P., Hurink, J., Werner, F.: Improving local search heuristics for some scheduling problems—I. Discrete Appl. Math. 65(1–3), 97–122 (1996). https://doi.org/10.1016/0166-218X(95)00030-UMathSciNetCrossRefMATH

51.

Brucker, P., Hurink, J., Werner, F.: Improving local search heuristics for some scheduling problems. Part II. Discrete Appl. Math. 72(1–2), 47–69 (1997). https://doi.org/10.1016/S0166-218X(96)00036-4MathSciNetCrossRefMATH

52.

Lourenco, H.R.D.: A computational study of the job-shop and the flow-shop scheduling problems. Dissertation, Cornell University (1993)

53.

Lourenco, H.R.D.: Job-shop scheduling: computational study of local search and large-step optimization methods. Eur. J. Oper. Res. 83(2), 347–364 (1995). https://doi.org/10.1016/0377-2217(95)00012-FCrossRefMATH

54.

Lourenco, H.R.D., Zwijnenburg, M.: Combining the large-step optimization with tabu-search: Application to the job-shop scheduling problem. In: Osman, I.H., Kelly, J.P. (eds.) Meta-Heuristics: Theory and Applications, pp. 219–236. Springer, Boston (1996). https://doi.org/10.1007/978-1-4613-1361-8_14CrossRef

55.

Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for traveling salesman problem. Complex Syst. 5(3), 299–326 (1989)MathSciNetMATH

56.

Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for TSP incorporating local search heuristics. Oper. Res. Lett. 11(4), 219–224 (1992). https://doi.org/10.1016/0167-6377(92)90028-2MathSciNetCrossRefMATH

57.

Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986). https://doi.org/10.1016/0305-0548(86)90048-1MathSciNetCrossRefMATH

58.

Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156–166 (1977). https://doi.org/10.1111/j.1540-5915.1977.tb01074.xCrossRef

59.

Glover, F.: Tabu search—part I. ORSA J. Comput. 1(3), 190–206 (1989). https://doi.org/10.1287/ijoc.1.3.190CrossRefMATH

60.

Glover, F.: Tabu search—part II. ORSA J. Comput. 2(1), 4–32 (1990). https://doi.org/10.1287/ijoc.2.1.4CrossRefMATH

61.

Glover, F., Laguna, M.: Tabu Search. Springer, Boston (1997). https://doi.org/10.1007/978-1-4615-6089-0CrossRef

62.

Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job-shop problem. Manag. Sci. 42(6), 797–813 (1996). https://doi.org/10.1287/mnsc.42.6.797CrossRefMATH

63.

Taillard, E.: Parallel taboo search technique for the job-shop scheduling problem. Internal Research Report ORWP89/11. Ecole Polytechnique Federale de Lausanne, Lausanne (1989)

64.

Edelkamp, S., Schrödl, S.: Heuristic Search: Theory and Applications. Morgan Kaufmann Publishers, Waltham, MA (2012). https://doi.org/10.1016/c2009-0-16511-x

65.

Resende, M.G.C.: A GRASP for job shop scheduling. In: INFORMS National Meeting, pp. 23–31, San Diego, CA, 4–7 May 1997

66.

Matsuo, H., Suh, C.J., Sullivan, R.S.: A controlled search simulated annealing method for the general job-shop scheduling problem. Working Paper. University of Texas, Austin (1988)

67.

Van Laarhoven, P.J.M., Aarts, E.H.L., Lenstra, J.K.: Job-shop scheduling by simulated annealing. Report OS-R8809. Centrum voor Wiskunde en Informatica, Amsterdam (1988)

68.

Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)MATH

69.

Michel, L., Hentenryck, P.V.: Activity-based search for black-box constraint programming solvers. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2012. Lecture Notes in Computer Science, vol. 7298, pp. 228–243. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-29828-8_15CrossRef

70.

Schulte, C., Tack, G., Lagerkvist, M.Z.: Modeling and programming with Gecode. http://www.gecode.org/doc-latest/MPG.pdf (2018). Accessed 02 Apr 2018.

71.

Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009). https://doi.org/10.1017/cbo9780511801655

72.

Pavlov, A.A. (ed.): Osnovy Sistemnogo Analiza i Proektirovaniya ASU (Ocнoвы cиcтeмнoгo aнaлизa и пpoeктиpoвaния ACУ; Fundamentals of System Analysis and Design of Automated Control Systems). Vyshcha Shkola, Kyiv (1991) (in Russian)

Titel: Introduction
verfasst von: Michael Z. Zgurovsky
Alexander A. Pavlov
Verlag: Springer International Publishing
Buch: Combinatorial Optimization Problems in Planning and Decision Making
Print ISBN: 978-3-319-98976-1

Electronic ISBN: 978-3-319-98977-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-319-98977-8_1

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner

Marktübersichten