Как мы можем доказать, что технологии оптимизации Quintiq превосходят другие?

Мы нашли лучшие решения для одних из самых сложных задач оптимизации в мире. Вот несколько наших последних рекордов:

Гибкая цеховая задача планирования (Flexible Job Shop Scheduling Problem)

Суть задачи

Гибкая цеховая задача планирования (FJSSP) является развитием классической задачи цехового планирования (JSSP). Задача JSSP строится на допущении, что каждую конкретную операцию можно выполнять только на одном станке. Задача FJSSP, как следует из ее названия, предполагает более гибкую конфигурацию: для выполнения одной операции подходят несколько станков.

Задачу FJSSP сформулировал Паоло Брандимарте в 1993 году. Первоначальное определение Брандимарте включало в себя несколько частных случаев, которые менялись в зависимости от гибкости настройки станков. В последующие годы учеными были опубликованы новые варианты, часть из которых содержала дополнительные ограничения. Существует несколько вариаций тестовых наборов Соломона и Геринга-Хомбергера. Герингом и Хомбергером рассмотрены несколько частных случаев, различающихся количеством клиентов — от 200 до 1000. Другие параметры, в том числе спецификации заказов и расстояния, также варьируются в зависимости от конкретной ситуации.

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

Каждая частная постановка задачи FJSSP характеризуется следующими условиями:

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

Мировые рекорды Quintiq

Команда оптимизации Quintiq изучила опубликованные частные постановки и результаты задачи FJSSP. Были обработаны все 313 частных постановок, для которых известны исходные условия и результаты. Оптимизатор Quintiq нашел новые лучшие решения для 119 из них — ни одной научной или производственно-исследовательской группе до сих пор такого не удавалось. Доказано, что 95 из 119 решений являются оптимальными.



Вот несколько наших последних и наиболее впечатляющих успехов:

реализации Бывший мировой рекорд1 Дата Мировой рекорд Quintiq2 Дата
Hurink-vdata vdata-abz9 498 Nov 2013 497 Jan 2016
Dauzere 08a 2066 Jan 2014 2061 Nov 2015
Hurink-rdata rdata-la27 1088 Nov 2013 1085 Nov 2015
Dauzere 14a 2162 Jan 2014 2161 May 2014
Hurink-vdata vdata-la25 752 Jan 2014 751 May 2014
Hurink-vdata vdata-abz7 493 Nov 2013 492 Jan 2014
Hurink-vdata vdata-car1 5006 Jan 2014 5005 Jan 2014
Hurink-vdata vdata-la26 1054 Feb 2000 1052 Sep 2013
Hurink-rdata rdata-la03 478 Feb 2000 477 Aug 2013
Dauzere 03a 2229 Oct 2008 2228 Mar 2013
1 Показаны мировые рекорды по верхней границе. С более подробными результатами по верхней и нижней границам можно ознакомиться здесь.
2 Все приведенные результаты являются оптимальными, то есть дальнейшее улучшение уже невозможно.