Time-Cost Optimization Algorithm for Generalized Assignment Problem

NP-난제인 GAP에 대해 Guéret et al.은 O(MSUP4/SUP) 복잡도의 선형계획법으로 해를 얻고자 하였다. 반면에, 본 논문에서는 이 문제에 대해 O(mn) 복잡도로 최적 해를 얻을 수 있는 휴리스틱 알고리즘을 제안하였다. 제안된 방법은 GAP의 m × n 시간과 비용행렬에 대해 시간행렬 최적화 결정(선택)과 비용행렬 최적화 결정(교환)의 2단계 최적화(TSO) 기법과 m × n의 시간x비용행렬에 대해 결정 (선택)하는 1단계 최적화(OSO) 기법으로 적용하였다. 제안된 알고리즘은 O(mn) 수행 복잡도의 단순한 결정... View More