Petri Net Induced Heuristic Search for Resource Constrained Scheduling

작성자

Haebom

카테고리

Empty

저자

Ido Lublin, Dor Atzmon, Izack Cohen

💡 개요

본 연구는 자원 제약 프로젝트 스케줄링 문제(RCPSP)를 자원 기반 타이밍 전이 페트리 넷의 도달 가능성 그래프 상에서의 최적 탐색 문제로 재정의합니다. 제안된 페트리 넷 기반 휴리스틱 탐색 기법은 비판 경로와 자원 기반 하한치를 결합한 휴리스틱을 사용하여 A* 탐색을 수행하며, 실험 결과 기존의 강력한 혼합 정수 선형 계획법(MIP) 기반 방법론보다 우수한 성능을 보였습니다.

🔑 시사점 및 한계

•

페트리 넷을 활용한 RCPSP 모델링은 최적 탐색 문제를 효과적으로 해결할 수 있는 새로운 프레임워크를 제공합니다.

•

제안된 휴리스틱 탐색 기법은 기존 MIP 솔버 대비 우수한 성공률과 해결 시간을 달성하며, 특히 자원 제약이 심한 문제에서 강점을 보입니다.

•

문제의 특성(자원 제약의 정도, 문제의 크기)에 따라 휴리스틱 탐색과 MIP 방법론의 성능이 독립적으로 영향을 받으며, 자원 강도가 솔버의 확장성 이점을 매개하는 것으로 나타났습니다.

•

향후 연구에서는 더 정교한 휴리스틱 개발이나 페트리 넷 모델의 확장성을 개선하는 방향으로 진행될 수 있습니다.

PDF 보기

Made with Slashpage