Skip to main content
SpringerLink
Log in

Discrete Optimization in the Industrial Computer Science

  • Chapter
  • First Online:
Automatic Control, Robotics, and Information Processing

Part of the book series: Studies in Systems, Decision and Control ((SSDC,volume 296))

  • 530 Accesses

Abstract

In the work there is presented a comprehensive overview of scientific and research directions accomplished by the Author and cooperating team in recent years. The team is working in the area of modeling and optimization dedicated for the implementation in discrete manufacturing systems, transport systems, warehousing systems etc. The immediate result of the these research is the original uniform approach to design of various algorithms for problems derived from the industry. Foundations of the approach combine not only graphs, operations research, combinatorial optimization, mathematical programming, but also modern solution technologies and powerful computing tools. In the review there are discussed general technologies of discrete processes modeling as well as the evolution of solving methods in the recent fifty years. There are some selected fundamental discrete optimization problems discussed in relation to the landscape of the solution space. There are also collected the main theoretical results obtained by the Author, his leading publications as well as the spectacular algorithms developed so far. The future research directions are also outlined. The presentation is illustrated by references to papers of the Author and the bibliography of collaborators.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 199.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 199.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Space diameter is the maximal distance between any two solutions.

References

  1. Amdahl, G.M.: Validity of the single processor approach to achieving large-scale computing capabilities. AFIPS Conf. Proc. 483–485 (1967). https://doi.org/10.1145/1465482.1465560

  2. Barták, R., Salido, M.A., Rossi, F.: Constraint satisfaction techniques in planning and scheduling. J. Intell. Manuf. 21(1), 5–15 (2010)

    Article  Google Scholar 

  3. Błażewicz, J., Domschke, W., Pesch, E.: The job shop scheduling problem: conventional and new solution techniques. Eur. J. Oper. Res. 93(1), 1–33 (1996)

    Article  Google Scholar 

  4. Bocewicz, G., Wójcik, R., Banaszak, Z.: Cyclic scheduling of multimodal concurrently flowing processes. In: Świa̧tek J. et al. (eds.) Advances in Systems Science, pp. 587–598. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-01857-7_57

  5. Bożejko W., Pempera J., Smutnicki C.: Parallel simulated annealing for the job shop scheduling problem. In: Allen, G. et al. (eds.) ICCS 2009, Part I, Lecture Notes in Computer Science 5544, pp. 631–40 (2009)

    Google Scholar 

  6. Bożejko, W., Pempera, J., Smutnicki, C.: Parallel tabu search algorithm for the hybrid flow shop problem. Comput. Ind. Eng. 65(3), 466–474 (2013)

    Article  Google Scholar 

  7. Bożejko, W., Jagiełło, S., Lower, M., Smutnicki, C.: On underwater vehicle routing problem. In: Moreno-Diaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) Computer Aided Systems Theory EUROCAST 2015. Lecture Notes in Computer Science, vol. 9520, pp. 861–868. Springer, Cham (2015)

    Google Scholar 

  8. Bożejko, W., Smutnicki, C., Wodecki, M.: Metropolitan delivery with time windows as a scheduling problem. In: Koukol, M. (ed.) Smart Cities Symposium, Prague (SCSP), pp. 1–5. Piscataway, NJ, IEEE (2016)

    Google Scholar 

  9. Brucker, P., Kampmeyer, T.: Cyclic job shop scheduling problems with blocking. Ann. Oper. Res. 159, 161–181 (2008)

    Article  MathSciNet  Google Scholar 

  10. Brucker, P., Jurish, B., Sieviers, B.: A fast branch and bound algorithm for the job shop problem. Discret. Appl. Math. 49, 107–127 (1994)

    Article  Google Scholar 

  11. Buzzone A., Laboratories of Simulation, http://www.itim.unige.it/

  12. EC Bestiary http://conclave.cs.tsukuba.ac.jp/research/bestiary/ (2017)

  13. Filipowicz, B.: Modele stochastyczne w badaniach operacyjnych (Polish). WNT, Warszawa (1996)

    Google Scholar 

  14. Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Norwell (1997)

    Google Scholar 

  15. Gnatowski, A., Smutnicki, C., Wodecki, M.: Wykorzystanie własności krajobrazu przestrzeni rozwiązań w konstrukcji algorytmów etaheurystycznych (Polish). In: 1st International Conference on Decision Making in Manufacturing and Services & XX Jubilee Symposium on Applications of Systems Theory, DMMS 2017 & ZTS XX, Conference Proceedings, Zakopane 2017, pp. 209–214 (2017)

    Google Scholar 

  16. Grabowski, J., Nowicki, E., Smutnicki, C.: Algorytm blokowy szeregowania operacji w systemie gniazdowym (Polish), Przegląd Statystyczny 35(1), 67–80 (1988)

    Google Scholar 

  17. Grabowski, J., Nowicki, E., Smutnicki, C.: Metoda blokowa w zagadnieniach szeregowania zadań (Polish). Akademicka Oficyna Wydawnicza EXIT, Warszawa (2003)

    Google Scholar 

  18. Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 87–326 (1979)

    MathSciNet  MATH  Google Scholar 

  19. Gustafson, J.L.: Reevaluating Amdahl’s Law. Commun. ACM 31(5), 532–3 (1988). https://doi.org/10.1145/42411.42415

    Article  Google Scholar 

  20. Jain, A.S., Meeran, S.: Deterministic job-shop scheduling: past, present and future. Eur. J. Oper. Res. 113, 390–434 (1999)

    Article  Google Scholar 

  21. Jain, A.S., Rangaswamy, B., Meeran, S.: New and stronger job-shop neighbourhoods: a focus on the method of Nowicki and Smutnicki (1996). J. Heuristics 6(4), 457–480 (2000)

    Article  Google Scholar 

  22. Kampmeyer, T.: Cyclic scheduling problems, Ph.D. thesis, Osnabrück University (2006)

    Google Scholar 

  23. Kowalczuk, Z., Białaszewski, T.: Approximate criteria for the evaluation of truly multi-dimensional optimization problems. In: MMAR Conference (2018)

    Google Scholar 

  24. Nowicki, E., Smutnicki, C.: Worst-case analysis of an approximation algorithm for flow-shop scheduling. Oper. Res. Lett. 8(3), 171–177 (1989)

    Article  MathSciNet  Google Scholar 

  25. Nowicki, E., Smutnicki, C.: Worst-case analysis of Dannenbring’s algorithm for flow-shop scheduling. Oper. Res. Lett. 10(8), 473–480 (1991)

    Article  MathSciNet  Google Scholar 

  26. Nowicki, E., Smutnicki, C.: New results in the worst-case analysis for flow-shop scheduling. Discret. Appl. Math. 46(1), 21–41 (1993)

    Article  MathSciNet  Google Scholar 

  27. Nowicki, E., Smutnicki, C.: An approximation algorithm for a single-machine scheduling problem with release times and delivery times. Discret. Appl. Math. 48(1), 69–79 (1994)

    Article  MathSciNet  Google Scholar 

  28. Nowicki, E., Smutnicki, C.: A decision support system for the resource constrained project scheduling problem. Eur. J. Oper. Res. 79(2), 183–195 (1994)

    Article  Google Scholar 

  29. Nowicki, E., Smutnicki, C.: A note on worst-case analysis of approximation algorithms for a scheduling problem. Eur. J. Oper. Res. 74(1), 128–134 (1994)

    Article  Google Scholar 

  30. Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job shop problem. Manag. Sci. 42(6), 797–813 (1996)

    Article  Google Scholar 

  31. Nowicki, E., Smutnicki, C.: A fast tabu search algorithm for the permutation flow-shop problem. Eur. J. Oper. Res. 91(1), 160–175 (1996)

    Article  Google Scholar 

  32. Nowicki, E., Smutnicki, C.: The flow shop with parallel machines: a tabu search approach. Eur. J. Oper. Res. 106(2–3), 226–253 (1998)

    Article  Google Scholar 

  33. Nowicki, E., Smutnicki, C.: Flow line scheduling by tabu search. In: Meta-Heuristics, pp. 175–189. Springer, Boston, MA (1999)

    Google Scholar 

  34. Nowicki, E., Smutnicki, C.: 2D and 3D representations of solution spaces for CO problems. In: International Conference on Computational Science, pp. 483–490. Springer, Berlin, Heidelberg (2004)

    Google Scholar 

  35. Nowicki, E., Smutnicki, C.: Some new ideas in TS for job shop scheduling. In: Metaheuristic Optimization via Memory and Evolution, pp. 165–190. Springer, Boston, MA (2005)

    Google Scholar 

  36. Nowicki, E., Smutnicki, C.: An advanced tabu search algorithm for the job shop problem. J. Sched. 8(2), 145–159 (2005)

    Article  MathSciNet  Google Scholar 

  37. Nowicki, E., Smutnicki, C.: Some aspects of scatter search in the flow-shop problem. Eur. J. Oper. Res. 169(2), 654–666 (2006)

    Article  MathSciNet  Google Scholar 

  38. Pempera, J., Smutnicki, C., Żelazny, D.: Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm. Procedia Comput. Sci. 18, 936–945 (2013)

    Article  Google Scholar 

  39. Pempera, J., Smutnicki, C.: Open shop cyclic scheduling. Eur. J. Oper. Res. 269(2), 773–781 (2018)

    Article  MathSciNet  Google Scholar 

  40. Rudy, J., Bożejko, W.: (2018) Reversed Amdahl’s Law for Hybrid Parallel Computing. In: Moreno-Diaz, R., Pichler, F. Quesada-Arencibia, A. (eds) Computer Aided Systems Theory, EUROCAST, : Lecture Notes in Computer Science, 10671. Springer, Cham (2017)

    Google Scholar 

  41. Siedlecki, W., Siedlecka, K., Sklansky, J.: An overview of mapping techniques for exploratory pattern analysis. Pattern Recogn. 21(5), 411–429 (1988)

    Article  MathSciNet  Google Scholar 

  42. Smutnicki, C.: Some results of the worst-case analysis for flow shop scheduling. Eur. J. Oper. Res. 109(1), 66–87 (1998)

    Article  Google Scholar 

  43. Smutnicki, C.: A two-machine permutation flow shop scheduling problem with buffers. Oper. Res. Spekt. 20(4), 229–235 (1998)

    Article  MathSciNet  Google Scholar 

  44. Smutnicki, C.: Algorytmy szeregowania (Polish). Akademicka Oficyna Wydawnicza EXIT, Warszawa (2002)

    Google Scholar 

  45. Smutnicki, C.: Efektywność algorytmów poszukiwań lokalnych a struktura przestrzeni rozwia̧zań (Polish). In: Greblicki, W., Smutnicki, C. (eds.) Systemy sterowania. WKiŁ, Warszawa (2005)

    Google Scholar 

  46. Smutnicki C.: Optimization technologies for hard problems. In: Janos, F., Klempous, R., Paz Suarez Araujo, C. (eds.) Recent Advances in Intelligent Engineering Systems, pp. 79–104. Springer, Berlin; Heidelberg (2011)

    Google Scholar 

  47. Smutnicki, C.: An efficient algorithm for finding minimal cycle time in cyclic job shop scheduling problem. IEEE 2012, 381–386 (2011)

    Google Scholar 

  48. Smutnicki, C.: Metody optymalizacji dyskretnej (Polish). In: Bożejko, W., Pempera, J. (eds.) Optymalizacja dyskretna w informatyce, automatyce i robotyce. Oficyna Wydawnicza PWr, Wrocław (2012)

    Google Scholar 

  49. Smutnicki, C.: Problemy kolekcjonowania (Polish). In: Bożejko, W., Pempera, J. (eds.) Optymalizacja dyskretna w informatyce, automatyce i robotyce. Oficyna Wydawnicza PWr, Wrocław (2012)

    Google Scholar 

  50. Smutnicki, C., Rudy, J., Żelazny, D.: Very fast non-dominated sorting. Decis. Making Manuf. Serv. 8(1–2), 13–23 (2014)

    MathSciNet  MATH  Google Scholar 

  51. Smutnicki, C.: New features of the cyclic job shop scheduling problem. In: MMAR 2015, pp. 1000–1005. IEEE (2015)

    Google Scholar 

  52. Smutnicki, C.: Optimization in CIS systems. In: Zamojski, W., Sugier, J. (eds.) Dependability Problems of Complex Information Systems, Advances in Intelligent Systems and Computing, Springer, vol. 307, pp. 111–128 (2015)

    Google Scholar 

  53. Smutnicki, C., Pempera, J., Rudy, J., Żelazny, D.: A new approach for multi-criteria scheduling. Comput. Ind. Eng. 90, 212–220 (2015)

    Article  Google Scholar 

  54. Smutnicki, C., Bożejko, W.: Parallel and distributed metaheuristics. In: Moreno-Diaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) Computer Aided Systems Theory, EUROCAST 2015. Lecture Notes in Computer Science, vol. 9520, pp. 72–79. Springer, Cham (2015)

    Google Scholar 

  55. Smutnicki, C.: Algorytmy szeregowania zadań (Polish). Oficyna Wydawnicza PWr, Wrocław (2017)

    Google Scholar 

  56. Smutnicki, C.: Cykliczny problem gniazdowy (Polish). In: Bożejko, W., Pempera, J., Smutnicki, C., Wodecki, M. (eds.) Zaawansowane modele i algorytmy optymalizacji w systemach cyklicznych. EXIT, Warszawa (2017)

    Google Scholar 

  57. Smutnicki, C.: Minimizing cycle time in manufacturing systems with additional technological constraints. In: MMAR 2017, pp. 463–470. IEEE (2017)

    Google Scholar 

  58. Smutnicki, C.: Cyclic Scheduling in interlaced and non-interlaced mode. In: MMAR (2018)

    Google Scholar 

  59. Smutnicki, C., Bożejko, W.: Tabu Search and solution space analyses. The job shop case. In: Moreno-Diaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) Computer Aided Systems Theory, EUROCAST 2017. Lecture Notes in Computer Science, vol. 10671, pp. 383–391. Springer, Cham (2017)

    Google Scholar 

  60. Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64, 278–285 (1993)

    Article  Google Scholar 

  61. Valenzuela, M.L., Rozenblit, J.W.: Learning using anti-training with sacrificial dat. J. Mach. Learn. Res. 1–42 (2016)

    Google Scholar 

  62. Watson, J.P., Beck, J.C., Howe, A.E., Whitley, L.D.: Problem difficulty for tabu search in job-shop scheduling. Artif. Intell. 143, 189–217 (2003)

    Article  MathSciNet  Google Scholar 

  63. Watson, J.P., Howe, A.E., Whitley, L.D.: Deconstructing Nowicki and Smutnicki’s i-TSAB tabu search algorithm for the job-shop scheduling problem. Comput. Oper. Res. 33(9), 2623–2644 (2006)

    Article  Google Scholar 

  64. Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67–82 (1997)

    Article  Google Scholar 

  65. Zhou, M., Venkatesh, K.: Modeling, Simulation, and Control of Flexible Manufacturing Systems: A Petri Net Approach. World Scientific (1999)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Electronics, Wrocław University of Science and Technology, 50-370 Wrocław, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

    Czesław Smutnicki

Authors
  1. Czesław Smutnicki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Czesław Smutnicki .

Editor information

Editors and Affiliations

  1. Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

    Piotr Kulczycki

  2. Institute of Control and Computation Engineering, University of Zielona Góra, Zielona Góra, Poland

    Józef Korbicz

  3. Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

    Janusz Kacprzyk

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Smutnicki, C. (2021). Discrete Optimization in the Industrial Computer Science. In: Kulczycki, P., Korbicz, J., Kacprzyk, J. (eds) Automatic Control, Robotics, and Information Processing. Studies in Systems, Decision and Control, vol 296. Springer, Cham. https://doi.org/10.1007/978-3-030-48587-0_12

Download citation

Publish with us

Policies and ethics

Search

Navigation