준비시간과 가공시간 그리고 제거시간으로 나누어지는 경우의 flowshop 일정계획

Flowshop scheduling with setup, processing and removal times separated

문기주* , 박재영*

Gee-Ju Moon , Jae-Young Park

Abstract

Operation time can be divided into three different times such as setup time, processing time and removable time.  The setup time and removable times are either independent or dependent of the processing time.  In this paper, the case with independent setup time and dependent removable time to processing time is considered for Johnson's rule application.  A heuristic to find an optimum job sequencing is suggested and comparison studies are followed to evaluated the heuristic's performance with the one's found in the literature.

1. 서론

* 동아대학교 산업시스템공학과

일정계획은 OR 연구가들이나 생산현장에서 근무하는 사람들 모두에게서 많은 관심을 받아온 주제라 할 수 있다. 이 일정계획 관련 문제중 flowshop에서의 순서계획 문제는[eqn: m]대의 기계나 설비들로 구성된 경우에 있어서 모든 작업들이 기계나 설비들에 대하여 동일한 순서로 가공되어지며 총 생산시간으로 정의되는 makespan을 최소화하는 것에 관한 것이다. 특히 두 대의 기계로 구성되는 경우 작업이 순차적으로 이루어져야하는 경우의 작업순서를 결정하는 연구가 Johnson[1]에 의해 이루어졌으며 이 밖에도 flowshop에 대한 많은 연구들[3, 5, 7]이 진행되어왔다. 일반적으로 Johnson rule이라고도 불리우는 이 연구에서는 몇 가지 특별한 가정들이 설정되어있으며 특히 작업변환시간(changeover time)은 순서에 독립적이며 공정시간에 포함되거나 무시되어질 수 있다고 가정한 것이다. 그러나 많은 경우 이러한 작업변환시간들은 여러 부분으로 나누어질 수 있으며 몇 가지의 서로 종속적이거나 독립적인 부분들로 나누어 볼 수 있다.

<그림 1> Flowshop 환경

즉 기계 [eqn: k]에서 작업 [eqn: i]의 공정시간은 가공시간과 함께 준비(setup)에 필요한 준비시간과 제거시간의  합으로 정의될 수 있다. 여기에서 준비시간은 기계 [eqn: k]상에서 작업 [eqn: i]의 공구들이나 치구 등의 준비에 필요한 시간을 말하며 반면 제거시간은 기계 [eqn: k]상에서 작업 [eqn: i]가 완성되기 이전에 공구나 치구들을 제거하는데 필요한 시간을 의미한다.

따라서 가공되는 작업들에 대하여 작업변환시간을 작업순서에 독립적인 요소들로 나누어 분석하는 방법들이 연구되었다. 우선 초기에는 문제를 수식화하고 완전열거법(enumeration)으로 해결할 수 있도록 변형하는 연구[7, 10]가 이루어졌으며 또한 두 대의 기계로 구성된 flowshop에 대하여 makespan을 최소화하는 동적계획법(dyna- mic programming)이 Corwin과 Esogbye[4]에 의해 개발되었다.

하지만 순서에 독립적인 작업변환시간을

가지는 flowshop 문제들은 NP-complete[6]이므로 효율적인 최적화 알고리즘보다는 휴리스틱 알고리즘들의 개발이 요구되고 있으며 이에 대한 연구들이 이루어져 왔다.

Gupta와 Darrow[9]은 두 대의 기계로 구성된 flowshop 문제에 대하여 대략적인 해들을 찾을 수 있는 휴리스틱 알고리즘을 개발하였으며 또한 [eqn: M]대의 기계로 구성된 경우에 TSP(Traveling Salesman Problem)를 바탕으로 한 휴리스틱 알고리즘을 개발한 Gupta[8, 9]에 의해 연구가 이루어졌다.

Sule[11]은 공정시간을 확장하여 가공시간, 준비시간 그리고 제거시간으로 나누어 이에 대한 휴리스틱 알고리즘을 개발하였다. 그 외에도 Sule와 Huang[12]은 3대의 기계로 구성된 flowshop문제로 확장하였으며, 보다 다양한 방법들이 Szware[13]등에 의해 연구되기 시작하였다.

<그림 2> 두 대의 기계를 가지는 flowshop공정시간의 도해

본 논문에서 다루는 순서계획 문제는 모든 가공시간이 알려져 있는 정적(static)인 경우의 flowshop 문제를 대상으로 하고 있으며 제안하고 있는 휴리스틱 알고리즘의 목적은 makespan의 최소화에 있다. Flowshop 문제에 대한 일반적인 가정들 이외에 공정시간을 준비시간, 가공시간 그리고 제거시간으로 나누어질 수 있는 경우에 대한 Sule의 연구에 대해 제거시간이 가공시간에 종속적인 경우에 대한 분석을 하고 개선 가능한 알고리즘을 제안하였다.

2. 연구내용

두 대의 기계로 구성된 flowshop문제에서, 작업의 가공에 걸리는 시간을 준비시간, 가공시간, 제거시간으로 나누어 처리되어야 하는 경우, Johnson rule을 적용하기 위하여, Ai와 Bi에 배정한 값의 계산방법을 제시한다. 각 기계에 할당되어진 작업들의 연결 공정은 다음과 같이 요약할 수 있다.

① 가공되는 단위에 따라 독립적인 준비   (setup)시간. 이러한 준비시간은 보통 기계들의  셋팅(setting)시간과 필요한 치공구를 가져오는 시간 그리고 설계 도면을 획득하는 시간과 같은 활동들로 구성될 것이다.

②  가공되는 단위에 단위당 종속적인 준비시간. 이것은 아마 필요한 공구들을 조정하고 단위당 치공구들을 준비하는 시간 등이 포함된다.

③  가공시간(processing time)

④ 가공되는 단위에 종속적인 제거(removal)시간. 이것은 아마 각 단위로부터 공구들을 제거하는 시간과 치공구로부터 제거하는 시간 등이 포함된다.

⑤  가공되는 단위에 독립적인 제거시간. 이 시간은 공구들과 치공구들을 해체하는 시간 등 을 포함한다.

위에서 활동 2, 3 그리고 4는 작업 단위에 종속적이므로 이들 시간들은 합쳐질 수 있고 또한 가공시간으로써 나타낼 수 있으나 활동 1, 5는 가공되는 단위당 가공시간에 대하여 독립적이다. 이러한 경우 각 시간치 별로 변환하여 Johnson rule을 적용시킬 수 있을 것이며, 각 시간치는 다음과 같이 정의한다.

[eqn: S_i^k] = 기계 [eqn: k]에서의 작업 [eqn: i]에 대한 단위

당 독립적인 준비시간.

단, [eqn: i] = [eqn: 1, `2, ` DOTSLOW ,` n] ,[eqn: k] = [eqn: 1, `2].

[eqn: P_i^k] = 기계 [eqn: k]에서의 작업 [eqn: i]에 대한 가공

시간. 이 시간은 활동 2, 3 그리고

4를 포함한다.

[eqn: R_i^k] = 기계 [eqn: k]에서의 작업 [eqn: i]에 대한 제거

시간.

[eqn: C_i^k] = 기계 [eqn: k]에서의 작업 [eqn: i]의 완성

시간.

문제를 수식화함에 있어 [eqn: i] 번째 가공순서의 작업을 작업 [eqn: i] 로 표현하고 기계 [eqn: k]는 두 대이므로 1은 첫 번째 기계를 2는 두 번째 기계를 나타낸다. <그림 2>에서 보는바와 같이 준비시간은 각 가공단위에 대하여 독립적이기 때문에 만일 기계 2에서 유휴시간(idle time)이 존재한다면 기계 2에서의 준비시간은 기계 1로부터 가공단위가 사용되기 이전에 실행되어질 수 있다. 각 가공단위는 가공이 완성되었을 때 기계 1에서 사용가능하지만 기계는 다음 작업에 대하여 기계상에서 제거공정이 끝나기 전에는 사용할 수 없다.

기계 1에서의 작업[eqn: i] 에 대한 완성시간(completion time)은 다음과 같이 주어진다.

[eqn: C_i^1 = SUM from j=1 to i ` S_j^1 ` + ` P_j^1 ` + ` R_j^1]            ⑴

기계 2에서의 작업[eqn: i] 에 대한 완성시간은 다음과 같다.

만일 [eqn: C_i-1^2 ` + ` S_i^2 ~ < ~ C_i-1^1 `+` S_i^1 ` + ` P_i^1] 이라면 기계 2의 완성시간은(그림 2 참조)

[eqn: C_i^2 = (C_i-1^1` + ` S_i^1 `+ ` P_i^1 )`+`P_i^2 `+ ` R_i^2] ⑵

또는,

[eqn: C_i-1 ^2 ` + ` S_i ^2 ~ >= ~ C_i-1 ^1 ` + ` S_i ^1 ` +` P_i ^1] 이라면

기계 2의 완성시간은

[eqn: C_i^2 ~ = ~ C_i-1^2 `+ ` S_i^2 `+` P_i^2 `+` R_i^2]       ⑶

으로 표현할 수 있다.  따라서,

[eqn: C_i^2 ``=`` MAX``[(C_i-1^1` + ` S_i^1 `+ ` P_i^1 )]

[eqn: , (C_i-1^2 +S_i^2 )]`+`P_i^2 `+ ` R_i^2]   ⑷

가 되고, makespan은 [eqn: C_i^1]과 [eqn: C_i^2]를 비교하여 큰 값을 선택한다. 여기서 두 대의 기계로 구성되는 flowshop문제는 Johnson rule을 적용하여 최적해를 구해낼 수 있다. 기계 1의 준비시간과 가공시간 동안 기계 2는 유휴가 될 것이므로 그 동안 가능한 준비시간이 큰 작업을 배치하고, 가공시간과 제거시간이 큰 작업은 뒤에 배치함이 유리할 것이다.

이러한 개념으로 Sule의 알고리즘은

[eqn: A_i = S_i^1 ` - ` S_i^2 ` + ` P_i^1]

[eqn: B_i = P_i^2 ` + ` R_i^2 ` - ` R_i^1]         ⑸

를 계산하여, Johnson rule을 적용하는 것이다. 여기에서 고찰해야 할 2 가지 변환가능한 것이 생기는데, 첫째, 음수 값에 관한 것이고, 둘째, 1번 기계의 준비시간과 처리시간의 합과 2번 기계의 준비시간에 관한 것이다. 음수 값은 두 값 비교시 편차에 관한 것이므로 절대치를 취하여 처리해 볼 수 있겠고, 현재 Sule의 1번 기계의 준비시간과 처리시간에 2번 기계의 준비시간을 차감한 값을 취하는 것은 그 값들 중 최대 값을 취하여 Johnson  rule을 적용해 볼 수 있겠다. Sule의 계산방식으로 계산된 Ai와 Bi의 값 중에서 음수 값을 가지는 경우 음수 값을 절대치로 만들어 Johnson rule에 적용하는 방법은 절대 부호만 추가하면 되겠고, max 방법은

[eqn: A_i ``=``MAX``[(S_i^1 ` + `P-_i^1 ), ``S_i^2 `]]

[eqn: B_i ``=``MAX``[ (P_i^2 ` + ` R_i^2 ),` R_i^1 `]]      ⑹

으로 표현할 수 있다. 이 3 가지 수치값들은 제거시간이 처리시간에 독립이지 못하여 공정시간이 준비시간과 가공시간으로 나누어지는 경우에 대해 중점적으로 적용하여 비교, 평가한다.

3. 수치실험

3.1 3가지 시간으로 분리된 경우

제안된 휴리스틱 알고리즘과 기존 휴리스틱 알고리즘을 비교하기 위하여 <표 1>과 같이 난수를 발생시켰고, 각 공정시간들을 max 휴리스틱과 Sule의 휴리스틱에 적용한 [eqn: A_i]와 [eqn: B_i]결과는 <표 2>와 같다.

<표 1> 기계 1과 기계 2의 공정시간

시간 작업	기계 1			기계 2
	준비([eqn: S_i^1])	가공([eqn: P_i^1])	제거([eqn: R_i^1])	준비([eqn: S_i^2])	가공([eqn: P_i^2])	제거([eqn: R_i^2])
1	6	12	5	2	1	8
2	3	6	4	8	4	7
3	2	4	1	4	2	5
4	4	8	5	1	1	6
5	1	2	2	5	3	7
6	9	18	8	9	5	8

<표 2> 수식에 의한 결과치

알고 리즘 작업	Sule
	[eqn: A_i]	[eqn: B_i]
1	6+12-2 = 16	1+8-5 = 4
2	3+6-8 = 1	4+7-4 = 7
3	2+4-4 = 2	2+5-1 = 6
4	4+8-1 = 11	1+6-5 = 2
5	1+2-5 = -2	3+7-2 = 8
6	9+18-9 = 18	5+8-8 = 5
알고 리즘 작업	max
	[eqn: A_i]	[eqn: B_i]
1	max{(6+12), 2} = 18	max{(1+8), 5} = 9
2	max{(3+6), 8} = 9	max{(4+7), 4} = 11
3	max{(2+4), 4} = 6	max{(2+5), 1} = 7
4	max{(4+8), 1} = 12	max{(1+6), 5} = 7
5	max{(1+2), 5} = 5	max{(3+7), 2} = 10
6	max{(9+18), 9} = 27	max{(5+8), 8} = 13

<표 2>에서 계산된 결과를 Johnson rule에 적용한다면 작업의 순서를 결정할 수 있으며 이에 대한 작업순서와 makespan은 <표 3>과 같다.

<표 3> 예제결과

알고리즘 결과	Sule	max
작업순서	5-2-3-6-1-4	5-3-2-6-1-4
기계 1	90	90
기계 2	92	92
makespan	92	92

<표 3>에 나타난 결과와 같이 두 방법의 작업순서가 다름에도 불구하고 같은 결과가 나온 것은 3가지 시간치로 나누는 경우의 문제는 제약이 느슨하여 어떤 방법이나 좋은 해를 잘 찾는다는 것을 나타내고 있으며 또한 보다 많은 수치실험으로 결과를 비교할 필요성을 보인 것이라 하겠다.

일반적인 경우를 평가하기 위하여 computer program을 작성하여 작업의 수를 10개로 하고, 각 시간 값에 난수를 발생시켜 Sule의 방법과 max방법으로 각각 10회씩 실험을 실시한 결과는 <표 4>와 같다. 표에 정리한 실험결과를 보면 큰 차이를 보이진 않으나 Sule의 방법이 항상 같거나 좋은 해를 찾았으므로 최적해를 찾는데 유용한 방안이 된다고 하겠다.

3.2  2가지 시간으로 분리된 경우

대다수의 공정에서 제거시간을 공정시간에서 독립된 것으로 처리하기보다는 가공시간의 일부로 처리하는 경우가 많다.  따라서 2가지의 시간치로 처리하는 경우에 작업순서를 결정하는 경우 Sule과 max를 비교분석하기로 한다.

공정시간을 3가지 시간, 준비□가공□제거시간으로 나눈 경우에는 Sule의 알고리즘이 효과가 있는 것으로 나타났는데, 만약 제거시간이 가공시간에 종속되어 없는 경우, 공정시간을 준비와 가공시간으로만 간주하고 문제를 해결할 때는 어떠한 rule이 적용되는 것이 합당한가를 수치실험을 통해 나타내고자 한다.  이때 적용되는 알고리즘은 Sule의 방법과 max방법을 적용하여 makespan의 최소화를 주는 순서를 찾고자 한다.

Sule의 알고리즘은 식⑴⑵⑶⑷에서 제거시간에 관계된 시간 값들만 없앰으로써,

[eqn: C_i^1 = SUM from j=1 to i ` S_j^1 ` + ` P_j^1 `]                  ⑺

[eqn: C_i^2 ``=`` MAX``[(C_i-1^1` + ` S_i^1 `+ ` P_i^1 )]

[eqn: , (C_i-1^2 +S_i^2 )]`+`P_i^2 `]  ⑻

와 같이 작업완료시간을 구할 수 있고, 이때 Sule의 작업순서를 결정하는 [eqn: A_i]와 [eqn: B_i]는

[eqn: A_i = S_i^1 ` - ` S_i^2 ` + ` P_i^1]

[eqn: B_i = P_i^2]                ⑼

가 된다.  또한 max방법에 의한 작업순서를 결정하는 [eqn: A_i]와 [eqn: B_i]는 ⑽과 같이 구해진다.

[eqn: A_i ``=``MAX``[(S_i^1 ` + `P-_i^1 ), ``S_i^2 `]]

[eqn: B_i ``=P_i^2]	⑽

<표  4> 3개 시간 분리 경우 수치실험결과

회수	알고리즘	기계1	기계2	make span	차이	%
1	Sule	1650	1638	1650	32	101.94
	max	1650	1682	1682
2	Sule	1428	1414	1428	8	100.56
	max	1428	1436	1436
3	Sule	1375	1555	1555	41	97.43
	max	1375	1596	1596
4	Sule	1270	1598	1598	0	100
	max	1270	1598	1598
5	Sule	1434	1416	1434	16	101.01
	max	1434	1450	1450
6	Sule	1469	1447	1469	38	102.59
	max	1469	1507	1507
7	Sule	1855	1840	1855	0	100
	max	1855	1852	1855
8	Sule	1103	1272	1272	60	104.72
	max	1103	1332	1332
9	Sule	1604	1549	1604	37	102.31
	max	1604	1641	1641
10	Sule	1442	1539	1539	0	100
	max	1442	1539	1539

위의 알고리즘에 의한 수치실험은 작업이 10개인 경우를 모의실험하여 그 결과를 <표5>에 정리하였다.

<표5>의 결과를 살펴보면, Sule의 알고리즘보다 max방법에서 보다 나은 결과치들이 나타나고 있다. 예를 들면, 4번은 우수한 결과치들이, 5번은 동일한 결과값이 만들어졌다.

따라서 공정시간이 3가지로 나누어지는 경우와는 달리 2가지 시간, 즉 준비시간과 가공시간으로 나누어지는 경우에는 Sule의 방법이 좋은 순서를 찾아내지 못한다는 것을 알 수 있으므로 max 방법과

<표 5>  2개 시간 분리 경우

수치실험 결과

회수	알고리즘	기계1	기계2	make span	차이	%
1	Sule	1085	1133	1133	0	100
	max	1085	1133	1133
2	Sule	1107	1116	1116	0	100
	max	1107	1116	1116
3	Sule	927	985	985	-44	95.53
	max	927	941	941
4	Sule	1015	1201	1201	10	100.83
	max	1015	1211	1211
5	Sule	1176	1179	1179	0	100
	max	1176	1179	1179
6	Sule	1062	1085	1085	-12	98.89
	max	1062	1073	1073
7	Sule	782	1105	1105	0	100
	max	782	1105	1105
8	Sule	970	1048	1048	-75	92.84
	max	970	973	973
9	Sule	762	879	879	0	100
	max	762	879	879
10	Sule	1018	1026	1026	-5	99.51
	max	1018	1021	1021

동시적용하여 좋은 해를 사용하는 것이 추천된다 하겠다.

4. 결론

공정시간은 일반적으로 준비□가공□제거시간으로 나누거나 혹은 제거시간은 가공시간의 종속시간으로 취급하여 준비시간과 가공시간 두 가지로 나누어 flowshop의 순서계획을 수립하고 있다. 특히 작업을 수행하는 기계가 순차적으로 사용되는 두 대의 기계로 구성된 flowshop의 경우에는 Johnson rule을 적용하여 최적의순서를 결정할 수 있기 때문에, 여기에서는 준비시간, 가공시간 그리고 제거시간으로 나눈 경우와 준비시간과 가공시간으로만 나눈 경우에 대해서 Sule의 방법과 max 방법을 각각 적용하여 그 수행도를 비교 분석하였다.

Sule의 방법은 공정시간이 3개로 나누어지는, 즉 치구등을 작업물에서 제거하는 제거시간을 가공시간과는 독립으로 간주한 경우에는 수행도가 가장 좋은 것으로 평가되었다. 그러나 3가지의 시간치로 나누어지는 것은 공정시간에서 준비시간과

제거시간이 가공시간에 독립으로 정의되었기 때문에 특정작업의 1번 기계에서 준비와 제거시간동안 2번 기계에서 미리 혹은 동시에 준비 혹은 제거가 가능하기 때문에 문제 자체가 너무 느슨한 제약을 가지고 있어서 여러 개의 최적해들이 존재하며, 그 중 한 개를 찾는 것은 어려운 일이 아닌 것으로 판단된다. 다시 말하여 최적해를 찾을 수 있는 알고리즘이 여러 가지로 만들어질 가능성이 있다는 의미가 된다.

Max 방법은 공정시간이 2가지 시간으로 나뉘는 경우 Sule의 변형방법과 비교하여 동시에 적용하여 둘 중 좋은 한가지 순서를 선택하는 해법으로의 사용이 추천된다. 2가지 시간으로 나뉜 경우 Sule의 변형알고리즘이 항상 좋은 해를 찾아내지 않았기 때문에 max방법과 병행하여 좋은 해를 선별적으로 사용하는 것이 추천된다.

참고 문헌

[1] Johnson, S. M., "Optimal Two and Three-Strage Production Schedules with Setup times included, "Naval Research Logistics Quarterly, vol. 1, no. 1, pp. 61-68 (1954)

[2] Yoshida, T. and K. Hitomi, "Optimal Two-Stage Production Scheduling with setup times Separated", AIIE Transactions, vol. 11, no. 3, pp. 261-263 (1979)

[3] Campbell, H. G., Dudek, R. A., and Smith, N. L., 1970, A heuristic Algorithm for the [eqn: n] job, [eqn: m] machine sequencing problem. Management Science, 16, 630-637

[4] Corwin, B. D., and Esogbue, A. O., 1974, Two-machine flowshop scheduling problems with sequence dependent setup times : A dynamic programming approach. Naval Research Logistics Quarterly, 21, 515-524

[5] Dannenbring, D. G., 1977, An evaluation of flowshop sequencing heuristic. Management Science, 23, 1174-1182

[6] Garey, M. R., and Johnson, D. D., 1979, Computers and Intractability : A Guided tour to the Theory of NP-complete(San Francisco, CA: Freeman)

[7] Gupta, J. N. D., 1975, A search algorithm for generalized flowshop scheduling problem. Computers and Operation Research, 2, 83-90

[8] Gupta, J. N. D., 1986, Flowshop schedules with sequence dependent setup times. Journal of the Operations Research Society of Japan, 29, 206-219

[9] Gupta, J. N. D., and Darrow, W. P., 1986 The two-machine sequence dependent flowshop scheduling problem. European Journal of Operations Research, 24, 439-446

[10] Srikar, B. N., and Ghosh, S., 1986, A MILP model for the [eqn: n]-job, [eqn: M]-stage flowshop with sequence dependent setup times. International Journal of Production Research, 24, 1459-1474

[11] Sule, D. R., 1982, Sequencing [eqn: n] jobs on two machines with setup, processing and removal times separated. Naval Research Logistics Quarterly, 29, 517-519

[12] Sule, D. R., and Huang, K. Y., 1983, Sequency on two and three machines with setup, processing and removal times separated, International Journal of Production Research, 21, 723-732

[13] Szwarc, W., and Gupta, J. N. D., 1987, A flow-shop problem with sequence-dependent additive setup times. Naval Research Logistics Quarterly, 34, 619-627