ЗАДАЧА ОПТИМАЛЬНОГО ПЛАНУВАННЯ РОБІТ ЗА НАЯВНОСТІ РІЗНОЇ ПРОДУКТИВНОСТІ ВИКОНАВЦІВ

Анотація

Розглядається задача планування роботи на ітерацію гнучкої методології  Scrum. Вона розглядається як задача оптимального планування робіт за наявності різної продуктивності виконавців. Характеристиками розглянутої задачі є наявність загального директивного строку для всіх пристроїв, різна непропорційна продуктивність пристроїв, наявність відношення часткового строгого впорядкування між роботами та визначена для кожного з завдань важливість. Наведено змістовну та математичну постановки задачі, що розглядається, та запропоновано евристичний алгоритм її розв’язування шляхом розбиття на дві підзадачі та розв’язування їх окремо. Для кожної з отриманих підзадач наведено математичні постановки. Для однієї з підзадач запропоновано жадібний алгоритм для отримання припустимого розв’язку.

Ключові слова: Scrum, оптимальне планування, розклад, різна продуктивність, директивний термін, паралельні пристрої, жадібний алгоритм.

Галкина Г. А, доктор технических наук, старший научный сотрудник, Гуляницкий Л. Ф. Задача оптимального планирования работ при наличии разной продуктивности исполнителей / Национальный технический университет Украины «Киевский политехнический институт имени Игоря Сикорского», Институт кибернетики имени В. М. Глушкова Национальной академии наук Украины, Украина, Киев

Рассматривается задача планирования работы на итерацию гибкой методологии Scrum. Она рассматривается как задача оптимального планирования работ при наличии разной продуктивности исполнителей. Характеристиками рассмотренной задачи являются наличие общего директивного срока для всех устройств, разная непропорциональная продуктивность устройств, наличие отношения частичной строгой упорядоченности между работами и определённая для каждого из заданий важность. Приведены смысловая и математическая постановки и предложен эвристический алгоритм решения рассматриваемой задачи путём разбития её на две подзадачи. Для каждой из полученных подзадач приведены математические постановки. Для одной из полученных подзадач предложен жадный алгоритм для получения допустимого решения.

Ключевые слова: Scrum, оптимальное планирование, расписание, разная продуктивность, директивный срок, параллельные устройства, жадный алгоритм.

H. Halkina, Dr.Sc. (Technology), Senior Researcher, L. Hulianytskyi The optimal scheduling problem for machines with different productivity / National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, V. M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Ukraine, Kyiv

The problem of scheduling work for an iteration in Scrum methodology is considered. It is considered as an optimal scheduling problem for machines with different unrelated productivity. The main characteristics of the problem include the existence of a common due date for all the machines, different unrelated productivity of the machines, the partial strict ordering set for the tasks and the value set for each of the tasks to be scheduled. The semantic and formal models of the problem are specified. A heuristic algorithm to solve the considered problem is suggested. It is based on the idea of splitting the problem into two different subproblems. For each of the resulting subproblems a formal model is specified. A greedy algorithm for finding a feasible solution is suggested for one of the subproblems.

Keywords: Scrum, optimal scheduling, schedule, different productivity, due date, parallel machines, greedy algorithm.