제 졸업논문을 정리해 2014년 IFIP APMS(프랑스 아작시오)에서 발표한 Integrated Assembly Line Balancing with Skilled and Unskilled Workers를 다시 풀어 씁니다. 서울대 산업공학과 문일경 교수님 지도 아래 썼고, 당시 ETRI 우편기술연구센터에 재직 중이었습니다. 10년이 지난 지금 다시 읽으며 무엇을 풀려고 했고 어떻게 풀었는지 제 언어로 남겨 둡니다.
왜 이 문제를 골랐나
조립라인 밸런싱(Assembly Line Balancing, ALB)은 1950년대부터 연구된 고전 문제입니다. 작업들을 선후관계를 지키면서 워크스테이션에 나눠 담되, 정해진 사이클 타임 안에 끝나게 하고 스테이션 수를 최소화하는 것이 기본형입니다.
실제 공장은 여기서 끝나지 않습니다. 숙련공은 여러 공정을 할 수 있지만 사람마다 가능 작업과 급여가 다릅니다. 비숙련공은 혼자 공정을 맡지는 못하지만 숙련공 옆에 붙으면 작업 시간을 줄여줄 수 있습니다. 워크스테이션 하나를 늘리는 것도 큰 고정비입니다.
논문에서 던진 질문은 세 가지를 동시에 정하는 것입니다. 스테이션을 몇 개 둘 것인가, 각 스테이션에 어떤 숙련공을 앉힐 것인가, 어느 공정에 비숙련공을 붙여 시간을 줄일 것인가. 목표는 이 선택들의 연간 총비용을 최소화하는 것입니다.
수리 모델: 무엇을 최소화하는가
연간 총비용 = 스테이션 운영비 × 스테이션 수 + 배치된 숙련공 급여 합 + 배치된 비숙련공 급여 합으로 두고, 이를 혼합정수계획(MILP)으로 세웠습니다.
- 각 작업은 정확히 한 스테이션에서 한 숙련공이 수행합니다.
- 비숙련공은 숙련공이 배치된 작업에만 붙을 수 있습니다.
- 숙련공은 한 스테이션에만 배치되고, 선행 작업은 후행 작업보다 앞 또는 같은 스테이션에 있어야 합니다.
- 스테이션 작업시간 합에서 비숙련공의 단축분을 뺀 값은 사이클 타임을 넘을 수 없습니다.
- 숙련공은 자기 가능 작업 집합 밖의 작업을 수행할 수 없고, 스테이션당 인원 상한도 지킵니다.
핵심은 비숙련공을 붙이면 해당 작업 시간이 γi만큼 줄어든다는 점입니다. 비숙련공 급여를 더 내는 대신 스테이션 하나를 늘리지 않아도 되는 상황이 생기고, 모델이 이 트레이드오프를 계산합니다.
문제는 크기다: NP-hard
LINGO 10으로 MILP를 풀었을 때 9~12개 작업 규모는 수 분 안에 최적해가 나왔지만, 21개 작업에서는 약 1시간이 걸렸고 32개 작업부터는 답을 내지 못했습니다. 실제 라인은 수십~수백 개 작업을 가지므로 MILP만으로는 실무 규모를 다루기 어렵습니다.
GA를 설계하면서 신경 쓴 부분
1. 염색체를 두 조각으로
염색체는 작업 배치 파트와 비숙련공 배치 파트로 나눴습니다. 작업 배치에는 작업마다 실수형 랜덤 키(random key)를 하나씩 두고, 비숙련공 배치에는 각 작업에 비숙련공을 붙일지 결정하는 0/1 비트를 두었습니다.
랜덤 키 방식은 선행 작업이 없는 후보 가운데 키 값이 큰 것을 먼저 뽑아가는 방식으로 디코딩합니다. 어떤 키 벡터가 들어와도 항상 유효한 작업 순서가 나옵니다. 교차와 돌연변이 뒤에 복구 절차가 필요 없다는 점이 큰 장점입니다.
2. 숙련공 배치는 GA가 아니라 휴리스틱으로
숙련공 배치까지 염색체에 넣으면 탐색 공간이 너무 커집니다. 그래서 작업 순서가 정해지면 누적 작업시간으로 스테이션을 자르고, 배치 가능한 숙련공 후보가 가장 적은 스테이션부터 채웠습니다. 그중 급여가 가장 낮은 사람을 고르고, 후보가 비는 스테이션이 생기면 조합을 다시 찾습니다. 제약이 심한 곳부터 결정한다는 CSP의 MRV 휴리스틱과 같은 발상입니다.
3. 연산자
- 부모 선택은 초반의 과도한 지배를 막는 랭크 기반 방식을 썼습니다.
- 작업 파트에는 실수형 랜덤 키에 맞는 convex hull crossover를, 비숙련공 파트에는 1점 교차를 적용했습니다.
- 돌연변이는 작업 파트의 swap과 비숙련공 파트의 비트 반전으로 구성했습니다.
- 50,000세대 또는 2,000세대 동안 0.1% 미만 개선 시 종료했습니다.
결과
GA는 C# / .NET Framework 4.0으로 직접 구현했고, Pentium IV 3.2GHz·2GB RAM 환경에서 실행했습니다. MILP가 최적해를 낸 9~21개 작업의 모든 소규모 사례에서 GA는 같은 최적값을 찾았고, 시간은 수 배에서 수십 배 짧았습니다. 예를 들어 21개 작업 사례는 MILP 약 3,800초, GA 약 110초였습니다.
MILP가 포기한 32개 작업 사례와 61개 작업·29명 규모에서도 GA는 해를 냈습니다. 61개 작업 사례에서는 스테이션 12개, 숙련공 23명, 비숙련공 23명으로 연간 약 318만 달러 구성과 평균 약 25분의 실행 시간이 나왔습니다.
지금 다시 보면
정확해법과 메타휴리스틱을 검증 쌍으로 쓰는 방식은 지금도 유효합니다. 작은 문제에서는 MILP로 정답을 확보해 GA를 검증하고, 큰 문제는 GA에 맡깁니다. 지금이라면 LINGO 대신 OR-Tools CP-SAT나 Gurobi를 고려할 수 있겠지만, 수백 개 작업 규모에서 휴리스틱과 메타휴리스틱이 필요한 이유는 여전히 남아 있습니다.
사람이 다 같지 않다는 전제도 중요합니다. 스킬 매트릭스, 급여 차이, 협업에 의한 시간 단축은 조립라인뿐 아니라 우편 물류센터의 작업 배치, 전기설비 점검 인력 스케줄링, 소프트웨어 팀의 태스크 배정에도 적용할 수 있는 구조입니다.
다시 확장한다면 비숙련공의 시간 단축량 γi를 상수가 아니라 학습곡선으로 두거나, 비용과 라인 유연성을 함께 보는 다목적 최적화로 발전시켜 보고 싶습니다.
원문: Moon, I., Shin, S., Kim, D. (2014). Integrated Assembly Line Balancing with Skilled and Unskilled Workers. IFIP APMS 2014, Ajaccio, France, pp. 459–466. Springer. HAL: hal-01388577 (CC BY 4.0)
#조립라인밸런싱 #AssemblyLineBalancing #MILP #유전알고리즘 #GeneticAlgorithm #메타휴리스틱 #생산최적화 #스케줄링 #산업공학 #운영연구 #최적화알고리즘 #ORtools
