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.

5 comments:

  1. Этот вопрос рассматривался в работах уфимской школы раскроя упаковки. Свойство алгоритма, который переводит линейно упорядоченные объекты к оптимуму задачи, учёные УГАТУ называют свойством реставрации.
    Вот цитата из работы Филипповой А.С.: "Свойство реставрации упаковки. Важной характеристикой декодера является его способность получить оптимальную безотходную упаковку, по заранее известному оптимальному коду (приоритетному списку), т.е. способность правильно декодировать. Названо это свойство декодера термином «реставрация». Алгоритмы SubNF, SubFF, BD и FBD обладают свойством реставрации. Это было замечено нами и доказано при проведении экспериментов с безотходными упаковками Е. Хоппер"

    ReplyDelete
  2. Что значит доказано при проведении экспериментов? Как можно такое свойство доказать при помощи экспериментов? Если я не ошибаюсь, то в приведенной тобой цитате говорится лишь о том, что на множестве индивидуальных задач Е. Хоппер были получены оптимумы, о которых заранее известно, что они безотходные. А индивидуальные задачи Е. Хоппер представляют собой всего лишь подмножество всех индивидуальных задач той массовой задачи, о которой идет речь в цитате.

    ReplyDelete
  3. Как доказали экспериментами -- я не в курсе, надо читать подробнее. Действительно, в задачах Хоппера известно заранее, что упаковка безотходная заранее, так же как и оптимум, а иначе как доказать свойство, если оптимум не известен? И представленная мной цитата продолжает последний абзац твоего сообщения об эвристике BL.

    ReplyDelete
  4. Что касается "задач Хоппера", то правильно, все-таки, задач Хоппер, это Ева Хоппер.
    Доказать можно, даже если не известен оптимум.
    Из какой работы Филипповой эта цитата?

    ReplyDelete
  5. > Доказать можно, даже если не известен оптимум.
    Согласен.
    > Из какой работы Филипповой эта цитата?
    Это из автореферата докторской.

    ReplyDelete