Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.48 No.1 pp.60-69
DOI : https://doi.org/10.11627/jksie.2025.48.1.060

Genetic Algorithm based Flow Shop Scheduling with Inspection Constraints

Ye Jin Kim^*

, Ye Jin Seo^*

, Jun-Hee Han^**†

, Kyungsu Park^*†

^*Department of Business Administration, Pusan National University
^**Department of Industrial Engineering, Pusan National University

^†Corresponding Author : junhan@pusan.ac.kr, ks.park@pusan.ac.kr

Received 26/02/2025 Finally Revised 11/03/2025 Accepted 12/03/2025

Abstract

This paper addresses a scheduling problem aimed at minimizing makespan in a permutation flow shop with two machines and an inspection process that must be conducted at least once every certain number of outcomes from the first machine. A mathematical programming approach and a genetic algorithm, incorporating Johnson's rule and a specific mutation process, were developed to solve this problem. Johnson's rule was used to generate an initial population, while the mutation process ensured compliance with the inspection constraints. The results showed that within a computation time limit of 300 seconds, the mathematical programming approach often failed to provide optimal or feasible solutions, especially for larger job sets. For instance, when the process times of both machines were similar and the inspection time was longer, the mathematical programming approach failed to solve all 10 experiments with just 15 jobs and only had a 50% success rate for 100 jobs. In contrast, the proposed genetic algorithm solved all instances and delivered equal or superior results compared to the mathematical programming approach.

Key Words : Permutation Flow Shop , Inspection Constraints , Genetic Algorithm , Johnson’s Rule

계측 관련 제약 사항을 고려한 유전 알고리즘 기반 플로우샵 스케줄링

김예진^*, 서예진^*, 한준희^**†, 박경수^*†

^*부산대학교 경영학과
^**부산대학교 산업공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

반도체 제조 산업에서는 안정적인 생산 스케줄링으로 정확한 납기일을 맞추는 것이 매우 중요하다. 최근에는 납 기 목표 달성과 자동화된 작업 스케줄링을 통해 생산의 효율성을 높이려 노력하고 있으며, 다양한 상황에서의 스케 줄링 연구가 필요하다. 예를 들어, 특정 반도체 공정 사이에 서는 모든 웨이퍼 로트(lot)마다 계측 및 검사가 일어나야 하지만 어떤 공정 사이에서는 모든 로트가 아니라 특정 개수의 로트마다 한 번만 계측을 하는 것도 가능하다.

본 논문에서는 이렇듯 두 개의 연속된 공정 사이에서 계측이 이루어지되 일부 로트, 즉 특정 개수의 로트마다 최소 한번을 계측하는 상황에서의 스케줄링에 대해 다룬 다. 특히 여러 로트들의 작업완료시각(makespan)을 최소 화하기 위해 작업 순서와 작업별 계측여부를 스케줄링하 였다. 이때, 두 개 공정에서의 작업 순서는 동일하다. 이러 한 스케줄링 문제를 해결하기 위해 본 논문에서는 수리계 획법 기반의 스케줄링 뿐만 아니라 유전 알고리즘 또한 개발하였다. 특히, 유전 알고리즘에서는 공정의 개수가 제 한적인 permutation flow shop에서 최적해를 제시하는 Johnson’s rule을 활용하여 초기 모집단을 도출하였으며, 계측 여부를 나타내는 염색체 부분의 변이를 위한 알고리 즘도 개발하였다. 이러한 유전 알고리즘은 수리계획법 기 반의 스케줄링이 가지는 계산의 복잡성 한계를 해소하여 실제 현장에 적용 가능할 것으로 기대된다.

본 논문의 구성은 다음과 같다. 제2장에서 관련 선행연 구들을 조사한다. 제3장에서는 구체적인 문제 상황을 정 의하고, 수리계획법 기반의 스케줄링을 도출한다. 제4장에 서는 유전 알고리즘을 통한 스케줄링 방법을 도출한다. 마 지막으로 제5장에서 수치 실험을 통하여 수리계획법 기반 의 스케줄링과 유전 알고리즘 기반의 스케줄링 성능을 비 교 및 분석한다. 마지막으로 제6장에서 연구 결론을 제시 한다.

2. 선행연구

Flow shop scheduling 문제는 NP-Hard 문제이므로 이를 해결하기 위해 많은 연구들이 유전 알고리즘 기반의 휴리 스틱 기법을 적용하였다. Allali et al.[1]는 분산 대기 순열 flow shop 스케줄링 문제를 다루며 makespan 최소화를 위 해 세 가지 메타 휴리스틱인 유전 알고리즘, ABC 알고리 즘, 철새 최적화 알고리즘을 도출하였다. An et al.[2]은 대 기 시간에 제한이 있는 장비가 2개인 flow shop 스케줄링 문제를 위해 B&B 알고리즘을 개발하였으며, Lee et al.[8] 은 첫 번째 장비와 나머지 두 개의 장비 사이의 대기 시간 에 제약을 갖는 flow shop 스케줄링 문제에서 유전 알고리 즘 및 지역 탐색 기반 스케줄링 방법을 연구하였다. Iyer et al.[7] 또한 flow shop 스케줄링 문제에서 유전 알고리즘 의 성능 개선을 위해 가장 긴 공통 수열을 제외한 부분끼 리 교차하는 LCS(longest common subsequence) Crossover 을 연구하였다.

이러한 연구들은 permutation flow shop 스케줄링, 즉 모 든 장비 및 공정에서 같은 작업 순서를 가정한 반면, 장비 및 공정 간에 작업 순서가 다른 non-permutation flow shop scheduling 연구들도 존재한다. Benavides and Ritt[4]는 비 순열 작업 순서를 위해 Taillard 방법과 로컬 작업 전달을 통한 작업 삽입을 기반으로 하는 반복적 greedy 알고리즘 을 제안하였으며, Vahedi-Nouri et al.[16]은 장비 가용성 제약이 있는 상황에서 NEH, NEH-ACS 방법 등을 사용해 근사해를 구하고, 이후에 반복 계산을 통해 최적의 솔루션 을 찾는 VFR 휴리스틱을 개발하였다. Bai et al.[3]는 대기 공간 제약과 bi-agent 상황에서의 non-permutation flow shop 스케줄링을 연구하고, 문제 크기에 따라 B&B 알고리 즘, Hybrid Particle Swarm Optimisation(HPSO) 알고리즘 등을 제안하였다. Brum et al.[5]은 순열 스케줄링이 선행 되고 이후 비순열 스케줄링 솔루션을 찾는 구조의 2단계 의 반복 greedy 알고리즘을 제안하였다.

이 외에도 Han et al.[6]은 대기 시간 제약과 skipping jobs가 있는 상황에서 makespan을 최소화하는 유전 알고 리즘을 제안하였다. Ramezanian and Rahmani[12]는 장비 의 연속적인 사용이 불가능한 availability constraints 상황 의 flow shop에서 Tacuchi 방법을 활용하여 유전 알고리즘 의 파라미터를 튜닝하였다. Tseng et al.[15]에서는 missing operation이 있을 때의 휴리스틱 기반의 NPFS 스케줄링을 연구하였으며, Pugazhendhi et al.[10]은 특정 작업이 몇 개 의 장비에서 missing operation을 가질 때의 휴리스틱 방법 을 제안하였으며, Saravanan et al.[9]는 multi hybrid flow shop 상황에서의 Simulated annealing(SA) 알고리즘을 연 구하였다. Rajendran and Ziegler[11]은 우선순위 규칙과 휴리스틱의 makespan을 비교하여 특정 수준의 missing operations가 존재할 때 휴리스틱이 더 좋은 결과를 보이는 것을 확인했다. 또 Ritt and Rossit[13]은 missing operations 가 있는 flow shop 문제 상황에서 iterated greedy algorithm 을 제안하였다.

본 연구에서는 일반적인 skipping job의 문제 상황과는 달리 어떤 작업이 skip되어야 하는지, 즉 작업의 계측 여부 또한 결정한다는 점에서 차별점이 있다.

3. 문제상황 및 수리계획법

본 논문에서는 2개의 연속된 장비가 존재하고, 때로는 연속된 공정 사이에서 계측을 실행해야 하는 상황에서의 작업 스케줄링 문제를 다룬다. 즉, 모든 웨이퍼에 대해서 계측을 수행하지는 않으나 적어도 w개의 작업(웨이퍼)당 한 개는 계측을 받아야 한다. 또한 장비 및 계측기 사이에 는 무한한 대기 공간이 존재하며, 장비 1과 장비 2에서의 작업 순서가 동일한 permutation flow shop 문제이다. 따라 서 <Figure 1>의 간트 차트와 같이 공정 1에서 작업이 완 료된 후, 해당 작업이 계측 공정을 거치는 경우에는 계측 공정을 거쳐 공정 2 작업을 시작할 수 있다. 이러한 문제 상황에서 최소 작업 완료 시간을 최적화하는 작업 순서를 결정하고자 한다.

이러한 permutation flow shop 스케줄링 수리계획법은 아래와 같으며, 사용된 변수들은 <Table 1>에 정리되어 있 다. 이들 중 S_m,k, C_m,j, A_j,k, R_k는 결정변수이다.

Min \sum_{j \in J} C_{2, j} A_{j, J}

(1)

subject to

\begin{matrix} \sum_{k = 1}^{J} A_{j, k} = 1 & for \forall j \end{matrix}

(2)

\begin{matrix} \sum_{j \in J} A_{j, k} = 1 & for \forall k \end{matrix}

(3)

\begin{matrix} \sum_{k = n - w}^{n - 1} R_{k} \geq 1 & for n \geq w + 1 \end{matrix}

(4)

S_{1, 1} \geq 0

(5)

\begin{array}{l} S_{m, k + 1} \geq S_{m, k} + \sum_{j \in J} τ_{m, j} A_{j, k} \\ for k \in {1, \dots, J - 1}, \forall m \end{array}

(6)

C_{1, j} + \sum_{k = 1}^{J} (R_{k} A_{j, k}) τ_{I} \leq \sum_{k = 1}^{J} S_{2, k} A_{j, k} for \forall j

(7)

C_{m, j} \geq \sum_{j \in J} S_{m, k} A_{j, k} + τ_{m, j} for \forall j, \forall m

(8)

A_{j, k}, R_{k} \in 0, 1

(9)

식 (1)은 목적함수로써 마지막 순서인 작업이 장비 2에 서 완료되는 시각을 최소화함을 의미한다. 제약식 (2)는 각 작업과 장비에 대해서 작업 j를 하나의 작업 순서에만 할당해야 함을 의미한다. 제약식 (3)은 모든 작업 순서 k에 또한 하나의 작업에만 할당되어야 함을 나타낸다. 제약식 (4)는 연속되는 w개의 작업 중 적어도 하나에 대해서는 계 측 공정을 수행해야함을 나타낸다. 제약식 (5)는 공정 1에 서의 첫 번째 공정 시작 시간은 0 이상임을 의미한다. 제약 식 (6)은 동일 공정에서 후행 작업의 공정 시작은 선행 작 업이 완료된 이후에 가능함을 나타낸다. 제약식 (7)은 작 업 j는 공정 1을 완료하여야 공정 2를 시작할 수 있음을 의미한다. 마지막으로 제약식 (8)은 각 공정에서의 작업 완료시간을 정의한다. 작업 완료시각은 공정 시작 시각과 작업시간의 합보다 크다.

4. 유전 알고리즘

4.1 염색체 구성 및 적합도

유전 알고리즘은 자연세계의 유전학에 기초하여 진화 형태를 모방한 전역 최적화 기법으로, 스케줄링 등과 같이 계산이 복잡한 문제를 해결하기 위해 널리 사용된다. 유전 알고리즘의 기본적인 과정은 다음과 같다. 생성된 초기 염 색체의 해 집단을 적합도(Fitness Value) 함수를 통해 평가 하고, 일부 우수한 해는 다음 세대에 그대로 남기되 염색 체 중 일부를 선택하여 교차, 변이 등의 과정을 통해 다음 세대인 자식을 생성한다. 이렇게 생성된 다음 세대의 해 집단에 대해 반복해서 적합도 계산을 평가, 선택, 교차, 변 이하여 세대를 거듭해나가면 가장 우수한 해를 찾는다.

본 논문에서는 유전 알고리즘을 위한 염색체를 <Figure 2>와 같이 정의하였으며, 작업순서를 나타내는 순열 m_k 부분과 작업 계측 여부를 나타내는 R_k 부분으로 구성된 다. 즉, <Figure 2>는 작업 3, 1, 4, 2, 5 순서로 공정을 진행 하며, 2번째 작업인 작업 1에 대해서 계측함을 의미한다.

이러한 염색체들의 적합도는 작업 완료시간인 makespan으로 계산되며, 적합도가 작을수록 작업 완료시간이 짧은 우수한 해를 의미한다.

4.2 초기 모집단 생성

작업 계측 여부를 나타내는 R_k 부분은 연속되는 w개의 작업 중 적어도 1번 이상 계측을 해야 하는 제약조건을 만족시키기 위해서 확률적으로 1을 부여하며 초기해를 생 성하였다. 즉, 가장 최근 계측 이후의 작업 개수가 늘어날 수록 점진적으로 1을 부여할 확률을 높였다. 예를 들어, 본 연구에서 가정한 w=10 상황에서는 가장 최근 계측 이 후의 작업 개수에 따라 0.03, 0.05, 0.07, 0.1, 0.15, 0.2, 0.3, 0.5, 0.7, 1 순으로 계측을 실시할 확률을 정의하였다. 즉, 계측 직후 작업은 3%의 확률로 계측하며, 계측 이후 2번 째 작업은 5%, ..., 계측 이후 10번째 작업은 100%의 확률 로 R_k 값이 1이 되도록 초기 염색체를 생성하였다.

작업순서를 나타내는 순열 m_k 부분은 아래와 같이 두 가지 방법을 적용하였다.

4.2.1 무작위 작업순서 생성

작업의 개수에 해당하는 순열을 무작위로 생성하여 이 를 염색체의 m_k 부분으로 활용하였다. 이와 같은 방법은 유전 알고리즘의 가장 기본적인 형태로 다양한 염색체 집 단을 구성할 수 있는 장점이 있으나, 최적해에 도달하는 과정이 길어질 수 있다는 단점이 있다.

4.2.2 Jonhson’s rule 기반 작업순서 생성

Johnson’s rule은 계측 공정이 없이 2개의 장비만 있는 permutation flow shop 문제에서는 makespan을 최소화할 수 있다고 알려져 있으며, 이를 통해 장비 1에서의 작업시 간이 짧은 작업은 앞 순서에, 장비 2에서의 작업시간이 짧 은 작업은 뒷 순서에 할당 염색체들이 생성된다. 자세한 알고리즘은 Stevenson[14] 등에서 확인할 수 있다. 본 논문 에서는 초기 모집단의 50%를 Johnson's rule 기반으로 생 성하고 나머지 50%는 무작위로 생성하여 구성한다.

4.3 선택(Selection)

진화 과정에서 부모 세대의 일부 염색체는 자식 세대 에 그대로 포함될 수도 있으나, 많은 경우 부모 세대의 염 색체 쌍들이 선택, 교차 및 변이되어 자식 세대로 이어진 다. 이러한 염색체 선택을 위해 본 연구에서는 ‘룰렛휠 선 택 기법(Roulette wheel Selection)'을 적용하였다. 룰렛휠 선택은 대표적인 선택 방법으로, 각 염색체의 적합도 값을 비교하여 좋은 염색체일수록 선택될 확률을 높이는 방법 이다. 본 논문에서 활용한 구체적인 룰렛휠 선택 기법과정 은 다음과 같다.

해당 세대의 전체 적합도 값 중 최대, 최소값을 구 한다.
각 염색체의 적합도 값에서 해당 세대의 적합도 최대 값 및 최소값 합을 뺀다.
이렇게 반전된 적합도 값의 크기에 비례하도록 룰렛 을 만든다. 즉, 반전된 적합도 값의 비율에 따라 선택 되도록 한다.

이러한 룰렛휠 선택 기법은 적합도 값이 높은 염색체, 즉 좋지 않은 해가 선택될 가능성을 일부 남김으로써 유전 자 탐색의 다양성을 유지할 수 있다.

4.4 교차(Crossover)

부모 세대에서 선택된 두 염색체는 특정 부분에서 분할, 교차하여 새로운 염색체를 형성하여 자식 세대에 포함된 다. 본 논문에서는 염색체의 m_k 부분과 R_k 부분이 명확 히 구분되고, 순열구조인 작업 순서 m_k 부분에서 한 번 더 교차가 이루어질 경우 작업 순서가 중복되어 나타날 수 있어 일 점 교차(One-point Cross Over)를 적용하였다. 즉, <Figure 3>과 같이 교차를 통해 첫 번째 부모 해의 m_k 부분이, 두 번째 부모 해의 R_k 부분이 자식에게 유전된다.

4.5 변이(Mutation)

유전 알고리즘에서는 ‘변이’를 통해 염색체의 다양성을 증가시켜 지역 최적해 문제를 방지한다. 본 논문에서는 염색체 부분에 따라 다른 변이 알고리즘을 적용한다.

4.5.1 작업순서의 변이

변이 알고리즘은 크게 Flip, Swap, Inversion, Scramble 4가지 방법이 있으며, 염색체의 첫 부분이자 작업순서를 의미하는 m_k 부분에서는 랜덤하게 두 값을 선택하여 값을 교차하는 Swap 방법을 적용한다. <Figure 4>는 본 연구에 서 적용한 Swap 변이의 예시를 보여준다.

4.5.2 계측 여부의 변이

염색체의 두 번째 R_k 부분은 계측을 나타내는 0과 1로 이루어진 이진 염색체이며, 연속되는 w개의 작업당 적어 도 한번은 계측한다는 제약조건을 지키면서 변이 알고리 즘을 구성해야 한다.

본 연구의 적용한 R_k 변이의 핵심은 다음과 같다. 우선 염색체의 R_k 부분에서, 1인 유전자 중 하나를 랜덤하게 선 택하여 0으로 바꾼다. 그 후 변이된 유전자를 기준으로 직 전 및 직후에 존재하는 1인 유전자를 찾아 제약조건을 위 배하는지 확인한다. 이대로 변이를 마치는 경우도 있으나, 상황에 따라서는 추가적으로 기존에 0인 유전자 한 개 또 는 두 개를 1로 변이해야 할 수도 있다.

예를 들어 <Figure 5>는 기존에 0인 유전자 1개를 1로 추가적으로 변이해야 하는 상황을 보여준다. 이 예시에서는 w=5이다. 구간 1은 직전 계측 기준으로 계측이 필요한 부분 을 보여주며, 구간 2는 직후 계측 기준으로 계측이 필요한 부분을 보여준다. 만약 각각의 구간에 1인 유전자가 없다면 연속되는 5개의 작업 중 최소 1번의 계측이라는 제약조건을 어기게 된다. 따라서 최소한의 변이를 위해 겹치는 유전자 들 중 하나를 랜덤하게 선택하여 0인 유전자를 1로 변이시 켜 준다. 이때, 기존에 1에서 0으로 변이시켰던 유전자는 제외하고 선택한다. 따라서 <Figure 5>의 예시에서는 6번째 유전자가 0에서 1로 변이된다. 만약 두 구간이 완전히 겹쳤 다면 추가적인 변이는 필요하지 않았을 것이다.

하지만 <Figure 6>과 같이 두 구간이 변이된 유전자를 제외하고는 겹치지 않는다면 추가적으로 두 개의 변이가 더 필요하다. 이는 w개의 작업당 정확히 1번의 계측이 이 루어졌던 경우에 발생한다. 이때는 기존 1에서 0으로 변경 한 유전자를 복원하는 것을 제외하고는 하나의 유전자 변 이를 통해서는 제약조건을 만족시킬 수 없으므로 두 개의 추가적인 변이를 실행한다. 먼저 구간 1에서 하나의 유전 자를 랜덤하게 선택하여 변이를 실행한다. 이때 구간 1에 서 일어난 변이의 위치에 따라 <Figure 7>과 같이 w-1개의 경우가 존재하며, 각 경우에 따라서 구간 2에서 일어날 수 있는 추가 변이 후보들이 결정된다. <Figure 7>의 회색 영 역은 구간 2에서 일어날 수 있는 변이의 위치를 표현한다. 예를 들어, 두 번째 유전자가 0→1로 변이한 경우에는 7번 째 유전자가 0→1로 변이해야 한다. 만약 3번째 유전자가 0→1로 변이한 경우에는 7번째 또는 8번째 유전자 중 랜덤 하게 선택하여 0→1로 변이하게 된다.

5. 실험 결과

5.1 주요 파리미터 설정

본 연구에서 수행한 실험에 대한 파라미터는 <Table 2> 에 요약되어 있다. 스케줄링을 하는 작업의 개수는 15개, 30개, ..., 150개이며, 각 작업개수에 대해 작업 소요시간과 계측 소요시간에 따라 총 9개의 case로 나누어 실험하였 다. 각 작업의 작업 소요시간은 장비 1에서는 [40, 60] 범 위에서 랜덤하게 생성되었으며, 장비 2에서는 case에 따라 장비 1의 범위의 0.5, 1.0, 1.5배 범위에서 랜덤하게 선택되 었다. 계측 소요 시간은 장비 1의 소요시간의 평균값에 0.5, 1.0, 1.5배를 곱한 고정값을 사용하였다. 계측간에 최 대 허용 작업수는 10개(w=10) 이며, 각 Case별 반복실험 횟수는 10회, 총 540번의 실험을 진행하였다. 모든 실험은 Intel Core I9-12900 CPU(3.20 GHz) 및 64.00 GB RAM 상 황에서 수행되었다.

수리계획법을 활용한 스케줄링 결과를 도출하기 위해 서는 파이썬 및 Gurobi Optimizer(version 11.0)를 활용하였 으며, 실용적 측면을 고려하여 계산시간을 300초로 제한 하였다.

유전알고리즘에서는 한 세대당 염색체의 수를 300개로 설정하였다. 부모 세대에서 상위 20% 염색체는 교차 및 변이 없이 그대로 자식 세대로 유전되었으며, 나머지 80% 는 제안된 룰렛휠 기반 선택, 교차, 변이 과정을 거쳐 자식 세대로 유전되었다. 또한 변이가 일어날 확률은 0.2로 설 정하였다. 이러한 파라미터들은 시행착오법을 통해 도출 되었으며, 수리계획법의 제한시간인 300초 동안 진화를 반복하여 가장 좋은 해를 도출한다.

5.2 실험 결과

<Table 3>과 <Figure 8>은 수리계획법 기반의 스케줄링 과 Johnson’s rule 기반의 초기해 생성 및 유전알고리즘 스 케줄링 실험 결과를 요약하여 보여준다. 수리계획법을 활 용한 스케줄링에서는 작업의 개수가 15개로 작을 경우에 는 모든 문제를 풀었으며 76.67%의 확률로 최적해를 제시 하였다. 하지만 작업개수가 증가함에 따라 최적해를 제시 하는 경우가 급격하게 감소하였으며, 특히 100개 이상의 작업 상황에서는 모든 문제에서 최적해를 제시하지 못하 였다. 뿐만 아니라 100개 이상의 작업 상황에서는 아예 문 제를 풀지 못하는 경우의 수가 급격하게 증가하였다. 이에 반해 유전 알고리즘은 그 특성상 모든 경우에 대해 해를 제공할 수 있었으며, 특히 Johnson’s rule 기반의 초기해 생성에서는 모든 문제에서 수리계획법 기반의 해와 동등 하거나 더 나은 해를 보여주었다. 무작위 기반의 초기해 생성에서도 90개의 문제 중 단 1개의 문제에서만 수리계 획법 기반의 해보다 높은 makespan을 보여주었으나, 이마 저도 최적해인 1544초와 대비해서 단 1초의 차이를 보였 다. 또한 유전알고리즘을 통한 makespan의 전체 평균 개선 율은 미비해 보이나, 이 수치는 수리계획법이 해를 제시한 문제들로만 도출된 값이며 수리계획법이 아예 해를 제시 하지 못하는 경우가 많으므로 실제 유전 알고리즘의 효과 성은 이러한 수치보다 더욱 크다.

또한 이러한 유전 알고리즘의 효과는 Case별로도 다소 큰 차이를 보였으며, Case별 성능의 특성은 <Figure 9>에 요약되어 있다. 가장 큰 차이를 보이는 개선율을 살펴보 면, 장비 1과 장비 2의 작업 소요시간이 명확하게 다른 Case 1~3, 7~9에서는 상대적으로 개선율이 매우 적었으나, 장비 1과 장비 2의 작업 소요시간이 유사한 Case 4~6에서 는 상대적으로 큰 개선율을 보였다. 또한 Case 4~6에서는 다른 Case와 대비 수리계획법 기반의 스케줄링이 최적해 를 제시하는 비율이 낮고 아무 해도 제시하지 못하는 비율 이 높은 것을 알 수 있다. 특히 작업 개수가 15개인 상황에 서도 다른 Case에서는 모든 문제에서 최적해를 구할 수 있었으나, Case 4~6에서는 30번의 실험 중 21번의 실험에 서 최적해를 도출하지 못하였으며 특히 Case 4~5는 모든 경우에 최적해를 도출하지 못하였다. 이렇듯 Case 4~6에 서 특히 유전 알고리즘의 효과가 더 컸다.

<Figure 10>은 수리계획법 기반의 스케줄링 대비 유전 알고리즘의 개선율을 Case별로 보여주고 있다. 특히 Case 4에서의 개선율이 도드라졌으며, 작업 개수가 15개인 상황 에서는 수리계획법 기반의 makespan은 평균 837.8초였으나 유전 알고리즘에서는 26초를 단축하여 평균적으로 3.098% 개선하였다. 또한, 수리계획법이 해를 제시하지 못한 비율 이 높았던 작업개수 150개 상황에서는 수리계획법 기반의 makespan의 평균은 7663초였으나 유전알고리즘에서는 96 초를 단축하였으며 1.537%의 개선율을 보였다. 전반적으로 는 작업의 개수가 적을 때에는 Case 4와 Case 5의 성능 개선이 도드라졌으며, 작업의 개수가 많은 상황에서는 Case 4뿐만 아니라 Case 1의 개선율도 상대적으로 높았다.

<Table 4>를 통해서는 Jonhson’s rule 기반 초기 모집단 의 효과를 분석할 수 있다. Johnson’s rule 기반의 초기 모 집단은 Case 4~6에서만 개선 효과가 있었으며, 작업의 개 수가 많을수록 효과가 있을 확률이 높은 경향을 보였다. 개선이 있는 경우에도 무작위 초기 모집단 간의 성능 차이 는 크지 않았다. 하지만 실험한 모든 문제에서 Johnson’s rule 기반의 초기 모집단이 동등하거나 더 좋은 성능을 보 였다.

6. 결 론

논문에서는 실제 반도체 제조 공정에서 발생하는 계측 상황을 고려하여, 두 개의 장비 사이에서 모든 작업이 아 니라 일부 작업(특정 개수의 작업마다 최소 한번)이 계측 을 받고 모든 장비에서의 작업 순서는 동일한 permutation flow shop의 스케줄링에 대해서 다루었다. 특히, 이러한 상 황에서 makespan을 최소화하기 위한 수리계획법과 Johnson's rule 기반의 초기 유전자 생성, 계측 여부의 변이 과정 등을 반영하는 유전 알고리즘을 개발하였다.

실제 스케줄링 환경에서는 스케줄링 도출을 위한 소요 시간에 제한이 있으므로 본 연구에서는 300초의 계산 시 간 제한을 가정하였으며, 이때 모든 경우에서 유전 알고리 즘이 수리계획법보다 좋은 스케줄링을 도출하였다. 특히 수리계획법을 활용한 스케줄링에서는 작업 개수가 15개로 작을 때에도 모든 경우에 대해 최적해를 제시하지 못하였 으며, 작업개수가 증가함에 근사해마저도 제시하지 못하 는 경우가 증가하였다. 유전알고리즘을 통한 스케줄링 개 선 효과는 두 장비의 공정 시간이 유사한 경우(Case 4~6) 에 컸다. 특히 계측 소요시간마저 큰 경우(Case 4)에는 작 업개수가 15개인 경우에도 10번의 실험 모두 최적해를 제 시하지 못하였고 유전알고리즘을 통한 개선율은 1.95%~ 4.00%였다. 또한 작업개수가 100개 이상인 경우에는 50% 이상의 확률로 아무 해도 제시하지 못하였다.

본 논문의 한계점 및 발전방향은 다음과 같다. 본 논문 에서는 두 장비에서의 작업 순서가 같다고 가정하였으나 상황에 따라서는 이러한 제약이 없을 수 있으며, 두 개의 장비가 아니라 더 많은 장비를 고려해야 할 수도 있다. 또 한 다양한 초기해 생성 방식 및 변이 방식 적용, 유전 알고 리즘 외의 여러 알고리즘의 적용 및 성능 비교 등도 추후 연구가 될 수 있다.

Acknowledgement

This work was supported by a 2-Year Research Grant of Pusan National University.

Figure

<Figure 1>.

Permutation Flow Shop Problem with Two Machines and Inspections

<Figure 2>.

Example of a Chromosome

<Figure 3>.

One-point Cross Over

<Figure 4>.

Example of a Swap Mutation in the Job Order Parts of a Chromosome

<Figure 5>.

Example of a Mutation in the Inspection Parts of a Chromosome (One Mutation Required)

<Figure 6>.

Example of a Mutation in the Inspection Parts of a Chromosome (Two Mutations Required)

<Figure 7>.

Scenarios for Two Mutations in the Inspection Parts of a Chromosome

<Figure 8>.

Overall Performance Analysis

<Figure 9>.

Performance Analysis by Several Cases

<Figure 10>.

Improvement Rate of Genetic Algorithm by Cases

Table

<Table 1>.

Variables and Parameters

Variables	Description
k	Order of job (k=1,2,…, J)
m	Machine number (mεM={1,2})
j	Job number (j=1,2,…, J)
Sm,k	Starting time of k-th job to machine m (mεM, kεJ)
Cm,j	Completion time of job j on machine m (mεM, jεJ)
Aj,k	1 if job j is assigned to job order k, otherwise 0 (k,jεJ)
Rk	1 if inspect for the k-th ordered job, otherwise 0 (kεJ)
Parameters	Description
w-1	Maximum number of jobs(wafers) between inspections
τm,j	Processing time of job j on machine m (mεM, jεJ)
τI	Processing time of Inspection

<Table 2>.

Parameters for Experiments

Case	# of jobs	Process time(range)	Inspection time (τi=βμτ1,j)	Maximum # of jobs between Inspections (w)	Replications	Limitation for computation time
1	15, 30, 50, 75, 100, 150	[40, 60]	[60, 90] (α=1.5)	75(β=1.5)	10	10	300 sec
2	50(β=1.0)
3	25(β=0.5)
4	[40, 60] (α=1.0)	75(β=1.5)
5	50(β=1.0)
6	25(β=0.5)
7	[20, 30] (α=0.5)	75(β=1.5)
8	50(β=1.0)
9	25(β=0.5)

<Table 3>.

Performances Comparison between Mathematical Programming(MIP) and Genetic Algorithm

<Table 4>.

Probability that Jonhson’s Rule Improves Performance Compared to a Random Initial Population

※ The values in parentheses represent the average improvement rate.

# of Jobs	Case 1	Case 2	Case 3	Case 4	Case 5	Case 6	Case 7	Case 8	Case 9
15	0%	0%	0%	0%	0%	0%	0%	0%	0%
30	0%	0%	0%	0%	10% (0.063%)	10% (0.065%)	0%	0%	0%
50	0%	0%	0%	0%	10% (0.039%)	0%	0%	0%	0%
75	0%	0%	0%	10% (0.079%)	10% (0.026%)	0%	0%	0%	0%
100	0%	0%	0%	50% (0.055%)	30% (0.040%)	0%	0%	0%	0%
150	0%	0%	0%	70% (0.093%)	60% (0.026%)	30% (0.013%)	0%	0%	0%

Reference

Allali, K., Aqil, S., and Belabid, J., Distributed No-Wait Flow Shop Problem with Sequence Dependent Setup Time: Optimization of Makespan and Maximum Tardiness, Simulation Modelling Practice and Theory, 2021, Vol. 116, 102455.
An, Y.J., Kim, Y.D., and Choi, S.W., Minimizing Makespan in a Two-Machine Flowshop with a Limited Waiting Time Constraint and Sequence-Dependent Setup Times, Computers & Operations Research, 2016, Vol. 71, pp. 127-136.
Bai, D., Liu, T., Zhang, Y., Ren, T., Zhang, Z.H., and Dong, Z., Scheduling Non-Permutation Flowshop with Finite Buffers and Two Competitive Agents, Computers & Industrial Engineering, 2023, Vol. 66, 108939.
Benavides, A.J. and Ritt, M., Two Simple and Effective Heuristics for Minimizing the Makespan in Non- Permutation Flow Shops, Computers & Operations Research, 2015, Vol. 66, pp. 160-169.
Brum, A., Ruiz, R., and Ritt, M., Automatic Generation of Iterated Greedy Algorithms for the Non-Permutation Flow Shop Scheduling Problem with Total Completion Time Minimization, Computers & Industrial Engineering, 2021, Vol. 163, 107843.
Han, J.H. and Lee, J.Y., Genetic Algorithm-Based Approach for Makespan Minimization in a Flow Shop with Queue Time Limits and Skipping Jobs, Advances in Production Engineering & Management, 2023, Vol. 18, No.2, pp. 152-162.
Iyer, S. and Saxena, B., Improved Genetic Algorithm for the Permutation Flowshop Scheduling Problem, Computers & Operations Research, 2004, Vol. 31, pp. 593-606.
Lee, J.H., Yu, T.S., and Park, K., Scheduling of Flow Shop with Overlapping Waiting Time Constraints using Genetic Algorithm, Journal of the Korean Institute of Industrial Engineers, 2021, Vol. 47, No.1, pp. 34-44.
Saravanan, M., Sridhar, S., and Harikannan, N., Optimization of Realistic Multi-Stage Hybrid Flow Shop Scheduling Problems with Missing Operations Using Meta-Heuristics, International Journal of Engineering and Technology, 2014, Vol. 6, No.1, pp. 484-496.
Pugazhendhi, S., Thiagarajan, S., Rajendran, C., and Anantharaman, N., Performance Enhancement by Using Non-Permutation Schedules in Flowline-Based Manufacturing Systems, Computers & Industrial Engineering, 2003, Vol. 44, No.1, pp. 133-157.
Rajendran, C. and Ziegler, H., A Performance Analysis of Dispatching Rules and a Heuristic in Static Flowshops with Missing Operations of Jobs, European Journal of Operational Research, 2001, Vol. 131, No.3, pp. 622-634.
Ramezanian, R. and Rahmani, D., MILP Formulation and Genetic Algorithm for Flow Shop Scheduling Problem with Missing Operations, International Journal of Operational Research, 2017, Vol. 30, No.3, pp. 321-339.
Ritt, M. and Rossit, D., Effective Heuristics for Permutation and Non-Permutation Flow Shop Scheduling with Missing Operations, Computers & Operations Research, 2024, Vol. 170, 106742.
Stevenson, W., Operations Management (14th Edition), McGraw-Hill Education, 2020.
Tseng, C.T., Liao, C.J., and Liao, T.X., A Note on Two-Stage Hybrid Flowshop Scheduling with Missing Operations, Computers & Industrial Engineering, 2008, Vol. 54, No.3, pp. 685-704.
Vahedi-Nouri, B., Fattahi, P., and Ramezanian, R., Minimizing Total Flow Time for the Non-Permutation Flow Shop Scheduling Problem with Learning Effects and Availability Constraints, Journal of Manufacturing Systems, 2013, Vol. 32, No.1, pp. 167–173.

Case	# of jobs	Process time(range)		Inspection time (τi=βμτ1,j)	Maximum # of jobs between Inspections (w)	Replications	Limitation for computation time
Case	# of jobs	Machine 1 (τ1,j)	Machine 2 (τ2,j = ατ1,j)	Inspection time (τi=βμτ1,j)	Maximum # of jobs between Inspections (w)	Replications	Limitation for computation time
1	15, 30, 50, 75, 100, 150	[40, 60]	[60, 90] (α=1.5)	75(β=1.5)	10	10	300 sec
2				50(β=1.0)
3				25(β=0.5)
4			[40, 60] (α=1.0)	75(β=1.5)
5				50(β=1.0)
6				25(β=0.5)
7			[20, 30] (α=0.5)	75(β=1.5)
8				50(β=1.0)
9				25(β=0.5)