일정대로 학습하는 알고리즘 : 현대 FJ에 대한 트윈 모델 접근
초록 및 1. 소개
-
혼합 정수 및 구속 조건 프로그래밍 모델
2.1 Mixed-Integer 선형 프로그래밍 모델
2.2 구속 조건 프로그래밍 모델
-
건설적인 휴리스틱
-
벤치 마크 인스턴스
-
수치 실험
5.1 건설적인 휴리스틱 실험
5.2 상용 솔버로 제안 된 모델 해결
-
결론과 참고 문헌
2 혼합 정수 및 구속 조건 프로그래밍 모델
이 섹션에서는 시퀀싱 유연성 및 위치 기반 학습 효과와 함께 FJS 스케줄링 문제에 대한 MILP (Mixed-Integer Linear Programming) 및 CP (Constraint Programming) 공식을 제시합니다.
\
\
\
\
\
2.1 Mixed-Integer 선형 프로그래밍 모델
위치 기반 결정 변수의 채택은 처리 시간의 변화와 관련된 제약을보다 자연스럽게 표현할 수 있기 때문에 위치 기반 학습 효과와 관련된 모델링 문제에 대한 기본 접근법으로 작용합니다. 제안 된 MILP 모델은 파생됩니다 [4] 소개 된 모델을 기반으로합니다 [25] 위치 기반 결정 변수를 고려합니다. 참조하십시오 [26]. 아래 표기법은 모델의 프레젠테이션을 단순화합니다.
\ \
\ MILP 모델은 다음과 같습니다.
\ \
\
\
2.2 구속 조건 프로그래밍 모델
제약 조건 프로그래밍 (CP)은 학업 및 산업 문헌에서 일정 문제를 해결하는 데 널리 사용되는 강력한 방법론입니다. CP Optimizer [19]CP에 뿌리를 둔 최적화 상업용 솔버 인 특수 제약 조건 및 변수 개념을 통합하여 문제를 예약하는 모델링 프로세스를 크게 용이하게합니다. 이 섹션에서는 CP Optimizer와 관련하여 활용을 위해 특별히 설계된 CP 모델을 소개합니다. CP Optimizer의 구문은 제제 내에서 발생할 때 정의됩니다. 모델은 아래에 따릅니다.
\ \
\
\
3 건설적인 휴리스틱
이 섹션에서는 시퀀싱 유연성 및 위치 기반 학습 효과와 함께 FJS 스케줄링 문제에 대한 두 가지 건설적인 휴리스틱을 제안합니다. 건설적인 휴리스틱은 한 번에 하나의 작업을 반복적으로 선택하고 시퀀싱하여 실행 가능한 솔루션을 처음부터 구축하는 알고리즘입니다. 제안 된 건설적인 휴리스틱은 가장 빠른 시작 시간 (EST) 규칙을 기반으로합니다. [4] 그리고 최초의 완료 시간 (ECT) 규칙 [20]. 목표는이를 사용하여 일련의 테스트 인스턴스를 해결하는 데 사용될 정확한 솔버에게 초기 실행 가능한 솔루션을 제공하는 것입니다.
\
\
\
\
\ 알고리즘 4는 ECT 규칙에 따라 건설적인 휴리스틱을 제시합니다. 알고리즘은 하나의 세부 사항을 제외하고 알고리즘 1과 매우 유사합니다. EST를 기반으로 한 건설적인 휴리스틱에서, 먼저 예정되지 않은 작업이 시작될 수있는 가장 초기의 순간 인 즉각적인 RMIN을 계산합니다. 해당 순간에서 시작할 수있는 모든 작동/기계 쌍이 고려되고 가장 짧은 처리 시간이있는 쌍이 선택됩니다. 그러나 모두 Instant Rmin에서 시작하기 때문에 가장 짧은 처리 시간을 가진 쌍이 선택되었다고 말하면 가장 빠른 끝이 끝나는 쌍이 선택된다고 말하는 것과 동일합니다. 이것은 ECT 규칙에 따라 건설적인 휴리스틱에서 극도로 가져 오는 아이디어입니다. 가능한 빨리 시작할 수있는 작동/기계 쌍의 선택을 제한하지 않고, 작업/기계 쌍은 작업의 처리가 일찍 시작되지 않더라도 선택됩니다.
\
\ 가능한. 알고리즘 4의 최악의 사례 시간 복잡성은 알고리즘 1과 동일합니다.
\ EST 기반 휴리스틱은 가장 빨리 시작할 수있는 쌍 작업/기계에 우선 순위를 부여합니다. 시공 시작시, 이것은 대략적으로 각 작업의 모든 첫 번째 작업에 우선 순위를 부여하는 데 대략적으로 일치하며, 이는 전례가없는 작업입니다 (그림 1의 예에서 작전 1, 3 및 7). 그럼에도 불구하고 가능한 한 빨리 작업을 예약하려는 의도로 인해 빈 기계를 선호하고 여러 기계를 사용하는 솔루션을 구축 할 수 있습니다. 각 작업의 첫 번째 작업을 빠르게 예약함으로써 더 많은 작업이 선례를 예약하게하여 미래의 방법 반복에서 가능성 수 (검색 공간)를 증가시킵니다. 반면에, ECT 규칙을 기반으로 한 휴리스틱은 가장 빨리 시작할 수 있는지 여부에 관계없이 가장 빠른 작업/기계 쌍을 선택합니다. 이러한 전략은 향후 반복에서 사용 가능한 작동/기계 쌍의 수를 제한하여 방법의 검색 공간을 줄일 수 있습니다. 또한, 학습 효과와 결합 된 가장 일찍 완료 할 수있는 작동/기계 쌍의 선택은 기계의 위치가 높을수록 가장 짧은 DE 처리 (위치 기반 학습 효과에 의해 감소됨)이므로 이미 여러 작업이 할당 된 기계에서 작업을 예약 할 수 있도록 방법을 이끌어냅니다. 이로 인해 모든 기계가 사용되는 것은 아닙니다. 고려 된 학습 속도 α와 당면한 인스턴스의 우선 순위의 DAG의 밀도에 따라, 한 휴리스틱이 다른 휴리스틱보다 낫다.
\
::: 정보
저자 :
(1) Kag Araujo, Sao Paulo University, Rua do Matao, 1010, Cidadee Universary, 05508-090, Words Paul, Sp, Brazil (Kendy9444 @ime.usp.br);
(2) Eg Birgin, Sao Paul 대학, Rua do Matao, 1010, Civil Universaria, 05508-090, Word Hever, Sp, Brazil ([email protected]);
(3) DP Ronconi, 상파울루 대학교 폴리 테크닉 스쿨 생산 공학과, Av. Luciano Gualberto, 1380, Universitaria City, 05508-010 Sao Paulo, SP, 브라질 ([email protected]).
:::
::: 정보이 논문은입니다 Arxiv에서 사용할 수 있습니다 CC 4.0 Deed (Attribution 4.0 International) 라이센스에 따라.
:::
\
Post Comment