DOI: https://doi.org/10.20535/SRIT.2308-8893.2020.1.09

Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах

Yuriy O. Zack

Анотація


Класичне в теорії розкладів завдання побудови послідовності виконання завдань на одній машині, що враховує не тільки витрати часу на роботу обладнання, а й на постоброблення, розглядається для багатостадійних виробничих систем, що складається із взаємозалежного ланцюжка ділянок і цехів промислового підприємства. Як критерій оптимальності розглядається виконання багатостадійного розкладу в найкоротшітерміни. Запропоновано методи розрахунку нижньої межі довжини оптимального розкладу і евристичні алгоритми отримання наближених розв’язків, що потребують невеликих обсягів обчислень. Запропоновані алгоритми ілюструються числовими прикладами.

Ключові слова


послідовності виконання завдань; багатостадійні розклади; мінімальний час; евристичний алгоритм; нижня межа значення критерію оптимальності

Повний текст:

PDF (Русский)

Посилання


Conway R.W. Theory of Scheduling / R.W. Conway, W.L. Maxwell, L.W. Miller. — Addison-Wesley Publishing Company, 1967. — 294 p.

Zack Yu.A. Applied problems of the theory of scheduling and traffic routing [in Russian] / Yu.A. Zack. — M., URSS, 2012. — 394 p.

Zgurovsky M.Z. Decision making in networked systems with limited resources [in Russian] / M.Z. Zgurovsky, A.A. Pavlov. — K.:. Nauk. dumka, 2010. — 573 p.

Zack Yu.A. Construction of two-stage schedules of processing of products on one machine / Yu.A. Zack // System research and information technologies. — 2018. — № 4. — P. 19–36.

Zack Yu.A. Developing admissible and optimal schedules of works on one machine / Yu.A. Zack // Cybernetics and systems analysis. — № 1. — 2012.

Zak Yu.A. Two-stage planning tasks for the flow line / Yu.A. Zak // Control Sciences. — M., 2019. — № 6. — P. 52–62.

Zack Yu.A. Algorithms for approximate multi-stage Flow-Shop-Problem solution / Yu.A. Zack // System research and information technologies. — 2019. — № 3. — P. 100–109.

Carlier J. The one-machine sequencing problem / J. Carlier // European Journal of Operational Research. — 1982. — N 11. — P. 42–47.

Domschke W. Produktionsplanung. Ablauforganisatorische Aspekte / W. Domschke, A. Scholl, S. Voß. — Berlin, Heidelberg: Springer Verlag, 2005. — 456 p.

Brucker P. Scheduling Algorithms / P. Brucker // Springer-Verlag, Berlin, Heidelberg und New York, 1998. — 377 p.

Sidorenko A.M. Work planning and scheduling subject to modules and articles assembly / A.M. Sidorenko, E.N. Khobotov // Automation in industry. — 2012. — № 10. — P. 21–25.

Zak Ju.A. Properties of admissible and optimum sequences of performance of works on a single machine / Ju.A. Zak // Control Sciences. — 2012. — № 5. — P. 54–61.


Пристатейна бібліографія ГОСТ


1. Conway R.W. Theory of Scheduling / R.W. Conway, W.L. Maxwell, L.W. Miller. — Addison-Wesley Publishing Company, 1967. — 294 p.

2. Zack Yu.A. Applied problems of the theory of scheduling and traffic routing [in Russian] / Yu.A. Zack. — M., URSS, 2012. — 394 p.

3. Zgurovsky M.Z. Decision making in networked systems with limited resources [in Russian] / M.Z. Zgurovsky, A.A. Pavlov. — K.:. Nauk. dumka, 2010. — 573 p.

4. Zack Yu.A. Construction of two-stage schedules of processing of products on one machine / Yu.A. Zack // System research and information technologies. — 2018. — № 4. — P. 19–36.

5. Zack Yu.A. Developing admissible and optimal schedules of works on one machine / Yu.A. Zack // Cybernetics and systems analysis. — № 1. — 2012.

6. Zak Yu.A. Two-stage planning tasks for the flow line / Yu.A. Zak // Control Sciences. — M., 2019. — № 6. — P. 52–62.

7. Zack Yu.A. Algorithms for approximate multi-stage Flow-Shop-Problem solution / Yu.A. Zack // System research and information technologies. — 2019. — № 3. — P. 100–109.

8. Carlier J. The one-machine sequencing problem / J. Carlier // European Journal of Operational Research. — 1982. — N 11. — P. 42–47.

9. Domschke W. Produktionsplanung. Ablauforganisatorische Aspekte / W. Domschke, A. Scholl, S. Voß. — Berlin, Heidelberg: Springer Verlag, 2005. — 456 p.

10. Brucker P. Scheduling Algorithms / P. Brucker // Springer-Verlag, Berlin, Heidelberg und New York, 1998. — 377 p.

11. Sidorenko A.M. Work planning and scheduling subject to modules and articles assembly / A.M. Sidorenko, E.N. Khobotov // Automation in industry. — 2012. — № 10. — P. 21–25.

12. Zak Ju.A. Properties of admissible and optimum sequences of performance of works on a single machine / Ju.A. Zak // Control Sciences. — 2012. — № 5. — P. 54–61.