최적화 문제 해결 현대 생산  운영관리 부산대학교 산업대학원 2012 년 2 학기 하병현

1 목차  서론  공정별 배치 -- 물량 거리 모형

2 서론  최적화 문제  주어진 대안들 중 목적을 고려하여 가장 나은 것 선택  예제  공정별 배치 문제 -- 물량 - 거리 모형 입력 : 부서 간 물량 및 단위 이송 비용 대안 집합 : 모든 가능한 배치 형태 목적 : 총 이송 비용 최소화  배정 문제 입력 : 각 작업자 별 과업 처리 비용 대안 집합 : 모든 가능한 작업자 - 과업 배정 방법 목적 : 총 비용의 최소화  문제의 난이도  쉬운 문제 e.g., 배정 문제, 표준 수송 계획  어려운 문제 (NP-hard problems) e.g., 물량 - 거리 모형, traveling salesman problems

3 서론  해결 방안  최적화 방법 모든 대안 검토 문제에 특화된 최적화 알고리즘 e.g., 배정 문제 : Hungarian method, 선형 계획 : Simplex method 범용 최적화 방법론 e.g., branch and bound, dynamic programming, A*-search 상용 최적화 소프트웨어 사용  보통 내부적으로 branch and cut 사용  근사해 도출 방법 발견적 기법 (heuristic algorithms) e.g., 물량 - 거리 모형의 최대 비용 부서 인접화 메타 휴리스틱 (meta-heuristics) e.g., simulated annealing, tabu search, genetic algorithms 상용 소프트웨어 사용  보통 내부적으로 메타 휴리스틱 사용  일부만 나열

4 공정별 배치 -- 물량 거리 모형  예제 문제  부서 간 이동 물량  부서 간 단위 물량 당 이동 비용 (D ij C ij ) 물량 한 단위 당, 인접 부서의 경우 1 원, 한 부서를 건너뛸 때마다 1 원이 추가 대각선의 경우 인접 부서로 봄  배치 가능 형태  Quadratic assignment problem  NP-hard

5 공정별 배치 -- 물량 거리 모형  발견적 기법 (gradient-descent 또는 greedy approach) 1. 최초 배치 도출 순서대로 배치 2. 총비용을 감소시킬 수 있는 새로운 배치 도출 모든 인접 부서를 서로 교환해본 후 총비용을 가장 감소시키는 배치 선택 3. 비용이 개선되었다면 단계 2 반복, 아니면 종료

6 공정별 배치 -- 물량 거리 모형  발견적 기법 ( 계속 )  구현 (Python) z0 = 2,778, X = [1, 1, 3, 2, 3, 2, 4, 4]  X[i]: 부서 i 가 위치한 열 L = [[0, 175, 50, 0, 30, 200, 20, 25], [0, 0, 0, 100, 75, 90, 80, 90], [0, 0, 0, 17, 88, 125, 99, 180], [0, 0, 0, 0, 20, 5, 0, 25], [0, 0, 0, 0, 0, 0, 180, 187], [0, 0, 0, 0, 0, 0, 80, 70], [0, 0, 0, 0, 0, 0, 0, 7], [0, 0, 0, 0, 0, 0, 0, 0]] def C(x1, x2): return max(1, abs(x1 - x2)) def total_cost(X): return sum(L[i][j] * C(X[i], X[j]) for i in xrange(7) for j in xrange(i + 1, 8)) ( 뒤에서 계속 )

7 공정별 배치 -- 물량 거리 모형  발견적 기법 ( 계속 )  구현 (Python) ( 계속 ) X0 = X = [1,1,2,2,3,3,4,4] z0 = total_cost(X) while True: updated = False for i in xrange(7): for j in xrange(i + 1, 8): X1 = X[:] X1[i], X1[j] = X1[j], X1[i] z1 = total_cost(X1) if z1 < z0: z0, X0 = z1, X1 updated = True if not updated: break print "z0 = %d, X = %s" % (z0, X0) ( 앞에서 계속 )

8 공정별 배치 -- 물량 거리 모형  최적해 방법 : 모든 대안 검토  발견적 기법의 결과인 2,778 원이 최적인가 ?  모든 대안 [1,1,2,2,3,3,4,4], [1,1,2,2,3,4,3,4], [1,1,2,2,4,4,3,3],... 모두 몇 개 ? 대략 8  7  6  5  4  3  2  1 = 8! =  구현 (Python) z* = 2,510, X = [1, 2, 3, 1, 4, 2, 4, 3]  문제 ? 12! = 479,001,600 30! = 265,252,859,812,191,058,636,308,480,000, z0 = 10**10 for X in permutations([1,1,2,2,3,3,4,4]): z = total_cost(X) if z < z0: z0, X0 = z, X print "z* = %d, X = %s" % (z0, X0)

9 공정별 배치 -- 물량 거리 모형  최적화 수리 모형 ( 문제를 기술하는 한 가지 방법 )  정수 계획 모형  입력 변수 L ij : 부서 i 에서 j 로의 이동 물량  결정 변수 y ik : 부서 i 가 k 번째 열에 있으면 1, 아니면 0  부서 i 가 위치한 열 :  k=1..4 k  y ik  부서 i 와 j 가 떨어진 정도 : max(1, |  k=1..4 k  y ik –  k=1..4 k  y jk |)  Objective min.  i=1..7  j=(i+1)..8 L ij  max(1, |  k=1..4 k  y ik –  k=1..4 k  y jk |)  Constraints  k=1..4 y ik = 1 for i=1,...,8  i=1..8 y ik = 2 for k=1,...,4

10 공정별 배치 -- 물량 거리 모형  최적화 방법 -- 상용 최적화 소프트웨어 사용  구현 (CPLEX) z* = 2,510, y 14 = y 23 = y 32 = y 44 = y 51 = y 63 = y 71 = y 82 = 1 float L[1..8][1..8] = [ [0, 175, 50, 0, 30, 200, 20, 25], [0, 0, 0, 100, 75, 90, 80, 90],... [0, 0, 0, 0, 0, 0, 0, 0] ]; dvar int y[1..8][1..4] in 0..1; minimize sum (i in 1..7) sum (j in (i + 1)..8) L[i][j] * maxl(1, abs(sum (k in 1..4) k * y[i][k] - sum (k in 1..4) k * y[j][k])); subject to { forall (i in 1..8) sum (k in 1..4) y[i][k] == 1; forall (k in 1..4) sum (i in 1..8) y[i][k] == 2; }

11 공정별 배치 -- 물량 거리 모형  근사해 도출 방법 -- 상용 소프트웨어 사용  구현 (MS Excel) z = 3,147  엑셀은 이 문제는 제대로 해결하지 못하는 것으로 보임 참고 : Google 에서 “ 엑셀 2007 해찾기,” “ 엑셀 해찾기,” “excel 2007 solver,” “excel solver” 등으로 검색

12 공정별 배치 -- 물량 거리 모형  근사해 도출 방법 -- 상용 소프트웨어 사용 ( 계속 )  구현 (Open Solver for Excel) z = 3,107

13 공정별 배치 -- 물량 거리 모형  근사해 도출 방법 -- 메타 휴리스틱 (simulated annealing)  구현 (Python) z* = 2,510 / 2,510 / 2,510 / 2,510 / 2,510 / 2,510 / 2,510 / 2,510 / 2,510 / 2, from random import shuffle, randrange, random from math import exp for _ in xrange(10): X = [1, 1, 2, 2, 3, 3, 4, 4] shuffle(X) X0 = X[:] z = z0 = total_cost(X) t, pi, EPSILON = 100, 0.999, while t > EPSILON: X1 = list(X) i, j = randrange(8), randrange(8) X1[i], X1[j] = X1[j], X1[i] z1 = total_cost(X1) if z1 <= z or random() < exp((z - z1) / t): X, z = X1, z1 if z < z0: X0, z0 = X[:], z t *= pi print "z0 = %d, X = %s" % (z0, X0)

14 공정별 배치 -- 물량 거리 모형  Medium-size problem (16 개의 부서 )  실험 결과  Gap = (z – z*) / z*  100% L = [[0, 166, 147, 72, 37, 92, 69, 153, 47, 85, 108, 180, 91, 42, 147, 116], [0, 0, 35, 181, 197, 159, 179, 48, 141, 178, 131, 84, 2, 75, 115, 181], [0, 0, 0, 193, 85, 171, 37, 157, 101, 0, 139, 68, 162, 127, 0, 89], [0, 0, 0, 0, 171, 33, 51, 172, 22, 105, 32, 193, 157, 79, 0, 50], [0, 0, 0, 0, 0, 92, 186, 4, 101, 136, 100, 159, 99, 193, 113, 109], [0, 0, 0, 0, 0, 0, 78, 111, 65, 107, 44, 21, 21, 115, 125, 85], [0, 0, 0, 0, 0, 0, 0, 0, 147, 173, 184, 166, 178, 184, 99, 66], [0, 0, 0, 0, 0, 0, 0, 0, 135, 40, 159, 167, 177, 110, 189, 108], [0, 0, 0, 0, 0, 0, 0, 0, 0, 79, 125, 200, 182, 155, 0, 115], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 87, 119, 166, 33, 141, 5], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 155, 53, 160, 2], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 134, 0, 106], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 181, 98, 130], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 120], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 114], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] 해결 방법총비용 Gap 계산시간비고 최적화 방법상용 소프트웨어 CPLEX31,338– 초최적해 근사해 도출 방법 발견적 기법 34,48610% < 0.1 초 상용 소프트웨어 OpenSolver36,71217% < 0.1 초초기해보다 나쁨 메타 휴리스틱 Simulated annealing31,3380% 9.2 초 10 회 수행 중 5 회