Saturday, July 24, 2010

Вопрос о существовании линейного порядка, обеспечивающего порождение оптимума 2

Пока искал информацию о свойстве реставрации упаковки, нашел следующую очень интересную работу:

(1) Залюбовский В.В. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Труды XIII Байкальской школы-семинара. Иркутск. Том 1. 2005. С. 461-468.

В этой работе на странице 462 ставится вопрос, вынесенный в заголовок этого поста:

"4. Наилучший элемент в пространстве решений соответствует оптимальному решению
исходной задачи."

и на него дается ответ на стр. 463 в духе [1]:

"Лемма 2. Для любой допустимой упаковки $\mathcal{P}$ множества предметов $L$ существует $NF$-активная упаковка $\mathcal{P}'$ такая что
\[|\mathcal{P}'|\leq |\mathcal{P}|."\]

Приведем основные понятия в порядке их упоминания в работе (1) с авторскими комментариями.
  1. Понятие NF-активной упаковки. Собственно говоря, именно для алгоритма Next Fit и доказывается о принадлежности оптимума множеству кодов.
  2. Понятие регулярной перестановки и упаковки. Для регулярной упаковки доказывается лемма, аналогичная Лемме 2.
  3. Понятие максимальной упаковки. Для этой упаковки лемма, аналогична Лемме 2 не приводится, хотя из Теоремы 3 можно сделать вывод, что ее доказательство неявно предполагается.
Библиография
  1. Giffler J., Thompson G.L., “Algorithms for solving production scheduling problems,” Operations Research, Vol. 8, 1960, pp. 487–503.

Thursday, July 22, 2010

Вопрос о существовании линейного порядка, обеспечивающего порождение оптимума

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

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

Если говорить об одномерной упаковке, то для задачи одномерной упаковки и для алгоритмов Any Fit классики такими вопросами не задавались. Объясняется это тем, что легко доказать, что для Any Fit алгоритмов всегда существует такой порядок.

В то же время в первой работе об алгоритмах с оценками в худшем случае для упаковки в полосу этот вопрос рассматривался для алгоритма "bottom-up left-justified" (BL) [1], эта же работа и вводит в оборот этот алгоритм. Там было доказано, что существуют примеры, где BL не дает оптимального решения.
  1. BS Baker, EG Coffman and RL Rivest, Orthogonal packings in two dimensions. SIAM Journal on Computing 9/4 (1980), pp. 846–855.

Wednesday, July 7, 2010

DOOR-2010

Сегодня утром мы с моим научным руководителем приехали из России, где были на конференции "Дискретная оптимизация и исследование операций". Было достаточно интересно. Появились новые знакомства.