퀸틱의 최적화 기술이 단연 업계 최고라는 것을 어떻게 입증할 수 있는가?

퀸틱은 세계에서 가장 까다로운 여러 최적화 과제를 해결했습니다. 최근 수립한 기록은 다음과 같습니다.

Flexible Job Shop Scheduling Problem

문제 개요
FJSSP(Flexible Job Shop Scheduling Problem)는 기존 JSSP(Job Shop Scheduling Problem)를 확장한 벤치마크입니다. JSSP는 오직 한 대의 시스템만이 특정 작업을 실행할 수 있다고 가정합니다. 이에 비해 FJSSP는 그 이름에서 알 수 있듯이 보다 유연한 설정을 가정합니다. 이는 한 대 이상의 시스템상에서 하나의 연산이 실행될 수 있는 운영 환경을 반영한 것입니다.

FJSSP는 1993년 Paolo Brandimarte에 의해 개발되었습니다. Brandimarte가 처음 고안한 FJSSP는 시스템의 유연성에 따라 구분되는 여러 인스턴스를 포함했습니다. 이후 시간이 흐르면서 과학자들은 여러 벤치마크 변형을 발표했으며 일부는 제약 조건이 추가되었습니다.

스펙에 차이가 있기는 하지만, 전체 완료 시간이 최소화되도록 모든 연산을 시스템에 순차적으로 할당(각 작업에 연산 순서 반영)해야 한다는 문제의 핵심은 동일하게 그대로 유지됩니다.

FJSSP는 다음과 같은 특징을 가지고 있습니다.
  • 작업의 횟수와 시스템의 대수가 지정됨
  • 각 작업은 고정된 순서의 연산으로 구성됨
  • 특정 연산은 오직 특정 시스템에서만 실행될 수 있음
  • 연산의 처리 시간은 실행되는 시스템에 따라 달라질 수 있음
  • 각 시스템은 한번에 오직 단 하나의 연산만 실행할 수 있음

퀸틱의 세계 최고 기록

퀸틱의 최적화 팀은 FJSSP의 공식 인스턴스 및 결과에 대한 연구를 수행했습니다. 그런 다음, 총 313개 인스턴스를 실행했으며 이에 대한 사양과 결과를 모두 공식 발표했습니다. 이들 313개 인스턴스 중에서 Quintiq Optimizer는 119개 인스턴스에 대해 새로운 가장 널리 알려진(best-known) 해결책을 발견했으며 이는 여타 학계 또는 산업 연구 그룹보다도 앞서는 것입니다. 이들 119개의 가장 널리 알려진(best-known) 해결책 중에서 95개는 최적의 해결책으로 입증되었습니다.

퀸틱이 최근 달성한 가장 중요한 결과는 다음과 같습니다.
인스턴스 이전 세계 최고 기록1 일자 퀸틱의 세계 최고 기록2 일자
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 여기에 제시된 모든 기록은 상향 한계(upper bound)의 향상을 나타냅니다. 상향 및 하향 한계(lower bound)의 향상을 보여주는 모든 결과를 여기에서 확인하십시오.
2 제시된 모든 결과는 최적의 결과입니다. 이는 더 이상의 그 어떤 향상도 가능하지 않다는 것을 의미합니다.