---

Text in pdf-file msp.pdf

Пусть S, I, and U - множества продуктов, операций и устройств соответственно. Предполагается, что каждая операция производит ровно один продукт и выполняется на одном устройстве. Определим следующие входные параметры:

• D_s > 0 - величина спроса на продуст s ∈ S;
• s_i ∈ S - продукт, производимый операцией i ∈ I;
• u_i ∈ U - устройство для выполнения операции i ∈ I;
• r_i > 0 - производительность операции i ∈ I, т.е. количество продукта s_i производимого в один час;
• a_ij - длительность переналадки устройства u с операции i на операцию j (предполагая, что u = u_i=u_j);
• a_i⁰ - длительность начальной переналадки устройства если операция i выполняется первой на устройстве u_i;
• T_i^min и T_i^max - нижняя и верхняя граница времени выполнения операции i.

Требуется определить множество операций для выполнения и построить расписание, чтобы обеспечить производство продукта в заданном объеме, соблюдая ограничения на T_i^min и T_i^max. За основной критерий принимается момент окончания последней операции (Makespan) обозначенный через C^max. Также рассматриваются два дополнительных критерия: минимимзация суммарного времени переналадок и суммарного времени производства на всех устройствах. Эти критерии добавляются в целевую функцию со штрафными коэффициентами P₁ и P₂, которые являются настраиваемыми параметрами. Данная задача NP-трудна [3].

Для каждого устройства u определим множество позиций: K_u:={1,2, ... , |I_u|}. Введем следующие переменные:

• x_ik ∈ {0,1} такие, что x_ik=1 тогда и только тогда, когда операция i выполняется на устройстве u_i в позиции k ∈ K_u.
• δ_i ≥ 0 - длительность операции i;
• α_uk ≥ 0 - длительность переналадки на устройстве u между позициями k и (k+1);
• α_u⁰ ≥ 0 - длительность начальной переналадки на устройстве u.

Модель ЧЦЛП выглядит следующим образом:

Целевая функция (1) отражает основной и дополнительные критерии. Условия размещения (2) - (3) означают, что в каждой позиции содержится не более одной операции, и кажая операция занимает не более одной позиции; (4) обеспечивает непрерывное использование позиций, т.е., если некоторая позиция занята, то предыдущие позиции на этом же устройстве заняты тоже (это используется для моделирования переналадок). Неравенства (5) отвечают за произведство продуктов в нужном объеме.

В (6) оценивается время переналадки на устройстве u между позициями k-1 и k (здесь M - достаточно большая константа, которую можно определить как M = max_i,j a_ij). Здесь правая часть неравенства равна a_ij тогда и только тогда, когда x_i,k-1 = 1 и x_jk=1, что позволяет запланировать по крайней мере a_ij единиц времени для переналадки, если операции i и j размещены последовательно. В (7) оценивается время начальной переналадки.

В неравенствах (8) общее время производства и переналадок ограничивается величиной C_max. В неравенства (9) требуется, чтобы врепя выполнения операцттi принадлежало интервалу [T_i^min, T_i^max ], если операция i выполняется, или δ_i=0 иначе.

ЛИТЕРАТУРА

[1] Борисовский П.А. Генетический алгоритм для одной задачи составления производственного расписания с переналадками // Труды XIV Байкальской междунар. школы-семинара "Методы оптимизации и их приложения". Т.4. Иркутск, ИсЭМ СО РАН. - 2008. - с. 166-173.

[2] Borisovsky, P.A., Eremeev, A.V., and Kallrath, J. 2017. "On Hybrid Method for Medium-Term Multi-Product Continuous Plant Scheduling." 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). Novosibirsk. Russia. 18-22 Sept. 2017. IEEE. pp. 42-47.

[3] Dolgui, A., Eremeev, A.V., Kovalyov, M.Y., and Kuznetsov, P.M. 2010. "Multi-Product Lot Sizing and Scheduling on Unrelated Parallel Machines." IIE Transactions 42(7): 514-524.

[4] Eremeev, A.V., Kovalyov, M.Y., and Kuznetsov, P.M. 2018. "Lot-size scheduling of a single product on unrelated parallel machines." Optimization Letters https://doi.org/10.1007/s11590-018-1307-1