순열 흐름 공정 일정 계획 문제는 n개의 작업으로 구성된 집합 J=1,2,…,n와 m개의 기계로 구성된 집합 M=1,2,…,m이 주어졌을 때, 모든 작업이 모든 기계를 동일한 순서로 통과하도록 하나의 공통 순열을 결정하는 문제이다. 각 작업 j∈J가 기계 k∈M에서 갖는 처리시간을 p_j,k라 하고, 공통 순열 π=π1,π2,…,πn라 가정한다. 여기서 π_i는 순열 상 i번째로 처리될 작업의 인덱스를 의미한다.

일반적인 flow shop 또는 job shop과 PFSP의 핵심적인 차이점은 모든 기계에서 동일한 작업 순서가 유지된다는 점이다.

예를 들어 세 개의 작업 J=1,2,3과 세 개의 기계 M=1,2,3이 있다고 하자. 일반적인 flow shop 또는 job shop에서는 기계마다 작업 처리 순서가 다를 수 있다. 기계 1에서는 1-2-3, 기계 2에서는 2-3-1, 기계 3에서는 3-1-2와 같은 순서가 허용될 수 있다. 이 경우 각 기계마다 가능한 작업 순서는 3!개이며, 세 개의 기계에 대해 가능한 순서 조합은 (3!)³개가 된다. 일반화하면 각 기계의 작업 순서를 독립적으로 결정하는 경우 탐색 공간은 (n!)^m에 해당한다.

반면 PFSP에서는 하나의 공통 순열만 결정한다. 예를 들어 π=2,1,3으로 결정되면 모든 기계에서 작업 2번, 1번, 3번 순서로 처리된다. 이 순열 제약은 탐색 공간을 (n!)^m에서 n!로 축소한다.

순열 π가 주어졌을 때, 기계 k에서 i번째 작업에 대한 완료 시각 C_πi,k는 다음과 같이 계산된다. 여기서 i=1,…n, k=1,…m이다.

초기조건은 Cπ0,k=0, Cπi,0=0이다. 목적함수는 Makespan Cmax=Cπn,m을 최소화하는 최적 순열 π^*를 구하는 것이다.

그러나 본 연구의 판넬라인 문제는 공통 순열 결정만으로 완결되지 않는다. 병렬 론지 베이가 존재하고, 각 블록은 물리적 조건과 베이 상태를 고려하여 하나의 베이에 배정되어야 한다. 따라서 다음 절에서는 PFSP 구조를 판넬라인의 분기형 공정 구조로 확장한다.

본 연구의 대상인 조선소 판넬라인은 전반부 공통 공정과 후반부 병렬 론지 베이 공정으로 구성된다. 전반부 공정에서는 모든 블록이 하나의 공통 투입 순서 π에 따라 처리된다. 후반부 공정에서는 각 블록이 베이 집합 중 하나의 베이에 할당되어 처리된다. 따라서 본 문제는 공통 순열 결정에 병렬 자원 배정이 결합된 분기형 하이브리드 흐름 공정으로 볼 수 있다.

블록 집합을 J=1,2,…,n, 전반부 공정 집합을 K^s, 후반부 병렬 베이 공정 집합을 K^b, 베이 집합을 B로 둔다. 블록 j의 공정 k의 처리시간은 p_j,k이며, 베이 할당 결과는 bj∈B로 표현한다. 여기서 b_j는 블록 j가 할당된 론지 작업 구역을 의미한다.

전반부 공통 공정에서 순열 π의 i번째 블록 π_i가 공정 k를 완료하는 시각은 다음과 같다.

후반부 베이 공정에서는 블록이 배정된 베이의 가용시각을 함께 고려한다. 블록 j가 할당된 베이 b_j에서 공정 k가 시작 가능한 가용시각을 A_bj,k라 할 때, 후반부 공정 완료 시각은 다음과 같이 계산된다.

블록 j가 공정 k를 완료하면, 해당 베이의 가용시각 A_bj,k는 완료 시각 C_j,k로 갱신된다. 전체 스케줄의 Makespan은 모든 블록의 마지막 공정 완료 시각 중 최댓값으로 정의한다.

본 연구에서는 판넬라인 스케줄링의 제약조건을 Capacity, Sequencing, Adjacency, Bay Assignment의 네 그룹으로 구분한다. Capacity는 일일 작업량, 작업 달력, 생산 가능 용량과 관련된 제약으로, 예를 들어 특정 일자의 허용 작업량이나 작업 가능 시간을 초과하는 블록은 후보에서 제외된다. Sequencing은 착수일 순서, 선후 관계, 연계 블록 관계를 반영하는 제약으로, 후공정 착수 순서를 역전시키거나 필수 선후 관계를 위반하는 블록을 제외한다. 두 제약은 생산 흐름과 실행 가능성을 유지하기 위한 하드 제약으로 적용한다. Adjacency는 특정 유형 블록 또는 고부하 블록의 연속 투입을 제한하는 제약이다. 예를 들어 동일 특성 블록이 연속으로 투입되거나, 작업량이 큰 블록이 충분한 간격 없이 배치되는 경우를 제한한다. 이는 작업 안정성과 부하 분산을 위한 운영 제약이므로, 모든 후보가 차단되는 경우 사전 정의된 우선순위에 따라 단계적으로 완화될 수 있다. Bay Assignment는 선택된 블록을 후반부 베이에 배정할 때 적용되는 제약이다. 블록의 폭, 길이, 론지 작업량 등으로 특정 베이에서 작업할 수 없는 경우 해당 베이는 후보에서 제외된다. 또한 대응 관계가 있는 블록은 현업 규칙에 따라 동일 베이 또는 지정 베이에 배정되어야 할 수 있다. 물리적 작업 가능성 및 필수 배정 규칙은 하드 제약으로 유지하고, 베이 선호, 연속 배정 패턴, 부하 균형은 운영 제약 또는 평가 기준으로 활용한다. 본 연구에서 V(π,b)는 스케줄(π,b)의 제약 미준수 횟수를 의미한다. 단, 이는 하드 제약 위반 수가 아니라, 현업 협의에 따라 불가피한 경우 제한적으로 완화 가능한 운영 제약의 미준수 횟수를 의미한다.

본 연구의 목적은 현업상 반드시 유지해야 하는 제약을 만족하면서, 완화 가능한 운영 제약의 미준수 횟수, 전체 작업 완료 시간, 론지 부하 편차를 순차적으로 줄이는 것이다. 이를 위해 스케줄을 블록 투입 순서 π와 베이 할당 b의 쌍 (π,b)로 표현한다.

론지 베이의 작업 부하 균형을 함께 고려하기 위해 베이 부하 편차 ∆_bay(π,b)를 정의한다. 블록 j의 론지 작업량을 lj라 한다. 베이 q에 할당된 총 론지 작업량 L_q(π,b)는 다음과 같이 계산된다.

론지 부하 편차 ∆_bay(π,b)는 베이별 총 론지 작업량의 최댓값과 최솟값의 차이로 정의한다.

따라서 본 연구의 판넬라인 스케줄링 문제는 다음과 같은 사전식 목적을 갖는 최적화 문제로 정의한다. C_max(π,b)는 식 (4)에서 정의한 Makespan이며, V(π,b)는 제약 미준수 횟수이다.

여기서 min은 일반적인 가중합 최소화가 아니라, 괄호 안의 항을 왼쪽부터 순서대로 비교하는 사전식 최소화를 의미한다. 즉, V(π,b)가 더 작은 스케줄을 우선한다. V(π,b)가 동일한 경우에는 C_max(π,b)이 더 짧은 스케줄을 선택하고, 두 값이 모두 동일한 경우에는 ∆_bay(π,b)가 더 작은 스케줄을 선택한다.

본 연구에서는 판넬라인의 블록 투입, 공정 진행, 베이 할당, 상태 갱신 과정을 이산 사건 시뮬레이션(DES) 환경으로 모델링한다. DES 환경은 제안 방법의 학습과 평가에 공통으로 사용되는 스케줄 생성 환경이며, 각 의사결정 시점에서 현재 생산 상태와 선택 가능한 후보 블록 집합을 제공한다.

DES 환경의 기본 작업 단위는 판넬 블록이다. 에이전트가 하나의 블록을 선택하면, DES 환경은 해당 블록의 공정 시작 시각과 완료 시각을 계산하고, 베이 할당 규칙에 따라 후반부 작업 구역을 결정한다. 이후 설비 가용시각, 작업 구역 가용시각, 일일 용량 사용량, 직전 선택 블록, 잔여 블록 집합, 작업 구역별 누적 작업량이 갱신된다. 갱신된 상태를 기준으로 다음 시점의 후보 블록 집합이 다시 계산되므로, 후보 집합은 고정되어 있지 않고 이전 선택 결과와 현재 생산 상태에 따라 매 step 달라진다.

DES 환경의 구현 타당성은 실적 데이터의 현업 수기 계획을 동일 환경에서 재현하는 방식으로 확인하였다. 구체적으로 현업 수기 계획의 블록 투입 순서와 베이 할당 결과를 DES 환경에 입력하고, 동일한 공정시간 계산 및 상태 갱신 절차로 Makespan과 제약 미준수 결과를 산출하였다. 이후 휴리스틱 방법과 제안 방법도 동일한 DES 환경에서 평가하여, 비교 결과가 평가 환경의 차이가 아니라 블록 선택 방식의 차이에서 발생하도록 하였다.

본 연구는 판넬라인 스케줄링 문제를 마르코프 결정 과정으로 정식화한다. 시점 t에서의 상태 s_t는 마스킹을 통과한 후보 블록 행렬 X_t와 전역 환경 벡터 e_t의 결합으로 정의된다.

후보 행렬 Xt∈RNt×db는 현재 선택 가능한 N_t개의 후보 블록 특성 행렬이다. 후보 블록 특성에는 블록의 물리적 크기, 심 수, 론지 수 등이 포함된다. 환경 벡터 et∈Rde는 현재 날짜와 시각, 당일 용량 사용률 등 전역 상태를 포함한다.

행동 a_t는 유효 후보 집합 A_t 내에서 하나의 블록을 선택하는 것이다. 액션 마스킹을 통과한 후보 집합 위에서 행동이 정의되므로, 행동 공간의 크기와 구성은 매 시점 달라진다.

전이는 DES 환경에서 수행된다. 정책이 블록을 선택하면, 환경은 해당 블록의 전반부 공정 시작 시각과 완료 시각을 계산하고, 베이 가용시각과 작업 부하를 갱신한다. 동시에 선택된 블록은 잔여 블록 집합에서 제거되며, 일일 용량 사용량과 직전 선택 블록 정보도 갱신된다. 종료 조건은 모든 블록이 투입 및 베이 할당을 완료한 경우이다.

본 연구에서는 별도의 step-wise 보상으로 정책을 업데이트하지 않고, rollout이 완료된 뒤 산출되는 평가 벡터를 후보 스케줄의 비교 기준으로 사용한다. 하나의 rollout을 τ라 하면, τ는 모든 블록의 투입 순서와 베이 할당이 완료된 하나의 스케줄을 의미한다. 본 연구에서는 2.4절의 목적함수와 동일하게 다음 평가 벡터를 사용한다.

여기서 F(τ)는 rollout τ의 평가 벡터이다. 즉, 중간 step의 보상을 별도로 설계하지 않고, rollout이 종료된 뒤 F(τ)를 기준으로 후보 rollout을 비교한다. 이 평가 결과는 3.6절의 Self-Labeling 단계에서 최상 rollout을 선택하는 기준으로 사용된다.

액션 마스킹은 현재 상태에서 선택 불가능한 블록을 후보 집합에서 제외하는 절차이다. 액션 마스킹은 무효 행동을 사전에 제거하여 탐색공간을 줄이고 정책 학습을 안정화하는 데 효과적인 방법으로 알려져 있다(Huang and Ontañón, 2022; Zahavy et al., 2018). 본 연구에서는 단순히 이미 선택된 블록만 제외하는 정적 마스킹이 아니라, 현재 DES 상태와 운영 제약을 반영하여 매 step 유효 후보 집합을 다시 구성하는 동적 마스킹을 사용한다.

마스킹은 계층적으로 수행된다. 먼저 아직 선택되지 않은 잔여 블록을 초기 후보로 두고, Capacity와 Sequencing 등 하드 제약을 적용하여 생산 용량, 착수 순서, 선후 관계를 만족하지 못하는 후보를 제거한다. 이후 Adjacency 계열 운영 제약을 적용하여 특정 블록군이나 고부하 블록이 연속으로 배치되는 후보를 추가로 제한한다. 베이 할당과 관련된 물리적 적합성은 후속 베이 할당 단계에서 별도로 확인한다.

모든 운영 제약을 적용한 뒤 후보 집합이 공집합이 되면, 일정 생성을 중단하지 않기 위해 완화 가능한 운영 제약을 사전 정의된 순서에 따라 단계적으로 완화한다. 본 연구의 완화 순서는 라인 그룹 연속 배치 제한, 조립 타입 혼합 제한, Cross seam 혼합 배치 제한, C/Seam 블록 간격 제한, 곡판 블록 간격 제한, 고심수 블록 간격 제한 순서로 적용된다. 이들은 실행 가능성보다는 작업 안정성과 부하 분산을 위한 운영 제약이므로, 후보가 모두 차단되는 경우에 완화할 수 있다. 반면 Capacity, Sequencing, 물리적 베이 적합성은 완화하지 않는다. 완화로 인해 발생한 미준수는 V(π,b)에 반영된다.

최종 마스크 벡터 M_t는 유효 행동에 0, 무효 행동에 -∞를 부여하며, 정책이 무효 행동을 선택하지 않도록 한다. 정책 로짓을 u_t라 하면, 다음과 같은 행동 확률 분포를 생성한다.

이처럼 제안 방법은 전체 잔여 블록 중에서 임의로 다음 블록을 선택하는 것이 아니라, 하드 제약을 먼저 만족시키고, 운영 제약을 단계적으로 적용한 후보 집합 안에서 정책이 다음 투입 블록을 선택하도록 한다.

Fig. 2 
Architecture of the proposed scheduling agent

정책 신경망은 포인터 네트워크 기반의 단일 스텝 후보 선택 모델로 구현하였다. 후보 블록 행렬 X_t와 전역 환경 벡터 e_t의 차원은 다음과 같다.

입력 인코딩 단계에서 각 후보 블록 벡터 xi∈R34는 블록 인코더 Φ_x를 통해 256차원 임베딩 h_i로 변환된다.

전역 환경 벡터 et∈R31는 별도의 환경 인코더 Φ_e를 통과하여 환경 표현 r_t를 생성한 뒤, 선형 투영을 통해 256차원 환경 컨텍스트 c_t로 변환된다.

환경 융합 단계에서는 환경 컨텍스트 c_t를 2층 MLP Ψ에 통과시켜 환경 편향 벡터 δ_t를 생성하고, 이를 모든 후보 블록 임베딩에 잔차 형태로 더한다.

후보 집합의 전역 요약은 융합된 후보 임베딩들의 평균 풀링으로 계산한다.

이후 전역 요약 벡터 g_t와 환경 컨텍스트 c_t를 결합하여 query 벡터 q_t를 생성한다.

다음으로 각 후보 블록에 대한 로짓은 포인터 메커니즘으로 계산된다.

여기서 C는 로짓 스케일링 상수이다. 정책은 현재 후보 집합 위에서 temperature-scaled softmax를 적용하여 확률 분포를 형성하며, 그로부터 다음 블록을 선택한다. 즉, 본 모델은 고정 클래스 분류기가 아니라 시점마다 달라지는 후보 집합 위에서 동작하는 동적 선택 모델이다.

정책이 다음 투입 블록을 선택하면, 베이 할당은 DES 환경 내부의 규칙 기반 절차로 수행된다. 본 연구의 학습 에이전트는 블록 투입 순서 결정에 집중하고, 베이 할당은 블록의 물리적 조건, 연계 관계, 베이 가용 상태, 누적 작업량을 고려한 결정론적 규칙에 따라 수행된다.

결정론적 베이 할당 규칙은 다음 순서로 적용된다. 첫째, 폭이나 부재 수 등 설비 조건을 기준으로 물리적으로 작업 가능한 베이 집합을 구성한다. 둘째, 짝 블록의 기배정 베이가 작업 가능한 후보에 포함된 경우 동일 베이를 우선한다. 셋째, 특정 유형 블록의 동일 베이 연속 배치를 제한한다. 마지막으로 남은 후보 중 누적 작업량이 적은 베이를 선택한다.

본 연구에서는 Corsini et al. (2024)이 제안한 Self-Labeling Improvement Method(SLIM)를 판넬라인 스케줄링 문제에 맞게 적용한다. 매 에피소드마다 현재 정책으로부터 M개의 rollout을 생성하고, 목적함수의 사전식 순서에 따라 최상 rollout τ^*을 선택한다. 이후 τ^*에서 추출된 step-wise 행동 시퀀스 {a^*}을 pseudo-label로 사용하여, 정책을 다음의 cross-entropy 손실로 학습한다.

이 방식은 매 step 보상으로 정책을 직접 업데이트하는 방식이 아니라, 현재 정책이 생성한 후보 스케줄 중 가장 좋은 스케줄의 선택 패턴을 학습하는 방식이다. 또한 보상 설계에 대한 의존도를 낮추고, 희소 보상이나 잡음이 있는 보상 환경에서 발생할 수 있는 학습 불안정을 완화하는 데 유리하다.

실험 데이터는 생성 데이터와 실적 데이터로 구분된다. 생성 데이터는 실제 판넬라인 블록의 속성 분포와 작업 특성을 반영하여 구성하였으며, 하나의 블록을 하나의 스케줄링 단위로 사용한다. 블록 수는 Small, Medium, Large 구간으로 나누고, 문제 분포는 여섯 가지로 설정하였다. General은 기준 조건, Paired Block은 짝 블록 관계 비중이 높은 조건, Subassembly는 연계 구조 블록 비중이 높은 조건, Mixed Relation은 짝 블록과 연계 구조가 함께 존재하는 조건이다. Heavy Workload는 심 수, 처리시간, 블록 크기 등 작업 부하가 증가한 조건이며, High Utilization은 생산 부하율과 용량 압박이 높은 조건이다.

생성 데이터 실험에서는 SPT(Shortest processing time first), MSF(Minimum seam first), LPT(Longest processing time first), Proposed를 비교한다. 실적 데이터 실험에서는 현업 수기 계획을 추가하여 Manual, MSDH(masking-based start-date heuristic), SPT, MSF, LPT, Proposed를 비교한다. 여기서 Manual은 현업 수기 계획을 그대로 재현한 결과이고, MSDH는 수기 계획의 착수일 구간을 유지한 상태에서, 마스킹 기반으로 블록 순서를 재구성한 휴리스틱이다. SPT, MSF, LPT는 각각 총 처리시간이 짧은 블록, 심수가 적은 블록, 총 처리시간이 긴 블록을 우선 선택하는 규칙이다.

생성 데이터 실험은 문제 규모와 분포 변화에 따른 성능을 확인하기 위해 수행하였다. Table 1은 생성 데이터의 각 Scale-Type 조건별 평균 Makespan RPD(%)를 제시하며, 괄호 안에는 평균 Makespan C_max을 나타낸다. Table 2는 동일 조건에서의 제약 미준수 횟수 V(π,b)를 나타낸다.

Table 1과 Table 2에서 Scale은 Small, Medium, Large 인스턴스를 의미하며, 각각 블록 수 20~80개, 90~140개, 150~200개로 구성된다. T1–T6은 문제 분포를 의미하며, T1은 General, T2는 Paired Block, T3은 Subassembly, T4는 Mixed Relation, T5는 Heavy Workload, T6은 High Utilization이다.

Table 1에서 제안 방법은 모든 생성 데이터 조건에서 가장 낮은 Makespan RPD를 달성하였다. Proposed의 RPD가 모든 생성 데이터 조건에서 0.00으로 표시된 것은 제안 방법이 각 인스턴스에서 비교 방법 중 최저 Makespan을 달성하여 식 (21)에 따른 상대 편차가 0으로 계산되었기 때문이다.

Table 2에서도 제안 방법은 블록 수가 증가해도 제약 미준수 횟수를 낮게 유지하였다. 특히 Large 구간에서 SPT와 MSF의 제약 미준수 횟수는 크게 증가하는 반면, 제안 방법은 모든 분포에서 3건 이하를 유지하였다. 이는 제안 방법이 단순 우선순위 규칙보다 문제 규모와 분포 변화에 안정적으로 대응함을 보여준다.

실적 데이터 실험은 실제 판넬라인 생산계획 사례를 대상으로 수행하였다. 평가 대상은 총 72개 블록으로 구성되며, 현업 수기 계획(Manual), MSDH, SPT, MSF, LPT, Proposed를 비교하였다.

Table 3은 실적 데이터의 종합 성능을 나타낸다. Fig. 3, Fig. 4, Fig. 5는 각각 Makespan RPD, 제약 미준수 횟수, 론지 부하 균형 결과를 시각화한 것이다.

Table 3의 Makespan RPD 열과 Fig. 3에서 Proposed는 RPD 0.00으로 가장 짧은 Makespan을 보였다. Manual은 RPD 18.30, MSDH는 RPD 18.17로 나타났다. MSDH는 현업 수기 계획의 착수일 구간을 유지하면서 마스킹 로직과 베이 할당 규칙을 적용한 방법이므로, Manual 대비 Makespan 측면에서는 소폭 개선되었다. 그러나 SPT, MSF, LPT와 같은 단순 휴리스틱은 Makespan을 더 크게 줄였음에도, 제약 미준수와 론지 부하 균형을 동시에 고려하는 데에는 한계가 있었다. Proposed는 학습된 정책을 통해 후보 블록을 선택함으로써 Makespan 측면에서도 가장 우수한 결과를 달성하였다.

Fig. 3 
Makespan RPD comparison on actual data

Table 3의 Violation Count 열과 Fig. 4에서 제약 미준수 횟수를 비교하였다. Manual은 71건의 제약 미준수를 보였으나, MSDH는 36건으로 감소하였다. 이는 마스킹 로직만 적용해도 현업 수기 계획 대비 제약 미준수 횟수를 크게 줄일 수 있음을 의미한다. 그러나 MSDH는 여전히 36건의 미준수가 남아 있으므로, 마스킹 이후 후보 중 어떤 블록을 선택하는지가 중요하다. Proposed는 학습 기반 정책을 적용하여 제약 미준수 0건을 달성하였으며, 이는 단순 마스킹을 넘어 학습된 후보 선택 정책이 추가적인 개선 효과를 제공함을 보여준다.

Fig. 4 
Constraint violation comparison on actual data

Table 3의 Longi Balance 열과 Fig. 5는 론지 부하 균형 결과를 나타낸다. Manual은 ∆ = 145로 가장 큰 부하 불균형을 보였으나, MSDH는 ∆ = 27로 크게 개선되었다. 이는 마스킹 로직과 베이 할당 규칙이 론지 작업량 분산에도 효과가 있음을 보여준다. Proposed는 ∆ = 15로 가장 낮은 부하 편차를 보였으며, LPT는 Makespan과 제약 미준수 측면에서는 비교적 우수했지만 ∆ = 43으로 Proposed보다 부하 균형이 좋지 않았다.

Fig. 5 
Longi workload balance comparison on actual data

Manual과 MSDH의 비교는 마스킹 로직과 베이 할당 규칙만으로도 RPD, 제약 미준수, 론지 부하 편차가 개선됨을 보여준다. Proposed는 여기에 학습 기반 후보 선택 정책을 결합하여 세 지표에서 가장 우수한 결과를 달성하였다.