동적 유연 욥 샵 스케줄링에서 유전 프로그래밍으로 진화된 스케줄링 규칙의 일반화 능력에 관한 연구

Investigation of the Generalisation Ability of Genetic Programming-evolved Scheduling Rules in Dynamic Flexible Job Shop Scheduling

동적 유연 욥 샵 스케줄링(DFJSS)은 동적 생산 환경에서 기계 할당과 작업 순서 결정을 동시에 수행해야 하는 복잡한 조합 최적화 문제입니다. 유전 프로그래밍(GP)은 DFJSS를 위한 스케줄링 규칙을 자동으로 진화시키기 위해 널리 적용되어 왔습니다. 그러나 기존 연구들은 주로 구조적 특성보다는 난수 시드(random seed)만 다른 동일한 유형의 DFJSS 인스턴스에서 GP 진화 규칙을 학습하고 테스트했기에, 유형 간(cross-type) 일반화 능력은 거의 탐구되지 않았습니다. 이러한 공백을 메우기 위해, 본 논문은 다양한 DFJSS 조건 하에서 GP로 진화된 스케줄링 규칙의 일반화 능력을 체계적으로 조사합니다. 문제 규모(예: 기계 및 작업 수), 주요 욥 샵 매개변수(예: 가동률), 데이터 분포 등 다양한 차원에서 일련의 실험을 수행하여 이러한 요인들이 본 적 없는(unseen) 인스턴스 유형에 대한 GP 성능에 어떤 영향을 미치는지 분석합니다. 연구 결과, 기계 수가 고정된 상태에서 훈련 인스턴스가 테스트 인스턴스보다 더 많은 작업을 포함할 때, 그리고 훈련 및 테스트 인스턴스가 유사한 규모나 욥 샵 매개변수를 가질 때 우수한 일반화가 나타나는 것으로 확인되었습니다. 추가 분석을 통해 DFJSS 인스턴스 내 의사결정 시점(decision points)의 수와 분포가 이러한 성능 차이를 설명하는 데 결정적인 역할을 한다는 사실이 밝혀졌습니다. 유사한 의사결정 시점 분포는 더 나은 일반화로 이어지는 반면, 상당한 불일치는 성능의 뚜렷한 저하를 초래합니다. 전반적으로 본 연구는 DFJSS에서 GP의 일반화 능력에 대한 새로운 통찰력을 제공하며, 이질적인 DFJSS 인스턴스를 효과적으로 처리할 수 있는 보다 일반화 가능한 GP 규칙을 진화시킬 필요성을 강조합니다.

Dynamic Flexible Job Shop Scheduling (DFJSS) is a complex combinatorial optimisation problem that requires simultaneous machine assignment and operation sequencing decisions in dynamic production environments. Genetic Programming (GP) has been widely applied to automatically evolve scheduling rules for DFJSS. However, existing studies typically train and test GP-evolved rules on DFJSS instances of the same type, which differ only by random seeds rather than by structural characteristics, leaving their cross-type generalisation ability largely unexplored. To address this gap, this paper systematically investigates the generalisation ability of GP-evolved scheduling rules under diverse DFJSS conditions. A series of experiments are conducted across multiple dimensions, including problem scale (i.e., the number of machines and jobs), key job shop parameters (e.g., utilisation level), and data distributions, to analyse how these factors influence GP performance on unseen instance types. The results show that good generalisation occurs when the training instances contain more jobs than the test instances while keeping the number of machines fixed, and when both training and test instances have similar scales or job shop parameters. Further analysis reveals that the number and distribution of decision points in DFJSS instances play a crucial role in explaining these performance differences. Similar decision point distributions lead to better generalisation, whereas significant discrepancies result in a marked degradation of performance. Overall, this study provides new insights into the generalisation ability of GP in DFJSS and highlights the necessity of evolving more generalisable GP rules capable of handling heterogeneous DFJSS instances effectively.