Efficiency research of the three-level model of small-series production planning - Lisetsky, Taras Nikolayevich (НТУ "ХПИ", 2018)
We consider the problem of finding an order portfolio that maximizes the total profit according to one of five optimization criteria and should fit the beginning date of the planned period and the due dates specified by the customers. Also, we need to build for this order portfolio a feasible (not violating the due dates) operational plan of jobs processing that would correspond to the minimum possible processing time of the entire order portfolio. We show that the problem in this formulation is a multi-stage scheduling problem. We describe previously developed methodology for the problem solving: the three-level model of production planning. We substantiate the possibility of applying the methodology for any type of small-series production according to one of the five criteria of optimality. We show that independently of the production type considered, whatever is the original production technology, and no matter how the multi-stage scheduling problem is implemented, we reduce the planning problem solving for any of the five optimality criteria to obtaining a feasible solution of the multi-stage scheduling problem for the criterion of maximizing the start time of the earliest job. We show that the efficiency of the multi-stage scheduling problem solving depends on the efficiency of solving the first level of the three-level model. Therefore, we statistically investigate and prove the efficiency of solving the problem of minimizing the total weighted completion time of jobs with precedence relations on a single machine. We show the efficiency of PSC-algorithm for the problem solving for the case when the weights of only terminal vertices of the precedence graph are non-zero. We have shown that the approximation algorithm for this problem solving allows to solve real practical large size problems (we checked dimensions of up to 10,000 jobs). The solutions obtained by the approximation algorithm coincided with those obtained by the exact PSC-algorithm in 99.97 % cases.

Рассматривается задача нахождения портфеля заказов, максимизирующего суммарную прибыль по одному из пяти критериев оптимизации, при котором соблюдено начало планового периода и директивные сроки, заданные заказчиками. Также требуется построить для этого портфеля заказов допустимый (не нарушающий директивных сроков) пооперационный план выполнения работ, которому соответствует минимально возможное время выполнения всего портфеля заказов. Показано, что задача в такой постановке является многоэтапной задачей ка- лендарного планирования. Описывается ранее разработанная методология решения задачи – трехуровневая модель планирования производства. Обосновывается возможность применения методологии для любого вида мелкосерийного производства по любому из данных пяти критериев оптимальности. Показано, что для любого вида производства, при любой исходной технологии выполнения изделий и при любой реализации многоэтапной задачи календарного планирования, решение задачи планирования по любому из пяти этих критериев оптимальности сводится к получению допустимого решения многоэтапной задачи календарного планирования по критерию максимизации момента запуска самой ранней работы. Показано, что эффективность решения многоэтапной задачи календарного планирования зависит от эффективности решения первого уровня трехуровневой модели. Поэтому, статистически исследуется и обосновывается эффективность решения задачи минимизации суммарного взвешенного момента окончания выполнения работ с отношениями предшествования на одном приборе. Показана эффективность ПДС-алгоритма решения задачи для случая, когда веса всех вершин графа предшествования, кроме конечных, равны нулю. Показано, что приближенный алгоритм решения этой задачи позволяет решать реальные практические задачи большой размерности (проверялись размерности до 10,000 работ). Решения, полученные приближенным алгоритмом, совпали с полученными точным ПДС-алгоритмом в 99.97 % случаев.
Исследование эффективности трехуровневой модели планирования мелкосерийного производства
Keywords: production planning; PSC-algorithm; combinatorial optimization; scheduling; планирование производства; ПДС-алгоритм; комбинаторная оптимизация; составление расписаний