Journal Search Engine

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

Journal of Society of Korea Industrial and Systems Engineering Vol.49 No.3 pp.175-186
DOI : https://doi.org/10.11627/jksie.2026.49.3.175

A Lot Scheduling Considering Dual Resource and Re-entrant in Semiconductor Manufacturing

Ji-Hwan Lee^*

, Gun-Hee Lee^*

, Ji-Na Kim^*

, Yu-Jin Lee^**

, Seung-Jun Lee^*

, Jun-Hee Han^*†

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

^†Corresponding Author : junhan@pusan.ac.kr

Received 25/08/2026 Finally Revised 04/09/2026 Accepted 07/09/2026

Abstract

Double Patterning Technology (DPT) in advanced semiconductor manufacturing involves re-entrant job flows between photolithography and etching stages and requires reusable resources such as masks and reticles. In practice, job-to-machine scheduling is typically performed before resource allocation, but this sequential approach often leads to bottlenecks and inefficiencies under complex constraints. This paper focuses on an integrated scheduling challenge in DPT by simultaneously determining job-machine and resource assignments. An Integrated Mixed-Integer Linear Programming (MILP) model that minimizes makespan is formulated to capture the full problem complexity, including re-entrant flows, dual resource constraints, transportation times and setup times. To efficiently handle large-size problems, a Genetic Algorithm (GA) and an Ant Colony Optimization (ACO) are proposed and compared. Computational results showed that GA and ACO yielded near-optimal quality solution in small-size problems while reducing computing time up to 98% compared to Integrated MILP. Also, GA made better solutions than ACO by balancing workloads between machines in photolithography stage. The proposed framework reflects real fab conditions and offers greater scalability and efficiency, serving as a robust alternative to traditional sequential scheduling in complex semiconductor environments.

Key Words : Semiconductor Manufacturing Scheduling , Dual Resource Constraint , Reentrant Shops , Genetic Algorithm , Ant Colony Optimization

자원 제약과 재진입을 고려한 반도체 Lot 스케줄링

이지환^*, 이건희^*, 김지나^*, 이유진^**, 이승준^*, 한준희^*†

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

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

반도체 산업은 첨단 미세가공 기술과 고가의 정밀 장비가 결합된 대표적인 자본집약적 산업으로, 전자․통신․자동차․의료 등 다양한 산업 분야의 핵심 부품을 생산한다. 웨이퍼 제조에서 패키징에 이르는 반도체 생산 과정은 수백 단계의 공정으로 구성되며, 각 단계에서 높은 정밀도와 엄격한 품질 관리가 요구된다. 특히, 반도체 생산 주기의 대부분을 차지하는 전공정은 웨이퍼 표면에 회로를 형성하는 산화, 포토리소그래피(포토), 식각, 증착, 이온 주입 등의 미세가공 공정이 고가의 설비에서 반복적으로 생산되기에 생산 관리의 관점에서 중요하다 할 수 있다[14].

이 중 포토 공정과 식각 공정은 전공정에서 주요 병목을 발생시키는 공정이다. 포토 공정은 회로 패턴을 웨이퍼에 형성하는 전공정의 핵심 단계로, 장비 한 대당 수백~수천억 원에 달하는 고가 설비를 사용한다. 이어지는 식각 공정은 포토 공정에서 형성된 패턴을 웨이퍼 표면에 실제로 전사하는 단계다. 두 공정 모두 장비 활용도가 높고 반복 수행 빈도가 커서 생산 흐름의 병목으로 작용하기 쉬우며, 처리 속도와 운영 효율이 전체 생산성과 리드타임에 직접적인 영향을 미친다.

웨이퍼 내 회로 패턴은 포토 공정과 식각 공정을 한 번만 거친다고 완성되는 것이 아니다. 회로 패턴을 더욱 미세화 하려는 노력이 지속되고 있으며 해상도 한계를 극복하기 위해 포토 공정과 식각 공정을 여러 번 거치는 Double Patterning Technology(DPT)가 웨이퍼에 적용되었다[17, 22]. 이에 따라 동일 설비를 재방문하는 re-entrant 공정이 빈번하게 발생하게 된다[11]. 또한 포토 공정의 마스크의 경우 공급부족과 높은 가격으로 인한 수량 부족으로 기계에 무한정 배치할 수 없다. 따라서 DPT는 마스크 자원의 제약과 재방문 상황이 동시에 존재하기 때문에 해당 공정의 효율적인 스케줄링이 전체 생산성에 긍정적인 영향을 미칠 수 있다[23, 26]. 하지만 기존 현장의 경우 웨이퍼 lot(작업)을 기계에 먼저 할당한 후 마스크를 기계에 할당하는 순차방식(Sequential)을 적용해왔으며 이는 자원의 상황을 고려한 작업 순서를 결정하지 못하기에 비효율적인 자원 운용과 공정 지연을 유발했다. 때문에 작업의 기계 할당과 자원의 기계 할당을 동시에 결정하는 통합방식(Integrated) 스케줄링이 고려될 필요가 있다.

본 논문은 기계와 포토 마스크 이중 자원 제약(Dual resource constraint)을 고려한 DPT 공정에서 발생하는 2-stage re-entrant flexible flow shop problem을 다룬다[17].

작업은 네 개의 공정 순서( $O 1 \to O 2 \to O 3 \to O 4$ )를 거치며, 이 중 $O 1$ 과 $O 3$ 은 포토 공정인 Stage 1에서 수행되고, $O 2$ 와 $O 4$ 는 식각 공정인 Stage 2에서 처리된다. 이러한 문제는 NP-hard로 분류될 만큼 복잡도가 높으며, 실제 산업 현장에서는 수백 대의 장비와 수천 개의 작업 단위가 얽혀 있어 최적 해 탐색이 어렵다[20, 28]. 따라서 현장에서는 빠른 시간 내에 의사결정을 내리기 위해 메타휴리스틱으로 접근한다[24, 13].

이를 바탕으로 본 논문에서는 최종 완료 시간(makespan)의 최소화를 목적으로 하는 Integrated 수리 모델을 정의하고 이를 빠른 시간 내에 해결하는 메타휴리스틱 알고리즘들을 제시하고 그 성능을 비교해보고자 한다.

이에 앞서 제2장에서는 기존 선행 연구를 분석하여 본 연구와의 차별점을 설명하고, 제3장에서는 본 논문에서 다루는 문제를 정의하고 제4장에서는 이를 수리적으로 정의한다. 제5장에서는 수리 모델을 푸는 메타휴리스틱 모델을 설명하고 제6장에서는 실험을 통해 제안한 알고리즘의 성능을 검증 및 비교하며 제7장에서는 연구의 최종 결론 및 향후 연구 방향을 논의하고자 한다.

2. 관련 문헌 연구

<Table 1>은 본 연구와 선행 연구와의 차별점을 정리한 표이다. Type은 문제 종류, Reentry는 재진입 여부, Dual resource는 이중 자원 제약, Resource sharing은 자원이 다른 기계에서도 사용될 수 있는지를 나타내는 자원 공유 여부, Machine-resource eligibility는 기계와 자원의 호환성인 기계-자원 정합성, Job-resource eligibility는 작업과 자원의 호환성인 작업-자원 정합성을 의미한다.

2.1 재진입 공정 관련 연구

재진입 공정은 동일한 작업이 동일한 공정 단계를 여러 번 반복해서 거치는 특성을 가지며, 반도체 제조에서 대표적으로 포토․식각 공정과 같은 반복 수행 공정이 이에 해당한다. 문제의 복잡도로 인해 기존의 연구들은 우선순위 규칙, 메타휴리스틱과 같은 방식으로 접근해왔다. Geng et al.[9]은 분산형 재진입 하이브리드 플로우샵에서 에너지 효율과 생산성과의 균형을 고려한 다목적 최적화 모델을 개발하고 이를 Artificial Bee Colony(ABC) 알고리즘으로 해결하였다. Von Aspern et al.[2] 은 재진입 플로우샵에서 총 가중 완료 시간 최소화를 위한 우선순위 규칙과 근사 알고리즘을 제안하였으며, Yuan et al.[29]은 강화학습 기반 메타휴리스틱을 적용하여 재진입 플로우샵의 makespan 최소화를 연구하였다. 또한 Vargas-Villamil et al.[27], Dugardin et al.[8], Liu et al.[16] 등 반도체 제조 환경을 대상으로 재진입을 고려한 스케줄링 연구가 꾸준히 되어왔다.

유전 알고리즘(Genetic Algorithm, GA)는 생물의 자연 선택과 진화 과정을 모사한 확률적 탐색 기법으로, 재진입 플로우샵 공정 연구에서 우수한 성능을 보여 왔다[11]. Chen et al.[5]은 GA를 사용하여 재진입 플로우샵 공정에서 makespan 최소화를 목표로 문제를 풀었으며 Lin et al.[15]은 기계 유지보수 산업에서 이중 자원 제약이 있는 재진입 플로우샵 스케줄링 문제에서 makespan 최소화를 목표로 GA를 적용하였다. 또한 Zheng et al.[30]은 순서 종속 셋업 시간과 제한된 버퍼를 갖는 재진입 하이브리드 플로우샵 문제로 확장하여, 총 가중 완료 시간을 최소화하는 방법을 제시하였다.

개미 군집 최적화(Ant Colony Optimization, ACO)는 개미의 경로 탐색 행동을 모방한 기법으로, 경로 기반 최적화 문제에서 우수한 성능을 보여 왔다[7]. Rong-Hwa et al.[21]은 병렬 기계, 순서 종속 셋업 시간 유연 플로우샵 환경에서 이중 페로몬 ACO를 사용하여 조기 완료 비용과 지각 비용의 합을 최소화하는 문제를 풀었다. Dhananjay et al.[6]는 광산 산업에서 이중 자원을 고려한 잡샵 스케줄링을 제약 프로그래밍과 Ant Colony System(ACS)으로 해결하였다. 반도체 제조 영역에서는 ACO가 생산 현장 최적화 및 자원 할당 문제에 활용된 사례가 보고되었으나 재진입 플로우샵을 대상으로 ACO를 직접 적용한 연구는 제한적이었다. 따라서 본 논문은 ACO를 재진입 플로우샵 공정을 대상으로 적용하고 이를 GA와 비교하고자 한다.

2.2 자원 제약과 관련된 연구

자원 제약이 포함된 플로우샵 스케줄링 문제는 기계 배치와 작업 순서 결정뿐만 아니라, 한정된 부자원(예: 작업자, 포토 마스크, 툴 등)의 동시 할당까지 고려해야 하므로 문제 복잡도가 크게 증가한다. Andy et al.[1]는 이중 자원 제약 환경에서 포토공정의 생산 스케줄링 문제를 대상으로 제약 프로그래밍(Constraint Programming, CP)과 혼합 정수․제약 프로그래밍(Mixed Integer Programming, MIP․CP)을 결합한 접근법을 제시하였으며 Gong et al.[10]은 작업자 유연성을 고려한 기계․작업자 유연 플로우샵 스케줄링 모델을 제안하였다. Mlekusch et al.[18]는 스크린 인쇄 산업에서 이중 자원 제약과 재진입을 고려한 유연 플로우샵 문제를 다루었다. 이러한 연구들은 자원 제약 조건하의 플로우샵 문제 해결을 위해 수리 최적화 기법과 휴리스틱 기법을 병행하는 접근을 제시하였다. 또한 Chen et al.[4], Chen et al.[3] 등 반도체 제조환경에서 자원 제약 환경을 고려한 스케줄링 연구가 꾸준히 되어왔다. 그러나 반도체 포토 공정과 같이 재진입 특성과 이중 자원이 동시에 존재하는 복합 구조에 대한 연구는 제한적이었다.

2.3 재진입 공정 및 자원 제약과 관련된 연구

반도체 웨이퍼의 패턴 미세화를 위해 재진입 공정이 도입되었으며 기계뿐만 아니라 다른 부자원까지 고려되어야 하지만 두 요소를 모두 고려한 연구는 부족한 상황이다. Munoz et al.[19]은 포토 공정을 대상으로 재진입, 포토 마스크를 포함한 이중 자원 제약을 고려하였으나, 포토 공정의 기계들이 모두 동일하고 같은 공정 시간을 가지는 Identical Parallel Machine으로 가정하였다는 한계가 존재한다.

2.4 차별성

종합적으로 본 논문은 재진입 플로우샵 공정과 자원 제약과 더불어 반도체 포토 공정에서 고려되어야 하는 자원 이동, 기계-자원 정합성, 작업-자원 정합성까지 고려한다는 점에서 기존 연구들과 차별성을 가진다. 또한 문제 상황에 맞는 GA와 ACO를 제안하고 실험을 통해 성능을 비교함으로써 현장에 알맞은 알고리즘을 제시한다는 점에서 그 의미를 찾을 수 있다.

3. 문제 정의

본 논문의 2-stage re-entrant flexible flow shop problem은 복수의 병렬 장비와 이중 자원 제약, 그리고 재진입 구조가 결합된 Dual resource constrained re-entrant flexible flow shop scheduling (RFFS) 형태에 해당한다. Stage 1은 비동일 병렬 기계(Unrelated parallel machine)로 구성되며, 각 공정을 수행하기 위해서는 기계뿐 만 아니라 자원이 필요하다. 자원은 여러 종류로 구분되며, 종류별로 복수의 자원이 존재한다. Stage 1 장비는 사전에 정의된 호환되는 자원을 가지고 생산할 수 있다. Stage 2는 또한 비동일 병렬 기계로 구성되지만, 자원은 사용하지 않는다. 두 단계 모두 처리 시간은 선택된 기계에 따라 달라지며, Stage 1에서는 여기에 더해 선택된 자원의 종류에 따라 처리 시간이 달라진다. 동일 기계에서 연속 수행되는 두 작업이 서로 다른 종류의 자원을 요구할 경우, 자원 전환에 따른 순서 의존 셋업 시간이 발생한다. 또한 동일한 자원이 서로 다른 기계에서 연속 사용될 경우 이동 시간이 발생한다. 모든 작업은 시작 후 중단 없이 완료될 때까지 처리되며, Stage 간 대기 버퍼는 무한 용량을 가진다고 가정한다. 자원의 이동 및 셋업 시간은 사전에 지정되어 있으며 작업이 사용하는 자원 또한 사전에 지정되어 있다. 작업 간 우선순위는 존재하지 않으며 각 기계는 한 시점에 하나의 작업만 처리할 수 있고, 각 자원은 역시 한 시점에 하나의 작업만 지원할 수 있다. <Table 2>는 MILP의 기호들을 정리한 것이다.

4. 수리 모형

본 논문에서 다루는 문제를 보다 명확히 정의하기 위해, <Table 2>에 정리된 표기법을 활용하여 혼합정수계획법을 제시한다. 본 MILP 모형은 DPT 공정의 재진입 및 이중 자원 제약을 포함한 스케줄링 문제를 설명한다.

수식 (1)은 전체 스케줄의 makespan을 최소화하는 목적함수를 나타내며 수식 (2)는 makespan을 정의한다. 수식 (3)부터 (5)까지는 작업의 기계 할당 및 순서 제약을 정의하며, 수식 (6)부터 (8)까지는 동일 기계 내에서의 시간 제약과 작업 연속성 유지를 표현한다. 수식 (9)부터 (11)까지는 작업의 자원 할당 및 순서 제약을 나타내고, 수식 (12)부터 (15)까지는 동일 작업에 사용되는 기계와 자원의 작업 시간을 동기화한다. 수식 (16)부터 (18)까지는 transportation, setup time을 반영하는 제약을 포함하며, 수식 (19)과 (20)는 가용 기계 및 자원에 대해서만 작업이 할당되도록 한다.

Minimize makespan

(1)

s.t.

M_{m k}^{complete} \leq makespan \forall m \in M, k \in K

(2)

\sum_{m, k} X_{i j m k} = 1 \forall i \in I, j \in J

(3)

\sum_{i, j} X_{i j m k} \leq 1 \forall m \in M, k \in K

(4)

\sum_{i, j} X_{i j m, k - 1} \geq \sum_{i, j} X_{i j m k} \forall m \in M, k \in K, k > 1

(5)

M_{m, 1}^{start} \geq 0 \forall m \in M

(6)

\begin{array}{l} M_{m k}^{complete} \geq M_{m k}^{start} + p_{i j m} + O ∙ (X_{i j m k} - 1) \\ \forall i \in I, j \in J, m \in M, k \in K \end{array}

(7)

M_{m k}^{start} \geq M_{m, k - 1}^{complete} \forall m \in M, k \in K, k > 1

(8)

\sum_{r, h, l} Y_{i j r h l} = 1 \forall i \in I, j \in J_{s}, s = 1

(9)

\sum_{j, i} Y_{i j r h l} \leq 1 \forall r \in R, h \in H_{r}, l \in L

(10)

\sum_{j, i} Y_{i j r h, l - 1} \geq \sum_{j, i} Y_{i j r h l} \forall r \in R, h \in H_{r}, l \in L, l > 1

(11)

\begin{array}{l} M_{m k}^{start} \geq R_{r h l}^{start} + O ∙ (X_{i j m k} + Y_{i j r h l} - 2) \\ \forall i \in I, j \in J_{s}, s = 1, m \in M, r \in R, h \in H_{r}, k \in K, l \in L \end{array}

(12)

\begin{array}{l} M_{m k}^{start} \leq R_{r h l}^{start} - O ∙ (X_{i j m k} + Y_{i j r h l} - 2) \\ \forall i \in I, j \in J_{s}, s = 1, m \in M, r \in R, h \in H_{r}, k \in K, l \in L \end{array}

(13)

\begin{array}{l} M_{m k}^{complete} \geq R_{r h l}^{complete} + O ∙ (X_{i j m k} + Y_{i j r h l} - 2) \\ \forall i \in I, j \in J_{s}, s = 1, m \in M, r \in R, h \in H_{r}, k \in K, l \in L \end{array}

(14)

\begin{array}{l} M_{m k}^{complete} \leq R_{r h l}^{complete} - O ∙ (X_{i j m k} + Y_{i j r h l} - 2) \\ \forall i \in I, j \in J_{s}, s = 1, m \in M, r \in R, h \in H_{r}, k \in K, l \in L \end{array}

(15)

\begin{array}{l} R_{r h l}^{start} \geq R_{r h, l - 1}^{complete} + T_{m^{'} m} + Set - O \\ ∙ (4 - X_{i^{'} j^{'} m^{'} k} - X_{i j m k^{'}} - Y_{i^{'} j^{'} r h, l - 1} - Y_{i j r h l}) \\ \forall i \in I, i^{'} \in I, j \in J_{s}, j^{'} \in J_{s}, s = 1, m \in M, m^{'} \in M, r \in R, \\ h \in H_{r}, k, k^{'} \in K, l \in L, l > 1 \end{array}

(16)

\begin{array}{l} M_{m k}^{start} \geq M_{m, k - 1}^{complete} + {Set}_{r^{'} r} - O \\ ∙ (4 - X_{i^{'} j^{'} m, k - 1} - X_{i j m k} - Y_{i^{'} j^{'} r^{'} h^{'} l} - Y_{i j r h l^{'}}) \\ \forall i \in I, i^{'} \in I, j \in J_{s}, j^{'} \in J_{s}, s = 1, m \in M, r, r^{'} \in R, \\ h \in H_{r}, h^{'} \in H_{r^{'}} k \in K, k > 1, l, l^{'} \in L, r, h \neq r^{'}, h^{'}, \\ j, i \neq j^{'}, i^{'} \end{array}

(17)

\begin{array}{l} M_{m k}^{start} \geq M_{m^{'} k^{'}}^{complete} + O ∙ (X_{i j m k} + X_{i, j - 1, m^{'} k^{'}} - 2) \\ \forall i \in I, j \in J, m \in M, m^{'} \in M, k \in K, k^{'} \in K, \\ (m, k) \neq (m^{'}, k^{'}) \end{array}

(18)

\sum_{k} X_{i j m k} \leq {em}_{i j m} \forall i \in I, j \in J, m \in M

(19)

\sum_{l} Y_{i j r h l} \leq {er}_{i j r} \forall i \in I, j \in J, r \in R, h \in H_{r}

(20)

5. 휴리스틱 방법론

본 논문에서 다루는 문제는 재진입, 비동일 병렬 기계, 이중 자원, 순서 의존적 셋업 시간, 자원 이동 시간이 결합된 Dual resource constrained re-entrant flexible flow shop의 일반화된 형태이다. 본 논문에서 제시한 MILP는 소규모 문제에 대해서는 최적해를 제공할 수 있는 정밀한 기준선으로 유용하지만, 문제 규모가 커질수록 몇 가지 한계가 존재한다. 첫째, 작업․기계․자원 축이 곱 형태로 증가함에 따라 탐색 공간이 폭발적으로 확장된다. 둘째, 순서․자원이동과 같은 작업쌍 기반 제약이 기하급수적으로 팽창하여 제약식 수의 급격한 증가를 유발한다. 셋째, Big-M 선형화를 통한 제약 변환은 LP이완을 약화시켜 계산 효율성을 떨어뜨린다. 이로 인해 MILP는 계산 시간이 급격히 증가하여 대규모 문제에는 사실상 적용이 불가능하다. 이러한 확장성 한계를 보완하기 위해 본 논문은 GA와 문제 특성에 맞게 수정한 ACO를 제시하고 이를 실험을 통해 비교한다.

5.1 GA 설계

GA는 생물의 자연선택과 진화 과정을 모사한 확률적 탐색 기법으로, 해를 염색체 형태의 유전자(Chromosome)로 인코딩하여 개체군(Population) 단위로 탐색을 수행한다. 알고리즘은 매 세대마다 각 개체의 적합도(Fitness)를 평가하고, 이를 바탕으로 부모 유전자를 확률적으로 선택하여 교차(Crossover)와 변이(Mutation) 연산을 통해 자식 개체를 생성한다. 이후, 우수 유전자를 다음 세대로 전달하고 유전적 다양성을 유지하여 지역 최적해에 빠지는 것을 방지한다[11].

본 논문에서는 유전자를 <Figure 1>과 같이 정의하였으며 작업의 할당 순서를 나타내는 벡터 $π$ 와 기계, 자원 할당을 나타내는 벡터 $ω$ 로 구성된다. 예를 들어 <Figure 1>에서는 작업 3, 1, 5 순서로 기계와 자원에 할당되며 작업 3의 경우 첫 번째 포토 공정에서는 1번 기계, 자원 종류(r) 2의 2번 자원(h)과 작업을 진행하며 첫 번째 식각 공정에서는 4번 기계와 작업한다. 이후 두 번째 포토 공정에서는 1번 기계, 1번째 자원의 1번 자원과 작업을 진행하며 두번째 식각 공정에서는 3번 기계와 작업을 진행한다. 이러한 유전자의 적합도는 makespan의 역수로 정의했으며 적합도가 클수록 더 우수한 해를 의미한다.

GA의 초기해는 무작위로 생성되었으며 는 무작위 순열, 는 기계 및 자원의 정합성을 고려하여 무작위로 생성된다.

선택은 전체 유전자의 적합도 값 기반 비례 선택(Roulette wheel selection)을 사용하였다. 유전자의 makespan이 작을수록 적합도가 커지므로 우수한 유전자가 선택될 확률이 커지도록 하여 세대가 거듭될수록 더 좋은 해가 탐색되도록 하였다. 또한, 이전 세대의 가장 우수한 개체를 다음 세대에 무조건 포함시키는 엘리트 보존 기법(Elitism)을 적용하여 탐색 과정 중 최적해가 소실되는 것을 방지하였다.

교차는 하나의 교차점을 기준으로 우측의 유전자를 서로 교환하는 Single point crossover (SPX), 두 교차점 사이의 유전자를 교환하는 Partial matching crossover (PMX) 연산자를 적용하였다. 이때 $π$ 와 $ω$ 모두 교환하며, 교환 후에 중복이 있을 경우, SPX는 교차점 우측의 중복 요소를 서로 교환하며 PMX는 교차점 바깥의 중복 요소를 서로 교환한다.

변이는 $π$ 의 임의의 작업의 $ω$ 를 랜덤으로 재할당하는 Single column mutation과 의 임의의 두 작업과 그에 대응하는 $ω$ 의 위치를 바꾸는 Column swap mutation을 적용하였다.

Algorithm 1: GA

Input :Problem Data, Population Size (Pop size), Maximum Iterations (Max iter), Crossover Probability (Pc), Mutation Probability (Pm)Output:Best chromosome (best solution), Minimum makespan (best fitness)1Initialize population with popsize;2Set best solution to null, best fitness to $\infty$ ;3foriteration = 1 to Max iterdo4forchromosome to popsizedo5Evaluate fitness;6Update best fitness, best solution;7Append best solution to new population;8while $length of new population < Pop size$ do9Select parents from population based on roulette wheel selection;10Apply crossover with pc (SPX or PMX);11Apply mutation with pm (Single Column Mutation12or Column Swap Mutation);13if $New population size < Pop size$ then14Append child to new population;15Replace population with New population;16return best solution, best fitness;

위의 과정을 정리한 Algorithm 1은 GA의 상세 절차를 표현한 것이다.

5.2 ACO 설계

ACO는 개미의 먹이 탐색 행동을 모사한 확률적 탐색 기법으로, 해를 구성하는 일련의 선택을 그래프 위의 경로 구성으로 모델링한다. 개미는 각 선택 지점에서 과거 성과가 누적된 페로몬 강도와 현재 상황에서의 휴리스틱 스코어를 결합해 다음 후보를 확률적으로 고른다. 이후, 우수 해에 기여한 선택에 더 많은 페로몬을 강화하고, 모든 페로몬은 시간에 따라 증발하여 조기수렴을 방지한다. 이 양의 되먹임과 확률적 탐색의 결합이 ACO의 핵심 메커니즘으로 알려져 있다[7].

기존 연구들에서는 단일 페로몬 구조를 기반으로 작업 순서를 학습하는 방식이 주류를 이루어 왔다. 그러나 자원 제약, 재진입 구조 순서 의존적 설정, 자원 이동 시간이 존재하는 복잡한 스케줄링 환경에서는 단일 페로몬 구조만으로는 충분한 탐색 유효성을 확보하기 어렵다. 따라서 본 논문에서는 다중 페로몬 기반 통합형 구조를 채택하여 모든 페로몬이 탐색 공간에서 서로 다른 차원을 학습하게 했다[16]. 본 논문에서 정의한 페로몬 행렬은 총 3가지로 정의된다. 수식 (20)은 작업 $(i, j)$ 의 기계 $m$ 과 자원 종류 $r$ 의 자원 $h$ 으로의 할당 페로몬 행렬, (21)은 각 기계 $m$ 내 작업 간 순서 $(i, j)$ 에서 $(i^{'}, j^{'})$ 를 학습하는 페로몬 행렬, (22)는 각 자원 종류 $r$ 의 자원 $h$ 의 작업 간 순서 $(i, j)$ 에서 $(i^{'}, j^{'})$ 를 학습하는 페로몬 행렬을 의미한다.

Algorithm 2: ACO

Input :Problem data, Maximum iterations (Max iter) Job set J, machine sets $M_{1}, M_{2}$ , parameters, soft reset max, Ant (Num ants)Output:Best solution, Best score1Initialize best score $B \leftarrow \infty$ , best solution $S \leftarrow 0$ ;2fort = 1 to Max iterdo3fora = 1 to Num antsdo4select initial location of resources;5whileoperations remaindo6Identify assignable operations of stage 1, 2;7Generate candidates for stage 1, 2;8Compute jointscores for stage 1, 2;9Select assignments of stage 1, 2;10Assign selected operations of stage 1, 2;11Update assignment matrix, machine/resourcequeues;12Evaluate score;13Store score and solution;14Select best ant;15ifa new best solution is foundthen16Update best score, best solution;17Switch exploration or refinement mode based on convergence;18Update, $α, β$ ;19Apply pheromone update or evaporation;20ifstagnation detectedthen21Apply soft reset;22ifearly stopping condition metthen23return S, B;24return S, B;

휴리스틱 스코어는 총 2가지로 정의된다. Stage 1은 자원을 사용하지만 Stage 2는 사용하지 않아 Stage별 특성이 상이하므로 휴리스틱 스코어를 따로 설정하는 것이 적절하다. Stage 1에서는 자원의 이동에 따라 이동 시간과 셋업 시간이 발생하기 때문에 후보 작업 $(i, j)$ 의 기계 $m$ 과 자원 종류 $r$ 의 자원 $h$ 조합에 대해 작업 시간, 자원 이동 시간, 셋업 시간을 모두 고려한 총 소요 시간 기준으로 수식 (23)과 같이 휴리스틱 스코어를 계산하였다. Stage 2의 경우 자원이 없으므로 작업 시간 기반으로 수식 (24)과 같이 정의한다.

각 후보 작업에 대해 페로몬 값과 휴리스틱 스코어를 조합하여 탐색 기반 선택 확률을 계산한다. 이후 각 의사결정마다 선택 확률이 높은 작업을 중심으로 해를 선정한다. Stage 1과 Stage 2에서 사용하는 선택 확률은 수식 (25), 수식 (26)과 같이 정의한다.

탐색의 다양성을 회복하고 새로운 해 공간으로의 확장을 유도하기 위해 본 논문에서는 Thomas et al. [25]의 Max-min ant system에서 제안한 Pheromone smoothing 개념을 참조하여 일정 반복 수 동안 해의 개선이 없을 경우 페로몬 값을 일정 비율 감쇠 시키는 Soft reset 전략을 도입하였다. Soft reset max는 페로몬 감쇠 비율의 기준값이며, 해당값을 기준으로 페로몬 감쇠 비율이 조정된다. 기존의 페로몬 값은 $γ$ , 초기 페로몬값은 $γ_{0}$ 이며 Soft reset을 적용한 감쇠율 $r$ 과 $γ^{'}$ 은 수식 (27)과 같다.

ACO의 초기해는 무작위로 생성되었으며, 모든 초기 페로몬은 1.0으로 설정된다.

탐색 초반에는 페로몬 가중치 $α$ 를 작게, 휴리스틱 가중치 $β$ 를 크게 설정하였으며 탐색이 진행될수록 $α$ 가 크게, $β$ 가 작아지도록 설계하였다. 이를 통해 초반에는 휴리스틱 기반 해가 구성되며 후반에는 페로몬 기반 학습효과가 강화되도록 설계하였다.

위의 과정을 정리한 Algorithm 2는 ACO의 상세 절차를 표현한 것이다.

τ^{Assign}

(20)

τ^{Morder}

(21)

τ^{Rorder}

(22)

η_{stage1}^{i, j, m, r, h} = \frac{1}{(processing + transportation + setup) time}

(23)

η_{stage1}^{i, j, m} = \frac{1}{processing time}

(24)

p_{stage1}^{i, j, m, r, h} = \frac{{[τ_{i, j, m, r, h}^{Assign}]}^{α} {[τ_{i, j, m}^{Morder}]}^{α} {[τ_{i, j, r, h}^{Rorder}]}^{α} {[η_{stage1}^{i, j, m, r, h}]}^{β}}{\sum {[τ_{i, j, m, r, h}^{Assign}]}^{α} {[τ_{i, j, m}^{Morder}]}^{α} {[τ_{i, j, r, h}^{Rorder}]}^{α} {[η_{stage1}^{i, j, m, r, h}]}^{β}}

(25)

p_{stage2}^{i, j, m, r, h} = \frac{{[τ_{i, j, m}^{Assign}]}^{α} {[τ_{i, j, m}^{Morder}]}^{α} {[η_{stage2}^{i, j, m}]}^{β}}{\sum {[τ_{i, j, m}^{Assign}]}^{α} {[τ_{i, j, m}^{Morder}]}^{α} {[η_{stage2}^{i, j, m}]}^{β}}

(26)

\begin{array}{l} γ = max (γ \cdot r + γ_{0} (1 - r), γ_{0}), \\ where r = \frac{soft reset \max}{current \max + \in} \end{array}

(27)

6. 실험 설계 및 결과

제안한 알고리즘의 성능을 평가하기 위하여 다양한 계산 실험을 수행하였다. 데이터 생성 방식은 <Table 3>에 정리되어 있으며, 이는 실제 현장의 생산 제약 조건을 단순화하여 반영한 것이다. 본 논문의 셋업 시간은 실험의 편의를 위해서 3으로 고정하였다. 자원 종류당 최대 Stage 1의 기계 수만큼 자원이 존재하는 경우(Sufficient)와 하나의 자원만 존재하는 경우(Insufficient)를 기준으로 작업 수, Stage 1의 기계 수를 고려하여 문제를 조합했으며 각 조합당 10개의 instance를 생성하였다.

제안한 GA와 ACO의 성능은 여러 하이퍼파라미터에 의해 크게 영향을 받는다. 따라서 본 연구에서는 사전 실험을 통해 주요 파라미터를 Optuna를 통해 체계적으로 조정하였다. GA에는 개체군 크기 Pop size, 교차 확률 Pc, 변이 확률 Pm이 사용되었으며, ACO에는 강화률 Q, 증발율 $ρ$ , 페로몬 가중치 $α$ , 휴리스틱 가중치 $β$ 가 사용되었다. <Table 4>는 파라미터의 탐색 범위와 최종 파라미터를 요약한 것이다.

모든 계산 실험은 Intel Core i9-12900KF @ 3.2 GHz, 64 GB RAM 사양의 데스크탑에서 수행되었으며, MILP는 Gurobi 12.0.1을 사용하여 구현하였다. 계산 시간은 현업 스케줄링 요구를 고려하여 문제당 최대 3,600초로 제한하였다. 제안한 메타휴리스틱 알고리즘은 Python 3.12.10 기반으로 구현되었으며, 각 시나리오에 대하여 10회 반복하여 평균값을 기록하였다. 비교 대상으로는 현업에서 사용되는 순차방식을 수리 모형으로 나타낸 Sequential MILP, 디스패칭 규칙인 Shortest Processing Time (SPT)를 선정하였다. Sequential MILP는 작업의 기계할당을 먼저 수행하고 이후 작업의 자원할당을 결정하는 수리 모형이며 각 할당 모두 makespan의 최소화를 목적함수로 수립하였다.

알고리즘의 성능 비교를 위해 Gap은 Integrated MILP 결과를 기준으로 하여 수식 (28)과 같이 정의하였다. Model은 Sequential MILP, GA, ACO, SPT의 Makespan값이며, Gap의 값이 음수이면 해당 알고리즘이 Integrated MILP보다 더 우수한 해를 도출하였음을 의미한다.

\frac{Model - Integrated MILP}{Integrated MILP}

(28)

6.1 소규모 문제 실험 결과

<Table 5>와 <Table 6>은 작업 수가 3~5개, Stage 1 기계 수가 2대, 자원이 충분한 경우와 불충분한 경우를 요약한 것이다. Integrated MILP와 Sequential MILP가 제한 시간 내에 최적해를 도출했으며 makespan 측면에서 가장 우수한 해를 보였다. 본 논문에서 제안한 Integrated MILP는 기존 현장의 Sequential MILP 대비 최대 24% 더 우수한 makespan을 보였다. 제안 알고리즘인 GA와 ACO는 Integrated MILP 대비 1% 미만의 Gap을 보이는 동시에 CPU Time은 GA가 약 18~31초, ACO가 약 3~8초로 최대 98% 더 짧은 시간 안에 근사 최적해를 구할 수 있었다. 하지만 Integrated MILP와 Sequential MILP는 더 큰 규모의 문제에 대해서 제한 시간 내에 해를 찾지 못하였다.

6.2 대규모 문제 실험 결과

<Table 7>과 <Table 8>은 작업 수가 40~200개, Stage 1 기계 수가 2~6대, 자원이 충분한 경우와 불충분한 경우를 요약한 것이며 <Figure 2>와 <Figure 3>은 작업이 40, Stage 1 기계수가 6대, 자원이 충분한 경우에 대해서 GA와 ACO로 도출한 간트 차트이다.

본 논문에서 제안한 GA와 ACO 모두 모든 시나리오에서 해를 도출하였으며 단순 휴리스틱인 SPT보다 더 나은 해를 보여주었다. GA의 경우 makespan 측면에서 ACO 대비 최대 22.01%의 Gap을 보였다. 이는 ACO의 해 선택 기준에 기인한다. ACO의 경우 각 Stage의 휴리스틱 스코어 계산 시 작업의 총 소요 시간이 적을수록 더 큰 휴리스틱 스코어를 받기 때문에 총 소요 시간이 적은 스케줄이 선택될 확률이 높아진다. 하지만 자원의 이동 시간과 셋업 시간을 적게 발생시키려는 경향 때문에 같은 자원을 공유하는 작업들끼리 같은 기계에서 연속적으로 처리되는 경우가 발생하였다. 이는 자원의 이동 시간과 셋업 시간을 줄이는데 효과적이지만, 오히려 기계 간 균형있는 작업 분배를 막아 전체 스케줄의 makespan이 증가하는 결과를 초래했다. 이런 현상은 포토 공정의 기계의 수가 많을수록 극명하게 나타났다.

따라서 본 논문에서 제안한 GA가 문제 규모와 상관없이 ACO보다 실시간 스케줄링에 더 적합한 대안이며, DPT 공정에서 요구되는 1시간 내 스케줄링 요건을 충족함과 동시에 병목 완화에 효과적인 알고리즘임을 입증하였다.

7. 결론 및 향후 연구

본 논문은 반도체 DPT 공정에서 복잡한 제약을 고려한 Lot 스케줄링 문제를 다루었다. 이를 해결하기 위해 재진입과 이중 자원을 동시에 고려한 유연 플로우샵을 정의하고 MILP 모델을 제시하였으며 이를 기준으로 GA, 다중 페로몬 ACO, SPT와 동일한 조건에서 비교, 분석하였다. 실험결과 MILP는 현장방식 대비 더 좋은 해를 보였고 제한 시간 내에 수렴하는 경우에는 최적해를 도출했다. 메타휴리스틱은 최적해 대비 작은 Gap의 해를 빠른 시간 내에 도출했으며, GA가 ACO보다 더 좋은 결과를 보였다.

본 논문의 의의는 다음과 같다. 첫째, 공정 반복성이 높은 환경에서 통합적 스케줄링 프레임워크를 제시하여 자원 배분과 작업 순서 최적화를 동시에 달성할 수 있는 가능성을 확인하였다. 둘째, 수리모델이 대규모 문제에서 계산 시간의 한계로 적용이 어려운 반면, GA는 대규모 문제에서도 실질적 계산 시간 내에 적용 가능하다는 점에서 산업 현장에서의 활용성을 높인다. 셋째, 현장 방식 대비 약 24% 개선된 해를 기록하여 기존 스케줄링 운영의 한계를 극복할 수 있는 대안임을 입증하였다.

향후 연구에서는 병렬 기계나 추가 재진입 단계를 포함한 대규모 확장 모델, 버퍼 제약 및 순서 의존적 셋업 시간 고려, 다목적 최적화를 통해 의사결정의 실효성을 높일 필요가 있다. 또한, MILP의 하한을 활용한 정확한 검증 기법과 고도화된 방법론을 개발한다면 보다 안정적인 스케줄링 품질을 확보할 수 있을 것이다.

Acknowledegment

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

Figure

<Figure 1>.

Chromosome Representation

<Figure 2>.

GA J40 P6 E2 Sufficient Gantt Chart (Makespan: 605)

<Figure 3>.

ACO J40 P6 E2 Sufficient Gantt Chart (Makespan: 715)

Table

<Table 1>.

Comparison of this study with previous literature

Reference (Year)	Type	Re entry	Dual resource	Resource sharing	Machine-resource eligibility	Job-resource eligibility	Method
Vargas-Villamil et al.(2003)	FFSP	O	X	O	X	X	MILP, Priority rules
Chen et al.(2006)	FSP	O	X	X	X	X	MILP, GA
Dugardin et al.(2010)	FFSP	O	X	X	X	X	NSGA-II
Liu et al.(2010)	FJSP	O	O	O	O	X	Simulation
Rong-Hwa et al.(2013)	FJSP	X	X	X	X	X	Multi-ACO
Dhananjay et al.(2013)	JSP	X	O	X	X	X	CP, ACS
Lin et al.(2013)	FSP	O	O	X	X	O	Multi-GA
Andy et al.(2018)	FFSP	X	O	O	O	O	MIP, CP
Gong et al.(2020)	FFSP	O	O	X	O	O	MILP, GA
Munoz et al.(2022)	IPMSP	O	O	O	O	O	IP, Heuristic
Geng et al.(2022)	FFSP	O	X	X	X	X	ABC
Chen et al.(2023)	UPMSP	X	O	O	O	O	INMR
Zheng et al.(2024)	FFSP	O	X	X	X	X	GA
Von Aspern et al.(2024)	FSP	O	X	X	X	X	Priority rules
Mlekusch et al.(2025)	FFSP	O	O	O	O	X	CP, MIP
Yuan et al.(2025)	FSP	O	X	X	X	X	RL
Chen et al.(2025)	FJSP	X	O	O	O	O	AQAGA
This study	FFSP	O	O	O	O	O	MILP, GA ACO

<Table 2>.

Notation of Mathematical Model

Index
S	The set of stage
s	The index of stages, (s=1,2)
I	The set of jobs
i	The index of jobs, (i=1,2,…\|N\|)
J	The set of operations
Js	The subset of operations at stages,(J1=1,3,J2=2,4,J1∪J2=J)
j	The index of operations, (j=1,2,3,4)
M	The set of machines
m	The index of machines, (m=1,2,…\|M\|)
R	The set of resource groups
r	The index of resource groups, (r=1,2,…\|R\|)
Hr	The set of resource group instances
h	The index of resource group instances, (h=1,2,…\|Hr\|)
K	The set of positions k in a sequence of machine m
k	The index of positions k in a sequence of machine m,(k=1,2,…\|K\|)
L	The set of positions l in a sequence of resource r
l	The index of positions l in a sequence of resource r,(l=1,2,…\|L\|)
Tmm′	Transportation time of resource from machine m to machine m′
Setrr′	Setup time of resource group r changing to resource group r′
emijm	Eligibility of machine m for job i operation j
erijr	Eligibility of resource group r for job i operation j
pijm	Process time of job i operation j in machine m
O	A Large number
Variables
Xijmk	1 if job i operation j occupies position k in the sequence of machine m,otherwise0
Yijrhl	1 if job i operation j occupies position l of resource r instance h, otherwise 0
Mmkstart	Start time of kth operation in the sequence of machine m
Mmkcomplete	Completion time of lth operation in the sequence of machine m
Rrhlstart	Start time of lth operation in the sequence of resource r instance h
Rrhlcomplete	Completion time of lth operation in the sequence of resource r instance h

<Table 3>.

Experiment data

Index	Data	Range
Job	Number of jobs	[3, 5, 40, 60, 80, 100, 150, 200]
Machine	Stage 1 machine	[2, 4, 6]
Stage 2 machine	2
Resource	Resource group	4
Resource instance(Sufficient)	U [1, number of Stage 1 machine]
Resource instance(Insufficient)	1
Time	Processing time ofStage 1 and 2	U [15, 25]
Transportation time	U [5, 10]
Setup time	3

<Table 4>.

Parameter setting

Parameter	Setting
Pop size	20
Pc	0.7
Pm	0.8
Q	7.9
ρ	0.2
α	0.6
β	2.6
Soft reset max	4.5
GA max iteration	20000
ACO max iteration	1396

<Table 5>.

Small Makespan, Gap

J×P	Resource	Makespan	Gap
3×2	Sufficient	98.6	112.5	98.6	100.2	133.1	0.14	0.00	0.02	0.35
3×2	Insufficient	100.2	113.6	101.0	100.7	128.7	0.13	0.01	0.00	0.28
5×2	Sufficient	145.0	176.8	149.9	147.7	185.6	0.22	0.03	0.02	0.28
5×2	Insufficient	147.6	183.7	148.8	149.4	192.8	0.24	0.01	0.01	0.31

<Table 6>.

Small CPU Time

J×P	Resource	CPU Time(s)
3×2	Sufficient	114.66	15.16	20.89	3.56
3×2	Insufficient	54.41	6.26	18.94	3.57
5×2	Sufficient	1931.47	154.23	31.08	6.32
5×2	Insufficient	2140.65	211.94	28.02	8.65

<Table 7>.

Makespan and CPU time of Large-size Sufficient-resources Instances

J×P	GA	ACO	SPT
40×2	945.5	211.285	971.0	172.286	1100.2	0.003
40×4	628.7	203.915	690.5	152.205	951.2	0.005
40×6	663.0	11.433	734.3	253.140	985.3	0.014
60×2	1371.7	13.992	1403.8	168.802	1565.2	0.007
60×4	984.9	88.929	1110.1	235.836	1394.1	0.010
60×6	961.5	99.581	1155.5	249.967	1459.9	0.029
80×2	1747.4	137.500	1790.1	326.375	2014.1	0.011
80×4	1279.5	157.692	1512.8	511.925	1797.7	0.017
80×6	1279.1	147.719	1604.2	680.873	1871.2	0.048
100×2	2192.2	141.341	2244.5	354.469	2540.2	0.017
100×4	1611.2	230.059	1986.6	543.160	2258.4	0.027
100×6	1628.8	250.092	2058.0	694.302	2376.5	0.074
150×2	3245.1	346.493	3338.7	503.448	3792.0	0.037
150×4	2535.6	360.471	3083.1	1220.655	3390.2	0.058
150×6	2464.8	368.228	3155.6	1281.443	3546.6	0.161
200×2	4311.2	470.576	4445.8	1050.882	4992.5	0.063
200×4	3411.2	461.501	4254.6	1497.849	4434.9	0.098
200×6	3413.7	469.546	4377.0	2173.803	4644.7	0.277

<Table 8>.

Makespan and CPU time of Large-size Inefficient-resources instances

J×P	GA	ACO	SPT
40×2	940.0	209.654	966.8	167.227	1103.2	0.003
40×4	651.1	184.811	700.2	135.438	940.9	0.005
40×6	719.8	9.906	719.8	258.140	968.6	0.014
60×2	1350.3	89.237	1388.9	194.332	1606.0	0.007
60×4	1029.9	96.446	1110.5	481.218	1367.0	0.010
60×6	1047.9	134.473	1178.3	217.762	1443.4	0.029
80×2	1773.0	127.447	1824.5	438.612	2071.2	0.011
80×4	1438.4	140.870	1605.1	498.869	1826.7	0.017
80×6	1387.3	129.056	1610.9	421.711	1900.7	0.048
100×2	2152.1	163.468	2215.7	463.621	2516.9	0.017
100×4	1777.2	167.641	1960.9	562.058	2264.6	0.027
100×6	1810.5	177.238	2066.2	593.608	2358.9	0.076
150×2	3214.0	346.706	3316.9	767.495	3760.2	0.036
150×4	2835.8	349.487	3097.7	994.485	3337.4	0.056
150×6	2822.1	354.624	3174.8	1245.127	3546.6	0.161
200×2	4263.6	479.392	4401.6	1432.717	4973.5	0.062
200*4	3835.7	451.244	4196.3	1562.718	4421.5	0.097
200*6	3862.1	449.970	4341.6	2198.231	4648.1	0.293

Reference

Andy, H., Scheduling of dual resource constrained lithography production: using CP and MIP/CP, IEEE Transactions on Semiconductor Manufacturing, 2018, Vol. 31, No. 1, pp. 52-61.
Aspern, M.V., Buld, F., Klein, N., and Pinedo, M., Flow shops with reentry: The total weighted completion time objective, Journal of Scheduling, 2025, Vol. 28, No. 6, pp. 585-600.
Chen, C.-A., Kuo, H.-A., and Chien, C.-F., Dual-resource constrained flexible job shop scheduling for SMT back-end production and an empirical study of wearable devices, IEEE Transactions on Automation Science and Engineering, 2025, Vol. 22, pp. 9230-9239.
Chen, H., Guo, P., Jimenez, J., Dong, Z.S., and Cheng, W., Unrelated parallel machine photolithography scheduling problem with dual resource constraints, IEEE Transactions on Semiconductor Manufacturing, 2023, Vol. 36, No. 1, pp. 100-112.
Chen, J.-S., Pan, J.C.-H., and Lin, C.-M., A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem, Expert Systems with Applications, 2008, Vol. 34, No. 1, pp. 570-577.
Dhananjay, T., Gaurav, S., Andreas, T., and Bernd, M., Constraint-based ACO for a shared resource constrained scheduling problem, International Journal of Production Economics, 2013, Vol. 141, No. 1, pp. 230-242.
Dorigo, M., Maniezzo, V., and Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996, Vol. 26, No. 1, pp. 29-41.
Dugardin, F., Yalaoui, F., and Amodeo, L., New multi-objective method to solve reentrant hybrid flow shop scheduling problem, European Journal of Operational Research, 2010, Vol. 203, No. 1, pp. 22-31.
Geng, K., Liu, L., and Wu, Z., Energy-efficient distributed heterogeneous re-entrant hybrid flow shop scheduling problem with sequence dependent setup times considering factory eligibility constraints, Scientific Reports, 2022, Vol. 12, pp. 18741.
Gong, G., Chiong, R., Deng, Q., Han, W., Zhang, L., Lin, W., and Li, K., Energy-efficient flexible flow shop scheduling with worker flexibility, Expert Systems with Applications, 2020, Vol. 141, pp. 112902.
Holland, J.H., Adaptation in natural and artificial systems, Ann Arbor, University of Michigan Press, 1975, pp. 32-36.
Kim, J.W., A study on deterministic utilization of facilities for allocation in the semiconductor manufacturing, Journal of Korean Society of Industrial and Systems Engineering, 2016, Vol. 39, No. 1, pp. 153-161.
Kim, Y.J., Seo, Y.J., Han, J.H., and Park, K., Genetic algorithm based flow shop scheduling with inspection constraints, Journal of Korean Society of Industrial and Systems Engineering, 2025, Vol. 48, No. 1, pp. 60-69.
Kyunghyang Shinmun, [Crossroads of K-semiconductor] Core competitiveness of next-generation semiconductors depends on 'packaging technology', https://www.khan.co.kr/article/202212212124015.
Lin, D., Lee, C.K.M., and Ho, W., Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop, Engineering Applications of Artificial Intelligence, 2013, Vol. 26, No. 4, pp. 1282-1290.
Liu, A.J., Yang, Y., Liang, X.D., Zhu, M.H., and Yao, H., Dynamic reentrant scheduling simulation for assembly and test production line in semiconductor industry, AMR, 2010, Vol. 97-101, pp. 2418-2422.
Ministry of Employment and Labor, Korea Chamber of Commerce and Industry, and SK Hynix, SK hynix youth hy-po job training course 2 textbook, Seoul, Korea Chamber of Commerce and Industry, 2023, pp. 82.
Mlekusch, J. and Hartl, R.F., The dual-resource constrained re-entrant flexible flow shop a constraint programming approach and a hybrid genetic algorithm, International Journal of Production Research, 2025, Vol. 63, No. 5, pp. 1803-1824.
Munoz, L., Villalobos, J.R., and Fowler, J.W., Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times, Computers & Operations Research, 2022, Vol. 143, pp. 105787.
Rifai, A.P., Nguyen, H.T., and Dawal, S.Z.M., Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling, Applied Soft Computing, 2016, Vol. 40, pp. 42-57.
Rong, H.H., Chang, L.Y., and Wei, C.C., Flexible job shop scheduling with due window-a two-pheromone ant colony approach, International Journal of Production Economics, 2013, Vol. 141, No. 2, pp. 685-697.
Samsung Electronics Newsroom, Sketching on a wafer (mm) in nm. part 1 - EUV minimum pitch single patterning of Samsung Electronics foundry division, https://news.samsungsemiconductor.com/kr/...
Seoul Economic Daily, Soaring Chinese foundries... imports of Korean parts increased by 20%, https://www.sedaily.com/article/13982716.
Soltani, S.A. and Karimi, B., Cyclic hybrid flow shop scheduling problem with limited buffers and machine eligibility constraints, International Journal of Advanced Manufacturing Technology, 2015, Vol. 76, No. 9, pp. 1739-1755.
Stutzle, T. and Hoos, H., Max-min ant system and local search for the traveling salesman problem, Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), 1997, Indianapolis, IN, USA, pp. 309-314.
The Elec, Samsung electronics promotes first outsourcing of 'photomask' for memory semiconductors, https://www.thelec.kr/news/articleView.html?idxno=35871.
Vargas-Villamil, F.D., Rivera, D.E., and Kempf, K.G., A hierarchical approach to production control of reentrant semiconductor manufacturing lines, IEEE Transactions on Control Systems Technology, 2003, Vol. 11, No. 4, pp. 578-587.
Wang, M.Y., Sethi, S.P., and van de Velde, S.L., Minimizing makespan in a class of reentrant shops, Operations Research, 1997, Vol. 45, No. 5, pp. 702-712.
Yuan, J., Gao, K., Slowik, A., Lu, B., and Jia, Y., Scheduling reentrant flowshops: reinforcement learning-guided meta-heuristics, IET Collaborative Intelligent Manufacturing, 2025, Vol. 7, No. 1, pp. e70029.
Zheng, Q., Zhang, Y., and Tian, H., A cooperative adaptive genetic algorithm for reentrant hybrid flow shop scheduling with sequence-dependent setup time and limited buffers, Complex & Intelligent Systems, 2024, Vol. 10, No. 1, pp. 781-809.

J×P	Resource	Makespan					Gap
J×P	Resource	Integrated MILP	Sequential MILP	GA	ACO	SPT	Sequential MILP	GA	ACO	SPT
3×2	Sufficient	98.6	112.5	98.6	100.2	133.1	0.14	0.00	0.02	0.35
3×2	Insufficient	100.2	113.6	101.0	100.7	128.7	0.13	0.01	0.00	0.28
5×2	Sufficient	145.0	176.8	149.9	147.7	185.6	0.22	0.03	0.02	0.28
5×2	Insufficient	147.6	183.7	148.8	149.4	192.8	0.24	0.01	0.01	0.31