열처리 공정의 생산스케줄 수립과 적용에 관한 연구
최 민 철*
A Study on Heat-Treatment Process Scheduling for Heavy Forged Products using MIP
Min Cheol Choi*
Abstract
The purpose of this study is to formulate and solve the scheduling problem to heat-treatment process in forging process and apply it to industries. Heat-treatment is a common process in manufacturing heavy forged products in ship engines and wind power generators. Total complete time of the schedule depends on how to group parts and assign them into heat furnace. Efficient operation of heat-treatment process increases the pro- ductivity of whole production system while scheduling the parts into heat-treatment furnace is a combinatorial problem which is known as an NP-hard problem. So the scheduling, on manufacturing site, relies on engineers' experience.
To improve heat-treatment process schedule, this study formulated it into an MIP mathematical model which minimizes total complete time. Three methods were applied to example problems and the results were compared to each other. In case of small problems, optimal solutions were easily found. In case of big problems, feasible solutions were found and that feasible solutions were very close to lower bound of the solutions. ILOG OPL Studio 5.5 was used in this study.
Keywords：Heat-Treatment Process, Scheduling, NP-Hard Problem, MIP
논문접수일：2012년 06월 14일 논문수정일：2012년 07월 06일 논문게재확정일：2012년 07월 10일
* 동아대학교 경영학과
1. 서 론
본 연구는 금속의 대형 단조제품의 가공공정에 서 가장 공정시간이 길고 병목공정인 열처리 공정 의 생산일정수립과 적용을 위한 연구이다. 열처리 공정의 운영환경과 현장에서의 제품의 투입방법을 알아보기 위해 경남 양산시에 소재하고 있는 Y사 를 방문하고 열처리 공정의 일정계획에 대한 연구의 필요성을 확인하였다. Y사는 Rotor Shaft, Tower Flange 등의 풍력발전 부품과 Connecting Rod, Pis- ton Rod 등의 선박엔진부품, Rudder Stock, Pro- peller Shaft 등의 조선기자재와 같은 대형 단조제 품을 생산하는 회사이다.
여기서 단조란 금속의 성질이 우수한 제품을 만 들기 위하여 원자재 금속을 가열한 후 압축 및 두 드림으로 형상을 변형시키는 작업을 말한다. 단조 가공에서는 열처리 공정을 통해서 금속의 내부 결 정구조를 균일하게 만들어서 내부 결함을 없애고, 연성 및 전성을 튼튼하게 하여 무거운 하중이 장 시간 반복되어도 견딜 수 있는 제품을 만들 수 있 다. Y사가 생산하는 제품은 아주 크고 무게가 수 톤∼수십 톤에 이르러 열처리로에 투입되면 제품 에 따라서 10∼70시간의 작업시간이 소요된다. Y 사에서는 열처리공정이 병목구간이 되며 전체 생 산공정의 생산성을 결정하는 주요 공정이 된다. 따 라서 처리능력(capacity, ton)이 각각 다른 열처리 로에 열처리 작업시간과 무게, 주문량이 다른 제품 들을 어떻게 조합하여 언제 투입하느냐에 따라 전 체 시스템의 생산성이 크게 달라진다. 하지만 현장 에서는 열처리 공정의 제품투입을 위한 과학적인 일정계획 수립방법이 없어서 작업자의 경험에 의 존하고 있는 실정이다. 이로 인해서 병목공정(열처 리로) 앞에서 대기 중인 재공품재고가 쌓이고 경 우에 따라서는 재공품이 변질됨으로써 이전 단계 의 공정에 재투입되고 다시 열처리로 앞에서 병목 구간을 형성함으로써 다른 제품의 투입이 지연되 는 악순환이 되풀이 되고 있다.
본 연구에서는 이러한 단조품 제조공정에서의
문제점을 해결하기 위해서 열처리로 용기의 제품 투입 방법에 관해서 연구하기로 한다. 여기서 용기 (bin)란 열처리로에 제품을 담아서 투입하는 일종 의 적재함을 말한다. 따라서 본 연구의 문제는 용 기에 투입할 제품의 조합을 구성하여 그것의 투입 순서를 정하는 것이다. 조합구성은 뱃치(batch) 구 성을 말하며 투입순서는 스케줄 수립을 말한다. 각 열처리로의 뱃치 작업의 작업완료시간은 투입되는 제품의 조합에 따라 다르다. 즉 열처리 작업시간과 무게, 주문량이 상이한 제품들을 합리적으로 조합 하여 투입함으로써 각 열처리로의 작업완료시간을 단축하여 전체 생산일정의 작업완료시간을 최소화 하는 것이 본 연구의 목적이다.
이 문제를 이론적 연구와 결부시켜보면 빈 패킹 문제(bin-packing problem)와 생산스케줄 수립문 제가 결합된 문제로 불 수 있다. 빈 패킹 문제는 다양한 용량의 제품(item)을 용기(bin)에 넣는 조 합문제로 를 용기들의 집합으로 를 제품들의 집 합으로 하고 만큼 각 용기의 사용비용이 들며 각 제품 는 만큼 용기(bin)의 용기능력(capacity)을 소모하고, 각 용기는 만큼 수용능력이 있다. 그 리고 는 용기 를 사용하면 1, 아니면 0으로 표 현되고 는 용기 에 제품 를 넣으면 1, 아니면 0으로 표현된다면 빈 패킹 문제는 다음의 수리적 모형으로 나타낼 수 있다.
Min
∈s.t ∈
≤ ∀ (1)
∈ ∀ (2)∈ ∀
∈ ∀
위에서 목적 함수식은 제품을 모두 용기에 담았 을 때 용기사용비용의 합을 최소화한다는 것을 의 미하고 제약식 (1)은 사용되는 용기에 담기는 제품 의 용량의 합은 용기의 용량을 초과할 수 없음을 나타내는 것으로 는 제품 의 길이, 무게, 부피
등을 의미하는 용기능력 소모량이다. 따라서 부등 식의 왼편은 용기 에 담겨지는 제품 들의 용량 의 합을 의미한다. 부등식의 오른편은 용기 의 수 용가능한 용량이 되고 용기 가 사용될 때만 가 1이 되어 용량 을 갖게 된다. 제약식 (2)는 위의 표에서 나타낸 것과 같이 각 제품은 쪼갤 수 없고 어느 용기에든 반드시 한곳에 담겨야 함을 나타낸 다. 이 때 와 는 용기 에 제품을 넣거나 용 기 가 사용되었을 때만 1을 가지게 되고 그렇지 않은 경우에는 0의 값을 가져 용량이나 비용함수 에 영향을 주지 않는다. 또한 는 용기에 투입된 제품의 개수나 적재용량과 관계없이 사용하게 되 면 1의 값을 가진다. 그리고 모든 용기의 사용비용 이 같을 때에는 모든 값들이 같으므로 1로 간주 되고, 이 문제는 용기의 사용 개수를 최소화하도록 목적함수가
∈로 바뀌게 된다.이러한 빈 패킹 문제는 NP-hard 문제로 모든 경우의 수를 모두 확인해 보는 방법 외에는 최적 의 해를 구할 수 없기 때문에 최적해에 근접한 해 를 찾는 휴리스틱(Heuristic) 방법이 연구되고 있 다. 빈 패킹의 휴리스틱 방법으로는 Eilon[5] 등의 FFD(FFD : first fit decreasing)와 Johnson[7] 등의 BFD(BFD : best fit decreasing) 방법이 있다. FFD 는 용기에 투입될 제품들을 내림차순으로 정렬한 후 용기를 순서대로 검사해 가면서 해당 제품을 채울 수 있는 첫 번째 용기에 채우는 방법이고, BFD는 용기에 투입될 제품들을 내림차순으로 정 렬한 후 모든 용기를 검사해서 각 용기에 제품을 채웠을 경우 남는 영역이 가장 적은 용기에 채우 는 방법이다. 이러한 휴리스틱 방법을 이용하면 최 적해는 아니더라도 최적해의 한계값(상한값 또는 하한값)을 정할 수 있기 때문에 실제 적용에서는 해의 개선의 기준으로 삼을 수 있다.
위와 같은 휴리스틱 방법 외에도 유전자 알고리즘 방면에서도 연구가 진행되었다. Arthur and Roger[4]
등은 “highly fit sequence”와 “sliding window”를 이용했는데, 이 방법은 조기수렴(premature-con-
vergence)의 가능성이 있다는 단점이 있다. 또한 Sami Khuri[9] 등은 정수 문자열과 “graded penalty term”을 이용했으나 이 방법은 비록 다음 세대에서 자식을 생성하지는 않더라도 용기 채우기 문제의 제한을 만족하지 않는 개체가 생성된다는 단점이 있다. 한편, 고려해야할 제약이 2개가 되면 2개 차원 의 빈 패킹(two-dimensional bin packing : 2CBP) 에 해당한다. 이처럼 2개 차원의 빈 패킹 문제도 NP-hard 문제인데[8], Spieksma[10]는 2CBP를 적 재와 스케줄링에 응용하는 휴리스틱 해법과 분지 한계탐색법을 연구하였다.
빈 패킹 문제는 산업현장의 실제 문제에도 응용 되고 있다. 박상혁[1] 등은 제철소 후판공장에서 두꺼운 슬라브(slab)를 압연하여 사각 형태의 철판 인 날판을 생산하고 절단할 때 최소 개수의 슬라 브를 이용하여 주어진 주문을 생산하는 모형을 제 시하였다. 그리고 효율성을 검증하였다. 이영덕[3]
은 빈 패킹 문제의 모형을 수정하여 산업현장에서 발생하는 컨테이너 적재사례에 다루었다. 컨테이 너 적재는 3차원 적재문제가 되지만 적재화물의 특성을 이용하여 모듈화 하여 1차원 빈 패킹 문제 로 변환하였고 실제 현장의 컨테이너 적재문제를 쉽게 다룰 수 있는 사례를 제시하였다. 안혜환[2]
등은 근거리 무선 인터페이스 표준인 블루투스(Blue- tooth)의 패킷(packet) 스케줄링 문제에 다루었다.
현재 패킷 스케줄링 방식이 많은 슬롯과 시간을 낭비하게 되어 최적화된 업링크와 다운링크에 적 합하지 않았다. 따라서 빈 패킹을 이용한 패킷 스 케줄링 모형을 제안하고 시뮬레이션을 통해서 그 성능이 기존 방식에 비해 우월함을 보였다.
본 연구는 열처리로라는 용기에 제품을 조합하 여 투입하고 이때 제품들의 용량의 합은 열처리로 의 용량을 초과할 수 없으며 모든 제품이 투입되 어야 한다는 점에서 기존의 빈 패킹 문제와 유사 하다. 그러나 본 연구에서는 열처리로 용기의 사용 개수를 최소화 하는 것이 아니라 열처리로의 누적 작업완료시간을 최소화 하여 전체 작업시간을 최 소화 한다는 점에서 차이가 있다. 용량제한 뿐만
아니라 시간제한도 포함된다. 실제로 열처리 공정 의 운영개선을 위해서는 열처리의 사용횟수를 줄 이는 것 보다 열처리로의 사용시간을 줄이는 것이 중요하다. 또한 빈 패킹 문제는 용기를 직렬로 나 열하여 그 비용을 따지지만 열처리로 문제는 여러 개의 열처리로가 병렬배치 되어 각 열처리로 중에 서 가장 작업시간이 긴 열처리로의 작업완료시간 이 전체 작업완료시간이 되고 이를 최소화 하는 문제라는 점에서 차이가 있다.
본 연구에서는 알고리즘 해법의 개발보다는 현장의 열처리 공정에서의 전체 작업완료시간을 최소로 하는 제품투입 일정계획을 수립하고 실제 현장의 방법보다 더 나은 제품투입 방법을 찾는데 목표를 두었으며 해를 찾는 데에는 ILOG OPL Studio 5.5 를 사용하였다. 규모가 작은 문제에 대해서는 최적 해를 찾을 수 있었고, 규모가 큰 문제일 경우는 일 정시간 동안 목적함수 값의 개선이 없으면 해 찾 기 과정을 멈추고 그 해를 최적해에 근접한 해로 간주한 뒤 근접해가 얼마나 최적해에 근접하는지 에 대해 설명하였다. 또한 논문에서 제안한 수리모 형에 대한 적합성은 최적해를 미리 아는 문제를 몇 개 적용하여 ILOG로 구한 최적해와 비교하는 방법을 사용하였다. 그리고 연구의 실험결과와 실 제 기업에서 사용하는 열처리 공정의 제품투입방 법을 비교해 보았다. 연구에 사용되는 열처리로의 용량, 제품의 종류, 필요작업시간 등의 데이터는 사례기업에서 직접 조사한 것이고, 연구를 진행하 면서 실무자와의 면담 등으로 관계를 유지하였다.
2. 열처리 공정의 일정계획 수립 모형
2.1 열처리 공정의 운영환경 및 특성
본 연구는 개의 제품과 서로 다른 처리능력을 가지는 개의 열처리로의 상황을 고려한다. 개 의 제품들은 개의 열처리로와 개의 스케줄에 분할 할당된다. 즉 제품 는 열처리로의 번째 스 케줄에 할당되어 있다( ⋯ ,
⋯, ⋯). 또한 제품 는 의 무게 를 가지며, 시간만큼의 열처리 작업이 이루어져 야 한다. 그리고 개의 열처리로와 각 열처리로의
개의 스케줄에서 처리해야할 개의 주문량이 있 다고 가정한다. 본 연구에서 고려해야할 열처리 공 정의 운영환경과 특성은 다음과 같다.
① 처리능력(capacity, ton)이 다른 각각의 열처리 로가 있고, 여기에 투입될 무게(ton)와 작업시 간, 주문량이 다른 제품들이 있다.
② 제품들은 쪼개어서 다른 열처리로에 나누어 투 입할 수 없고(정수), 각 열처리로에 여러 종류 와 개수의 제품이 담길 수 있으나, 열처리로의 용량 을 초과할 수 없다.
③ 제품들의 주문량 을 충족해야 한다.
④ 열처리로가 작업 중일 때에는 중간에 다른 제품 을 투입할 수 없다. 따라서 각 열처리로의 한 묶 음의 작업완료시간은 투입된 제품들 중에서 가장 작업시간이 긴 제품의 작업종료시간이 된다. 이 를 열처리로의 스케줄의 작업시간 라 한다.
⑤ 열처리로의 개의 스케줄이 모두 완료되는데 걸리는 시간이 열처리로의 작업완료시간이 되 고 이는 열처리로의 스케줄들의 작업시간의 합으로 구할 수 있다. 이를 열처리로의 누적 작업완료시간이라 한다.
⑥ 각 열처리로가 병렬로 운영되므로 모든 제품들 의 주문량을 완료하는 전체 작업완료시간은 각 열처리로의 누적작업완료시간 중 가장 긴 열처 리로의 누적작업완료시간이 된다.
이러한 환경에서 본 연구의 목적은 모든 제품들의 주문량을 완료하는 열처리공정의 전체 작업완료시 간을 최소화 하는 일정계획을 수립하는 것이다.
2.2 열처리 공정 운영의 예
열처리 공정의 운영과 본 연구의 문제에 대한 이해를 위해서 다음의 예제를 설명한다. <표 1>과
같이 3종류의 제품과 각 제품의 서로 다른 작업시 간, 무게, 주문량이 있고 두 대의 열처리로(25t)가 있다고 가정한다. 열처리로의 용량은 서로 달라도 무관하며 간단한 예시를 위해서 동일한 용량으로 가정하였다. <그림 1>를 통해 2대의 열처리로에 투입해야할 제품들의 일정계획을 알 수 있다. = 3인 각 제품 가 = 2인 각 열처리로 에 주문량
개 만큼 투입함을 알 수 있다. A열처리로의 첫 번째 작업일정에는 5t, 7t, 10t 제품이 하나씩 투입 이 되었으며 작업 중에는 다른 제품을 투입하거나 중단할 수 없으므로 작업시간이 가장 긴 제품의 종료시간이 첫 번째 작업일정의 작업시간으로 20 시간이 걸렸다. A열처리로는 4번의 일정으로 작업 을 마쳤으며 A열처리로의 누적 작업완료시간은 65시간이 되고, B열처리로는 5번의 일정으로 작업 을 마쳤으며 누적 작업완료시간은 80시간이 된다.
각 제품별 주문량을 모두 완료하는 전체 작업완료 시간은 두 열처리로의 누적 작업완료시간 중 큰 값인 80시간이 된다. 본 예제의 투입일정계획은 최 적해가 아니며 열처리로의 개수와 주문량, 제품의 종류, 작업시간, 용량 등이 많아질수록 일정계획을 수립하는 것은 매우 어려운 문제가 된다.
<표 1> 열처리로에 투입될 제품의 정보 Item 1 Item 2 Item 3
작업시간(시간) 10h 15h 20h
무게(ton) 5t 7t 10t
주문량(개) 11 12 5
<그림 1> 2대의 열처리로에 제품 투입 예제
2.3 수리모형
열처리 공정에서 전체 작업완료시간을 최소로 하 기 위한 각 열처리로에 제품을 투입하는 일정계획 문제를 정수계획모형(Mixed Integer Programming) 으로 표현하면 다음과 같다.
(1) Subject to
×≦ ∀ (2)
≦× ∀ (3)
×≦ ∀ (4)
≦ ∀ (5)
∀ (6)All variables are non-negative 여기에서
: 주문이 들어온 제품의 종류, ⋯
: 제품 의 무게, ⋯
: 제품 의 열처리 시간, ⋯
: 제품 의 주문량, ⋯
: 번째 열처리로, ⋯
: 번째 열처리로의 생산능력, ⋯
: 열처리의 스케줄, ⋯
: 제품 가 열처리로 의 스케줄 에 투입되 는 개수(정수)
: 제품 가 열처리로 의 스케줄 에 투입되 면 1, 그렇지 않으면 0
: 열처리로 의 스케줄 의 열처리 시간
: 전체 작업완료시간
식 (1)은 열처리로의 전체 작업완료시간을 최소 화 한다는 것을 의미하고, 식 (2)는 열처리로에 투입 되는 제품들의 무게의 합은 열처리로의 용량을 초 과할 수 없다는 것을 의미하며, 식 (3)은 열처리로에 여러 개의 제품이 투입될 수 있음을 나타낸다.
는 이진변수로 열처리로에 한 묶음(batch)에 투입될
<그림 2> 예제문제의 최적 투입일정계획
<그림 3> 예제문제의 최적투입일정계획(ILOG)
순번 제품무게
(ton)
열처리시간 (시간)
주문량 (개)
열처리로 생산능력
(ton) 최적값 ILOG
결과
실행시간 (초)
1 10, 12, 20 5, 20, 20 15, 20, 10 30, 50 180 180 8.1
2 30, 35, 50 20, 30, 45 12, 8, 13 80, 100 285 285 40.8
3 25, 45 12, 20 15, 20 50, 70, 90 120 120 39.3
4 9, 12, 15 12, 15, 15 20, 22, 25 50, 70, 80 66 66 96.1
⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯
10 15, 20 10, 10 10, 10 30, 50 50 50 1.3
<표 3> 수리모형의 검증을 위한 추가실험의 요약 수 있는 제품개수()의 상한 값을 100으로 설정하
여 나타낸 것이다(이는 정수계획법의 모형과 기법 중 고정비 모형(fixed-charge problem)을 표현한 것이 다). 만약 열처리로가 아주 커서 1000개까지도 투입 이 가능하다면 1000 이상의 수를 곱해주면 된다. 식 (4)는 열처리로에 제품이 투입된다면 제품들 중에 서 가장 작업시간이 긴 제품의 종료시간이 해당 열 처리로의 스케줄(작업일정)의 작업시간이 되고, 제 품이 투입되지 않는다면 작업시간은 발생하지 않는 다. 식 (5)는 각 열처리로의 누적작업완료시간들 중 에서 가장 긴 열처리로의 종료시점이 전체 작업완료 시간이 되고, 식 (6)은 주문량 충족에 관한 식이다.
위 수리모형을 검증하기 위해서 최적값을 아는 예 제 문제를 만들어 ILOG로 모델링 및 실행해보고 그 결과가 일치하여 수리모형이 최적값을 찾는지를 알아 보았다. 사용될 예제문제의 정보는 <표 2>와 같다.
<표 2> 수리모형의 검증을 위한 예제의 정보 Item 무게(ton) 열처리시간 주문량
열처리로 20t, 50t
1 10t 10 12
2 20t 20 10
서로 다른 용량을 갖는 두 대의 열처리로에 두 종류의 제품을 투입하는 최적 일정계획은 <그림 2>와 같으며 전체 작업완료시간은 80시간이 걸린 다. 동일한 예제문제를 수리모형에 적용하여 ILOG 로 실행해본 결과는 <그림 3>과 같으며 제품의 투입방법에는 다소 차이가 있으나 전체 작업완료 시간은 80시간으로 동일하다. 따라서 수리모형은
본 연구에 있어서 적합하다고 할 수 있다.
수리모형의 검증을 위해서 제품의 종류와 개수, 열처리 시간, 주문량, 열처리로의 개수, 용량을 바 꿔가며 추가적으로 실험을 하였다. 그 결과 수리모 형을 ILOG로 실행했을 때 모든 문제에서 최적값 을 찾아내었다. 이는 <표 3>과 같다. 1번 실험은 서로 다른 무게와 열처리시간, 주문량을 갖는 3종 류의 제품이 30t, 50t의 용량을 갖는 두 대의 열처 리로에 투입된 것을 의미한다.
3. 열처리 공정 실제 문제에의 적용 과 효과
이 장에서는 사례기업인 Y사의 실제 문제를 앞 서 개발한 수리모형에 적용하여 열처리 공정에서 의 제품투입 일정계획을 3가지 방법으로 수립하고 효과를 설명하고자 한다. 사례기업은 용량이 다른 세 종류의 열처리로를 보유하고 있고, 열처리로에 투입해야할 제품은 총 12종류가 있으며 제품마다 무게와 열처리 작업시간, 주문량이 다르다. 제품 9 는 생산개수가 없으므로 실험에서 제외한다. 사례 기업의 투입될 제품과 열처리로의 내용은 <표 4>
와 같다.
<표 4> Y사의 투입제품과 열처리로의 내용
No 제품명 무게
(ton) 열처리
시간 주문량 열처리로
1 풍력Shaft 14 21 86
150톤 : 1대 100톤 :
3대 60톤 :
1대 2 Piston Crown 7 24 24
3 C/Cover 5 65 10
4 P/ROD 8 48 10
5 TR BAR 13 24 44
6 HJ-BAR 16 24 54
7 C/ROD 11 49 100
8 풍력Shaft 18 15 32 9 Piston Crown 25 36 - 10 C/Cover 18 73 42 11 C/HEAD 17 32 55 12 M/JOURNAL 18 34 1
3.1 사례기업의 일정계획 수립과 비교
사례기업의 문제를 다음의 3가지 방법으로 나누 어서 앞에서 수립된 수리모형을 적용하여 일정계 획을 수립한 뒤 그 결과를 서로 비교해 보았다.
① 제품의 주문량을 대상으로 열처리로 투입계획 을 한꺼번에 수립한다. 이 방법은 전체 제품을 대상으로 전체 작업완료시간을 최소로 하는 일
정계획을 수립하게 된다. 매우 변수가 많아서 현장에서는 접근하지 못하는 방법이다.
② 실제 현장에서 사용하는 방법으로 제품의 주문 량을 작업시간이 작은 것부터 크기순으로 정렬 하여 순서대로 4개씩 묶어서 3개의 제품군으로 그룹화 하여 일정계획을 수립한다. 이 방법은 작업시간이 비슷한 제품들끼리 묶어서 일정계 획을 수립하는 방법으로 ①의 방법보다 한꺼번 에 고려해야할 제품의 수가 줄어들어 일정계획 을 수립하는데 조금 쉽고 작업시간이 긴 제품 과 짧은 제품이 묶이는 문제를 방지하여 일정 별 작업완료시간을 줄일 수 있다.
③ 전체 제품을 대상으로 일정계획을 수립하되, 제 품의 생산개수를 1/4로 나누어 4개의 그룹을 만들어서 일정계획을 수립한다. 이것은 1개월 의 물량을 4개의 주간 단위로 일정계획을 수립 하는 것과 같다. ②의 방법과 같이 작업시간이 비슷한 제품군별로 일정계획을 수립할 경우 작 업시간이 짧은 제품군이 열처리 공정에 투입될 때에는 산출되는 주기가 짧아서 다음 공정이 과열되고, 작업시간이 긴 제품군이 투입될 때에 는 산출 주기가 길어서 앞의 공정에서 완료한 재공품 재고가 증가하고, 다음 공정에서는 작업 물량을 대기하는 경우가 발생할 수 있다. 따라 서 모든 제품을 주간 단위로 일정계획을 수립 하여 소량씩 빈번하게 작업을 완료하면 이러한 현상을 피할 수 있다.
3.1.1 실험 1-모든 제품을 한 번에 일정계획 수립(①의 방법)
<표 4>의 모든 제품과 주문량을 한 번에 용량 이 다른 5대의 열처리로에 투입하는 일정계획을 수립하는 방법이다. 고려해야할 변수가 너무 많 아서 작업자의 경험에 의존하는 현장에서는 쓰 지 못하는 방법이다. <표 4>의 데이터를 바탕으 로 수리모형에 적용하여 ILOG를 실행했는데 마 지막 실행가능해(feasible solution, 근접해)를 찾 은 후 2시간 동안 더 나은 해를 찾지 못하여 실
<표 5> 실험 1의 제품투입 일정계획 열처리로 : 150t
일정 제품별 투입개수 총 투입무게
(t)
작업 시간
누적 작업완료시간
1 2 3 4 5 6 7 8 10 11 12
1 8 144 15
457
2 2 7 148 73
3 10 140 21
4 1 13 150 49
5 1 8 149 32
6 2 8 150 32
7 1 8 149 32
8 11 1 138 49
9 1 8 149 32
10 1 13 150 49
11 2 7 148 73
열처리로 : 100t(1)
일정 제품별 투입개수 총 투입무게
(t)
작업 시간
누적 작업완료시간
1 2 3 4 5 6 7 8 10 11 12
1 5 5 95 49
460
2 6 96 24
3 6 96 24
4 9 99 49
5 6 96 24
6 5 90 73
7 6 96 24
8 7 91 24
9 7 91 24
10 2 4 98 24
11 7 91 24
12 14 98 24
13 1 98 73
행을 중지하고 마지막 해를 최적해에 근접한 해 로 간주하였다. 실험 1의 모든 작업을 완료하는 데에는 총 462시간이 소요되었다. 이 결과를 바 탕으로 열처리로의 제품투입 일정계획을 수립하 면 <표 5>와 같으며 일정계획은 각 열처리로를 중심으로 수립하였다. <표 5>의 150t 열처리로 는 총 11번의 일정으로 작업을 하며 두 번째 일정 에는 7번 제품 2개와 10번 제품 7개가 투입되고 총 무게는 148t(11t×2+18t×7)로 처리용량을 초과 하지 않는다. 이때 150t 열처리로의 두 번째 일정 은 함께 투입된 제품들 중 가장 긴 작업시간이 작업완료시간이 되므로 10번 제품의 작업시간인
73시간이 소요되고 열한번의 각 일정의 작업시 간을 합하면 150t 열처리로의 누적작업완료시간 은 457시간이 된다. 총 5대의 열처리로중에서 가 장 긴 누적작업완료시간이 전체 작업완료시간이 되므로 60t 열처리로가 작업이 완료되는 462시간 이 전체 작업완료시간이 된다. 그리고 2번 제품 은 150t 열처리로에 4개, 100t(1) 열처리로에 14 개, 100t(3) 열처리로에 6개가 투입되어 총 24개 로 주문량을 충족하게 된다. <표 5>의 일정계획 표는 현장의 열처리로 앞에 붙여두고 모든 작업 자가 작업과정을 쉽게 이해할 수 있어서 실제 현 장에 적용할 수 있도록 구성해 보았다.
열처리로 : 100t(2)
일정 제품별 투입개수 총 투입무게
(t)
작업 시간
누적 작업완료시간
1 2 3 4 5 6 7 8 10 11 12
1 7 98 21
457
2 7 98 21
3 2 5 100 73
4 1 5 94 24
5 2 5 100 73
6 7 98 21
7 7 98 21
8 7 98 21
9 6 96 24
10 7 98 21
11 9 99 49
12 1 5 99 32
13 2 4 100 32
14 6 96 24
열처리로 : 100t(3)
일정 제품별 투입개수 총 투입무게
(t)
작업 시간
누적 작업완료시간
1 2 3 4 5 6 7 8 10 11 12
1 7 98 21
460
2 5 90 15
3 5 90 73
4 7 98 21
5 9 99 49
6 6 1 3 95 73
7 6 96 24
8 5 90 15
9 4 6 98 24
10 5 85 32
11 5 2 97 24
12 7 98 21
13 5 90 15
14 7 98 21
15 3 3 99 32
열처리로 : 60t
일정 제품별 투입개수 총 투입무게
(t)
작업 시간
누적 작업완료시간
1 2 3 4 5 6 7 8 10 11 12
1 1 1 1 48 34
462
2 4 52 24
3 3 51 32
4 4 52 24
5 5 55 49
6 4 1 1 60 49
7 2 36 15
8 5 55 49
9 3 54 15
10 5 55 49
11 5 55 49
12 5 55 49
13 4 52 24
실험 일정수립방법 제품그룹 (투입제품)
누적 작업완료시간 그룹별 작업
완료시간
전체 작업 150ton 100ton 100ton 100ton 60ton 완료시간
2
제퓸울 작업시간의 크 기순으로 정렬하여 3개 의 제품군으로 그룹화 하여 스케줄링
그룹 1
(1, 2, 5, 8) 108 108 108 108 102 108 (근접해)
482 그룹 2
(4, 6, 7, 11) 226 225 227 228 226 228 (근접해) 그룹 3
(3, 10, 12) 146 146 146 146 146 146
(최적해)
합계 480 479 481 482 474
<표 7> 실험 2의 결과 요약
<표 8> 실험 3을 위한 제품 그룹 제품종류(개수)
1 2 3 4 5 6 7 8 9 10 11 12
그룹 1 22 6 3 3 11 14 25 8 0 11 14 0
그룹 2 22 6 3 3 11 14 25 8 0 11 14 0
그룹 3 22 6 3 3 11 14 25 8 0 11 14 0
그룹 4 20 6 1 1 11 12 25 8 0 9 13 1
합계 86 24 10 10 44 54 100 32 0 42 55 1
3.1.2 실험 2-실제 기업의 운영방법을 반영한 실험(②의 방법)
실험 2는 실제 사례기업에서 사용하는 방법으로 제품을 작업시간이 작은 것부터 크기순으로 정렬 하여 순서대로 4개씩 묶어서 총 3개의 그룹으로 만들었다. 이는 <표 6>과 같다.
<표 6> 실험 2를 위한 제품 그룹 그룹 1 제품 1, 2, 5, 8 그룹 2 제품 4, 6, 7, 11 그룹 3 제품 3, 10, 12
<표 5>와 같은 방법으로 각 제품의 그룹별로 5개의 열처리로에 투입하는 일정계획을 수립하였으며 상 세한 일정계획은 생략한다. 그룹 1과 그룹 2는 ILOG 실행 결과 마지막 실행가능해를 찾은 후 2시간 동안 더 나은 해를 찾지 못하여 실행을 중지하고 마지막 해를 근접해로 간주하였다. 그룹 1의 작업완료시간 은 총 108시간, 그룹 2는 총 228시간이 소요되었다.
그룹 3은 문제의 크기가 작아서 1.28초 만에 최적해 를 찾았으며 작업완료시간은 총 146시간이 소요되었
다. 모든 주문량을 완료하는데(3개의 그룹의 모든 작 업을 마치는데) 걸린 시간을 의미하는 전체 작업완 료시간은 각 열처리로의 누적작업완료시간을 합한 것 중에서 가장 긴 시간이 되고 482시간이 걸렸다.
이는 실험 1의 방법보다 더 오래 걸린 것으로 실제 기업에서는 더 나은 제품투입 일정계획 수립방법이 있음에도 불구하고도 활용하지 못하고 있음을 알 수 있다. 실험 2의 결과는 <표 7>과 같다.
3.1.3 실험 3-주문량을 1/4로 나누어서 일정계획 수립
실험 3은 전체 제품을 대상으로 일정계획을 수 립하되, 제품의 주문량을 1/4로 나누어 4개의 그룹 을 만들어서 일정계획을 수립한다. 즉 제품의 주문 량을 소량씩 빈번하게 완료되도록 해서 모든 제품 이 비슷한 분포로 산출될 수 있도록 일정계획을 수립함으로써 작업시간이 비슷한 것끼리 묶었을 경우에 발생하는 문제를 피하는 방법이다. 열처리 로에 투입될 제품을 <표 8>과 같이 그룹 1～그룹 3은 동일하게 주문량을 배정하고, 남은 제품의 개 수를 그룹 4에 배정하였다.
실험 일정수립방법 제품그룹 (투입제품)
누적 작업완료시간 그룹별 작업
완료시간
전체 작업 150ton 100ton 100ton 100ton 60ton 완료시간
3
전체 제품을 대상으로 하되, 제품의 개수를 1/4 로 나누어서 주간 단위 로 일정계획 수립
그룹 1
(모든 제품) 120 118 123 122 96 123
(근접해)
481 그룹 2
(모든 제품) 120 118 123 122 96 123
(근접해) 그룹 3
(모든 제품) 120 118 123 122 96 123
(근접해) 그룹 4
(모든 제품) 112 113 112 112 107 113
(근접해)
합계 472 467 481 478 395
<표 9> 실험 3의 결과 요약
실험 제품그룹 작업완료시간-ILOG 결과 이론적 하한값 차이
1 모든 제품 462(근접해) 429.667 6.99%
2
그룹 1(1, 2, 5, 8) 108(근접해) 101.341 6.17%
그룹 2(4, 6, 7, 11) 228(근접해) 212.541 6.78%
그룹 3(3, 10, 12) 146(최적해) 115.784 20.69%
3
그룹 1(모든 제품) 123(근접해) 110.031 10.54%
그룹 2(모든 제품) 123(근접해) 110.031 10.54%
그룹 3(모든제품) 123(근접해) 110.031 10.54%
그룹 4(모든 제품) 113(근접해) 99.573 11.88%
<표 10> 이론적 하한값과의 비교 그룹 1～그룹 3은 동일한 제품의 종류와 개수를
가지므로 같은 일정계획을 수립하게 된다. ILOG 실행 결과 마지막 실행가능해를 찾은 후 2시간 동 안 더 나은 해를 찾지 못하여 실행을 중지하고 마 지막 해를 근접해로 간주하였다. 하나의 그룹의 작 업을 완료하는 데에는 123시간이 걸렸다. 그룹 3개 가 모두 동일한 일정계획을 가지므로 3개의 그룹 이 모두 작업완료시간은 동일하다. 그룹 4는 작업 을 완료하는데 113시간이 걸렸다(근접해). 실험 3 의 전체 작업완료시간은 각 열처리로의 누적작업 완료시간 중 가장 긴 시간인 481시간이 된다. 이 방법은 실험 2의 결과보다 1시간 단축된 것으로 차이가 거의 없다. 오히려 운영상의 문제를 고려해 볼 때 실제 기업이 사용하는 실험 2의 방법보다 주문량을 나누어서 일정계획을 수립하는 실험 3의
방법이 더 나을 수 있음을 의미한다. 실험 3의 결 과는 <표 9>와 같다.
3.2 이론적 하한값과의 비교
실험 2의 그룹 3은 최적해로 일정계획을 수립하 였으나 그 외에는 근접해로 수립한 것이다. 최적해 에 의한 전체 작업완료시간과 근접해에 의한 것과 의 차이를 가늠해보기 위해 모든 실험의 결과들을 다음의 공식으로 구해 보았다. 이 공식은 각 제품
의 무게()와 열처리 작업시간(), 주문량()을 곱한 값들을 더한 후 각 열처리로 의 용량()들 의 합으로 나눈 것이다. 이는 작업해야할 모든 제품 들을 쪼개어서 열처리로에 가득 채웠을 때의 전체 작업완료시간으로 ‘이론적 하한값’이라 명명한다.
No 제품별 개수 전체 작업완료시간 (ILOG)
이론적
하한값 차이
1 2 3 4 5 6 7 8 9 10 11 12
1 80 28 10 8 48 45 107 27 0 34 64 13 477 429.7 9.89%
2 71 29 9 7 42 48 124 28 0 35 66 0 472 429.8 8.95%
3 77 26 8 8 45 43 111 24 0 31 83 6 475 429.8 9.56%
4 80 25 9 10 45 45 95 25 0 26 90 20 487 429.7 11.78%
5 94 21 8 7 41 43 83 21 0 33 86 21 467 429.7 7.98%
6 92 25 8 7 35 51 81 17 0 32 91 20 462 429.6 7.02%
7 92 23 11 7 28 45 95 17 0 36 77 18 471 429.8 8.75%
8 90 23 10 7 25 51 106 20 0 31 79 15 471 429.5 8.80%
9 93 24 8 7 29 58 115 16 0 29 68 16 472 429.8 8.95%
10 90 26 7 7 24 53 119 15 0 32 64 17 478 429.6 10.13%
<표 11> 이론적 하한값과의 추가 비교실험
××
실험 1을 위 식에 적용하여 해를 구해본 결과 429.667시간이 나왔다. 본 문제의 정수 최적값은 쪼개어서 담을 수 없으므로 이보다 큰 값을 가지 게 된다. 실험 2의 그룹 3이 최적해임에도 이론적 하한값과 20.69% 차이가 나는 것을 보면 다른 실 험의 근접해들도 모든 경우의 수를 적용해 보지 않아서 최적해의 여부는 알 수 없으나 최적해에 상당히 근접하고 있음을 알 수 있다.
다양한 문제에서도 ILOG의 근접해가 최적해 에 근접하는지 알아보기 위해서 <표 11>과 같이 추가적으로 10개의 문제를 실험해 보았다. 각 제 품별로 주문개수를 변화시켜 랜덤하게 생성하였 는데 이론적 하한값이 비슷하도록 주문개수를 변 화시켜 그 차이를 비교해 보았다. 그 결과 모든 실 험에서 구한 근접해가 이론적 하한값과 7∼12%
의 차이를 보임으로서 최적해와 매우 근접해 있 음을 알 수 있다. 따라서 본 연구에서 개발한 수 리모형과 ILOG 모델은 현장의 일정계획 수립에 큰 도움이 되리라 판단된다.
4. 결 론
열처리로의 제품투입 일정계획은 열처리로의 대수와 제품의 종류, 무게, 작업시간, 주문량이 많아질수록 매우 복잡한 문제가 된다. 또한 대형 단조제품의 생산 공정에서 생산성을 결정하는 주 요 공정인 열처리 공정은 작업시간, 주문량, 무 게가 다른 제품들을 어떻게 조합하여 열처리로 에 투입하느냐에 따라 전체 공정의 생산성이 달 라진다. 하지만 현장에서는 작업자의 경험에 의 존하여 열처리로의 제품투입 방법을 결정하고 있는 실정이다. 이에 본 연구에서는 열처리 공정 의 운영개선을 위해 전체 작업완료시간을 최소 로 하는 제품투입 일정계획의 모형을 수립하였 고 3가지 실험을 통해서 일정계획의 수립방법과 차이를 설명하였다. 그 결과 실제 현장에서는 더 나은 일정계획 수립방법이 있음에도 불구하고 그렇지 못한 방법을 사용하고 있는 문제점을 발 견하였다. 그리고 개선방법을 제시하였다. 그리 고 이론적 하한값과의 비교를 통해서 본 연구의 모형을 활용하면 비록 근접해로 일정계획을 수 립하여도 실제 최적해와 매우 근접한 결과를 얻 을 수 있음을 밝혔다.
본 연구는 실제 현장에서 과학적인 방법으로 열 처리 공정의 일정계획을 수립할 수 있는 방법을 상세히 설명하였고, 현장의 방법보다 더 나은 적용 방법을 제시한 것에 의의가 있다.
참 고 문 헌
[1] 박상혁, 장수영, “후판 날판설계를 위한 이차원 빈패킹 최적화 기법”, ｢대한산업공학회/한국 경영과학회 춘계공동학술대회논문집｣, 2006, pp.1-6.
[2] 안혜환, 윤희용, 손재기, 전기만, 양만석, “Bin- Packing과 DRR을 이용한 블루투스 MAC 계 층에서의 효과적인 패킷 스케줄링”, ｢한국정 보과학회 봄 학술발표논문집｣, 제30권, 제1호 (2003), pp.451-453.
[3] 이영덕, “컨테이너 빈패킹문제의 사례연구”, ｢경영 학연구논문집｣, 제10권, 제1호(2003), pp.17-25.
[4] Arthur, L.C. and L.W. Roger, "A Heuristic for Improved Genetic Bin Packing," Infor- mation Processing Letters, 1993.
[5] Eilon, S. and N. Christofides, "The loading problem," Management Science, Vol.17(1971),
pp.259-268.
[6] Gupta, N., D. Jatinder, and C.H. Johnny, "A new heuristic algorithm for the one-dimen- sional bin-packing problem," Prodution Plan- ning and Control, Vol.10, No.6(1999), pp.598- 603.
[7] Johnson, D.S., A. Demers, J.D. Ullman, M.R.
Garey, and R.L. Graham, "Worst-case per- formance bounds for simple one-dimensional packing algorithm," SIAM Journal of Com- puting, Vol.3(1974), pp.299-326.
[8] Monaci, Michele, and Paolo Toth, "A Set- Covering-Based Heuristic Approach for Bin- Packing Problems," INFORMS Journal on Computing, Vol.18, No.1(2006), pp.71-85.
[9] Sami Khuri, and Martin Schutz, "Evolu- tionary Heuristics for the Bin Packing Pro- blem," The ICANNGA, Springer-Verlag, Vienna (1994), pp.285-288.
[10] Spieksma, F.C.R., "A branch-and-bound algo- rithm for the two-dimensional vector packing problem," Comput. Oper. Res., Vol.21(1994), pp.19-25.
