С.В. Минухин, канд. техн. наук
Харьковский национальный экономический университет
(Украина, 61001, Харьков, пр-т Ленина, 9-а,
тел.: 057 7021831, e-mail:
Д.С. Ленько
(Украина, Харьков, e-mail:
АННОТАЦИЯ
Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма при использовании правил доминирования—относительного уменьшения суммарного запаздывания и числа получаемых локально-оптимальных решений. Приведены результаты вычислительных экспериментов для взвешенного и невзвешенного случаев запаздывания работ с произвольными директивными сроками. Найдены условия, при которых используемый алгоритм позволяет улучшить расписания работ и определить наиболее эффективные правила доминирования.
КЛЮЧЕВЫЕ СЛОВА:
ранговый подход, гамильтонов путь, расписание, суммарное запаздывание, временная сложность, директивный срок, одиночное устройство, длительность, правило доминирования.
СПИСОК ЛИТЕРАТУРЫ
1. Ye Nong, Gel Esma S., Li Xueping, Farley Toni, Lai Ying-Cheng Web Server QoS Models: Applying Scheduling Rules from Production Planning // Computers & Operations Research.— 2005. — № 32. — P. 1147—1164.
2. Zafril Rizal M Azmi, Kamalrulnizam Abu Bakar, Abdul Hanan Abdullah, Mohd Shahir Shamsir, Wan Nurulsafawati Wan Manan Performance Comparison of Priority Rule Scheduling Algorithms Using Different Inter Arrival Time Jobs in Grid Environment // Intern. J. of Grid and Distributed Computing.— 2011. — Vol. 4, No. 3. — P. 61—70.
3. Singh H., Dr. Kumar S. Dispatcher Based Dynamic Load Balancing on Web Server System // Ibid. — 2011.— Vol. 4, No. 3. — P. 89—105
4. Zafril RizalMAzmi, Kamalrulnizam Abu Bakar , Mohd Shahir Shamsir, Wan Nurulsafawati Wan Manan, Abdul Hanan Abdullah Scheduling Grid Jobs Using Priority Rule Algorithms and Gap Filling Techniques // Intern. J. of Advanced Science and Technology. —2011.— Vol. 37. — P. 61—76.
5. Klusacek D., Rudova H. Comparison of Multi-criteria Scheduling Techniques. S. Gorlatch, P. Fragopoulou and T. Priol, Editors. —Springer US, 2008. — P. 173—184.
6. Klusacek D., Rudova H. Improving QoS in Computational Grids through Schedule-based Approach // In Scheduling and Planning Applications Workshop at the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS 2008). Sydney, Australia. — 2008.
7. Листровой С.В., Минухин С.В. Модель и подход к планированию распределения ресурсов в гетерогенных ГРИД-системах // Проблемы управления и информатики. Международный научно-технический журнал. — 2012. — № 5. — С. 120—133.
8. Листровой С.В., Минухин С.В. Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии // Электрон. моделирование. — 2012.— 34, №1. — С. 29—43.
9. Koulamas C. The Total Tardiness Problem: Review and Extensions // Operations Research.— 1994.— Vol. 42. — P. 1025—1041.
10. Koulamas C. The Single-machine Total Tardiness Scheduling Problem: Review and Extensions // European J. of Operational Research. — 2010. — Vol. 202, No. 1. — P. 1—7.
11. Sena T., Suleka J.M., Dileepan Parthasarati Static Scheduling Research to Minimize Weighted and Unweighted Tardiness: A State-of-the-art Survey //Intern. J. Production Economics. — 2003.— Vol. 83, No. 1. — P. 1—12.
12. Du J., Leung J.Y.-T. Minimizing Total Tardiness on One Machine is NP-hard //Mathematics of Operations Research. — 1990. — ¹ 15. — P. 483—495.
13. Lawler E.L. A «Pseudo Polynomial» Algorithm for Sequencing Jobs to Minimize Total Tardiness // Annals of Discrete Mathematics. — 1977. — No1. — P. 331—342.
14. Baker K.R., Shrage L.E. Finding an Optimal Sequence by Dynamic Programming an Extension to Precedence-related Tasks // Operations Research Letters.—1978.—No 26.— P. 111— 120.
15. Lawler E.L. A Fully Polynomial Approximation Scheme for the Total Tardiness Problem // Ibid. — 1982.— No 1. — P. 207—208.
16. Potts C.N., Van Wassenhove L.N. Dynamic Programming and Decomposition Approaches for the Single Machine Total Tardiness Problem // European J. of Operational. —1987. — No 32. — P. 405—414.
17. Kovalyov M.Y. Improving the Complexities of Approximation Algorithms for Optimization problems // Operations Research Letters.— 1995.—Vol. 17, March.—P. 85—87.
18. Koulamas C. A Faster Fully Polynomial Approximation Scheme for the Single Machine Total Tardiness Problem // European J. of Operational Research.— 2009.— No 193.—P. 637— 638.
19. Павлов А.А., Мисюра Е.Б. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» // Системные исследования и информационные технологии. — 2002. — № 2. — С. 7—32.
20. Павлов О.А., Мисюра Е.Б., Шевченко К.Ю. Побудова ПДС-алгоритму розв'язання задачі мінімізації сумарного зваженого запізнення виконання робіт на одному приладі // Вісн. НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. — Київ: Век+, 2012. — № 56. — С. 58—70.
21. Мінухін С.В. Метод мінімізації часу виконання завдань з директивними строками на некластеризованому ресурсі обчислювальної системи // Інформаційно-керуючі системи на залізничному транспорті. —2009. — № 3. — С. 47 — 53.
22. Minukhin S. Efficient Method for Single Machine Total Tardiness Problem // IV Intern. Conf. «Problems of Cybernetics and Informatics» (PCI'2012), September 12—14, 2012.
23. Мінухін С.В., Лєнько Д.С. Дослідження методів мінімізації сумарного часу запізнювання робіт з директивними строками на одиночному обчислювальному ресурсі // Проблеми і перспективи розвитку ІТ-індустрії. Системи обробки інформації. — 2013. — Вип. № 3 (110). Т. 2. — С. 30—35.
24. Шевченко К.Ю. Алгоритм гілок та меж для статистичних досліджень нового ПДСалгоритму розв'язання задачі мінімізації сумарного зваженого запізнення виконання робіт на одному приладі // Вісн. НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. — Київ: Век+, — 2012. — № 55. — С. 56—69.
25. Chu Ñ. Efficient Heuristics to Minimize Total Flow Time with Release Dates // Operations Research Letters. — 1992.— ¹12. — P. 321—330.
26. Jouglet A., Savourey D.D., Carlier J., Baptiste P. Dominance-Based Heuristics for One-Machine Total Cost Problems // European J. of Operational Research.—2008.—184 (3).—P. 879— 899.
27. Jouglet A., Savourey D. Dominance Rules for the Parallel Machine Total Weighted Tardiness Scheduling Problem with Release Dates//Computers & Operations research. — 2011. — Vol. 38, Issue 9. — P. 1259—1266.
28. Jackson J. R. Scheduling a Production Line to Minimize Maximum Tardiness. Minimizing Total Tardiness for One Machine Research, Report 43, Management Science Research Project, UCLA, 1955.
29. Lai Tsung-Chyan, Kuo Yuh-Kwo Minimizing Total Tardiness for SingleMachine Sequencing // J. of the Operations Research Society of Japan.— 1996. — Vol. 39, ¹ 3. — Ð. 316—321.
30. Scheduling Single Machine Scheduling
31. OR-Library
32. Zotkin D., Keleher P.J. Job-Length Estimation and Performance in Backlling Schedulers // In Proc. 8th High Performance Distributed Computing Conf. IEEE, 1999.
33. Mohamadreza Kaviani, Majid Aminnayeri, Seyed Nima Rafienejad, Fariborz Jolai. An Appropriate Pattern to Solving a Parallel Machine Scheduling by a Combination of Meta-heuristic and Data Mining // J. of American Science. — 2012. — № 8 (1). — P. 160—167.
34. Chandra P., Li S., Stan M. Jobs and Tool Sequencing in an Automated Manufacturing Environment // Intern. J. of Production Research. — 1993. — Vol. 31, Issue 1. — P. 2911— 2925.
35. Sekhar C.V. S., Devi M.P. Improvement of Performance in a Maintenance Job Shop // Proc. of the 11th WSEAS Intern. Conf. on Applied Mathematics. Dallas, Texas, USA, March 22—24, 2007.— P. 29—34.
МИНУХИН Сергей Владимирович, канд. техн. наук, профессор кафедры информационных
систем Харьковского национального экономического университета. В 1976 г. окончил Харьковский ин-т радиоэлектроники. Область научных исследований — оптимизация функционирования распределенных вычислительных систем, распределенные вычисления, облачные вычисления.
ЛЕНЬКО Дмитрий Сергеевич. В 2013 г. окончил Харьковский национальный экономический университет. Область научных исследований — методы и алгоритмы построения расписаний.