Задача о рюкзаке.

[пианист]

Навскидку попробовал бы свести задачу к целочисленному программированию, и, соответственно, запихнул в какую-нибудь программу для MIP.
По сути это будет перебор, конечно, но код компактно записывается.

[Geen]

Someone в сообщении #1558905 писал(а):

Geen в сообщении #1558904 писал(а):

Но это же уже не упаковка рюкзаков?

Почему? Просто не осталось предметов такого объёма, который мог бы влезть. В любом случае, весьма похоже.

Ну если на задачах установлено (частичное) упорядочивание - какие задачи надо выполнить до старта рассматриваемой, то это уже мало похоже на укладку рюкзаков... особенно, если связи заданы для наиболее длительных задач.

[Dmitriy40]

Someone в сообщении #1558898 писал(а):

Содержательно "рюкзаки" — это рабочие, занимающиеся сборкой, которых надо загрузить работой достаточно равномерно.

В упомянутой мною теме решалась задача как раз максимально одинаковой загрузки нескольких конвейеров (а не максимально плотной упаковки рюкзаков, это вроде бы существенно другая задача).
В двух словах: распределяем хоть как-то более-менее оптимально (в соответствии с долей общего времени), потом делаем несколько циклов оптимизации перестановкой заданий пока это приводит к улучшению. Там хорошее решение достигалось за всего несколько циклов оптимизации. Но не идеальное.
Литературу посоветовать не могу.
И да, как-то оно всё меньше похоже на укладку рюкзака(-ов). Я бы искал что-то в сторону методов планирования производства, выше об них уже упоминали.

[Someone]

Geen в сообщении #1558916 писал(а):

Ну если на задачах установлено (частичное) упорядочивание - какие задачи надо выполнить до старта рассматриваемой

Нет, не установлено. Бригада получает задание собрать несколько комплектов устройств (каждый комплект упаковывается в отдельный ящик), причём, комплекты, вообще говоря, имеют разный состав. Их сборка является приоритетной. Время сборки разных устройств варьируется ориентировочно от $3$ до $40$ минут. Два одинаковых устройства одновременно рабочий собирает быстрее, чем два по отдельности (например, каждое отдельно — за $10$ минут, а одновременно оба — за $15$). Кроме того, при наличии у рабочего достаточного свободного времени нужно собирать устройства, не входящие в комплекты (из заданного списка). В сборке одного комплекта могут участвовать несколько рабочих, но каждое устройство должно собираться одним рабочим, который персонально отвечает за качество сборки. Пока все заданные комплекты не упакованы в ящики и не вывезены, нового задания не будет. Оптимизация касается одного задания.

Dmitriy40 в сообщении #1558918 писал(а):

В упомянутой мною теме решалась задача как раз максимально одинаковой загрузки нескольких конвейеров

Ну, это, как я понял, не совсем то, что нужно. Потому что простоев у рабочих в сумме получается довольно много, и если их удачно распределить, то появится время для сборки дополнительных устройств, не входящих в комплекты. Насколько я догадываюсь, комплекты собираются по специальным заказам, а дополнительные устройства идут в продажу (их делают много).

[Sender]

пианист в сообщении #1558912 писал(а):

Навскидку попробовал бы свести задачу к целочисленному программированию

Да, такой подход выглядит привлекательным, причём можно отметить, что, во-первых, в данном случае это не просто целочисленное программирование, а 0-1-линейное программирование(или булево линейное программирование), а во-вторых, в отличие от канонической задачи линейного программирования, целочисленность позволяет задать в том числе нелинейные ограничения. Так, если у нас есть переменные $x,y,f\in\{0,1\}$, мы можем наложить ограничение в виде $f = x\vee y$ при помощи, например, такой системы неравенств:

$$\begin{cases}x\leqslant f \\ y \leqslant f \\ x+y-f \geqslant 0\end{cases}$$

-- Пт июл 01, 2022 09:26:20 --

Если отвлечься от условия о возможности ускоренного выполнения нескольких одинаковых работ одним рабочим, формулировка задачи очевидна.
Если есть $m$ рабочих и $n$ работ, подлежащих исполнению, естественно задать пространство решений в виде набора булевых переменных $\{x_{ij}\},1\leqslant i \leqslant m,1\leqslant j \leqslant n,x_{ij}\in\{0,1\}$, где $x_{ij}=1$ означает, что j-я работа выполняется i-м рабочим.
Максимизации подлежит сумма всех $x_{ij}$:$\sum \limits_{\substack{1\leqslant i\leqslant m \\ 1\leqslant j\leqslant n}} x_{ij}\to \max.$
Все обязательные работы из заданного подмножества должны быть выполнены:
$\forall j \in P \sum \limits_{1\leqslant i\leqslant m}x_{ij}=1.$
Ну и ограничения, накладываемые трудовым кодексом:
$\forall i, 1 \leqslant i \leqslant m \sum \limits_{1\leqslant j\leqslant n}x_{ij}t_j \leqslant T.$

[пианист]

Sender
Да, все верно, "в целочисленном программировании все функции линейные" (с).
--
Кстати, есть примерчик для похожей задачи: в документации glpk http://ftp.gnu.org/gnu/glpk/glpk-5.0.tar.gz, в examples есть файлик bpp.mod:

Цитата:

We need to estimate an upper bound of the number of bins sufficient
to contain all items. The number of items m can be used, however, it
is not a good idea. To obtain a more suitable estimation an easy
heuristic is used: we put items into a bin while it is possible, and
if the bin is full, we use another bin. The number of bins used in
this way gives us a more appropriate estimation.

[Sender]

Sender в сообщении #1558990 писал(а):

Если отвлечься от условия о возможности ускоренного выполнения нескольких одинаковых работ одним рабочим, формулировка задачи очевидна.

Забыл ещё добавить условие того, что каждая работа выполняется не более одного раза:
$\forall j, 1\leqslant j\leqslant n \sum\limits_{1\leqslant i\leqslant m}x_{ij}\leqslant 1.$

[Mihaylo]

Соотношение эффективности алгоритма и точности решения как-то смутно задано. Укажите допустимое время работы алгоритма и примерное число предметов. А также разъясните, как должен работать алгоритм при изъятии предметов из рюкзаков и появлении новых предметов для размещения.

[Someone]

Спасибо всем за советы. Если у заинтересованных лиц будут какие-нибудь вопросы, я их задам.

[ozheredov]

пианист в сообщении #1558997 писал(а):

an easy
heuristic is used: we put items into a bin while it is possible, and
if the bin is full, we use another bin. The number of bins used in
this way gives us a more appropriate estimation.

Какой-то очень завышенный upper bound получится, не?

[пианист]

"Мопед не мой", с вопросами лучше к автору.

[Sender]

Sender в сообщении #1558990 писал(а):

Если отвлечься от условия о возможности ускоренного выполнения нескольких одинаковых работ одним рабочим, формулировка задачи очевидна.

Впрочем, если подумать, это условие не вызывает особых сложностей.
Если у нас множество всех номеров работ разбито на непересекающиеся классы эквивалентности $\{1,\dots,n\}=\cup\limits_{1\leqslant k \leqslant r}W_k$, т.к. все работы из класса $W_k$ одинаковы, они выполняются за одно и то же время $\forall i \in W_k\; t_i=T_k$, а две одинаковые работы из класса $W_k$ выполняются за время $\tau_k\leqslant 2T_k$. Обозначии $s_{ik}=\sum\limits_{j \in W_k}x_{ij}$, тогда вклад $k$-го класса в общее время работы $i$-го рабочего составит $t_{ik}=\lfloor \frac{s_{ik}}{2}\rfloor\tau_k+(s_{ik}\mod 2)T_k$.
Ну а реализацию целочисленного деления на 2 делаем по определению: $\lfloor \frac{a}{2}\rfloor = b$ при $a,b\in \mathbb{Z}_+$ эквивалентно системе неравенств

$$\begin{cases} 2b\leqslant a \\ 2b+1 \geqslant a \end{cases}$$

В свою очередь, $a\mod 2 = a-2\lfloor \frac{a}{2}\rfloor.$

(Оффтоп)

Интересно, есть какое-нибудь общепринятое обозначение для множества $n$ первых натуральных чисел $\{1,\dots,n\}$? И даст ли в итоге какой-нибудь положительный эффект всё это колдунство?