유연생산시스템(FMS)은 수치제어 기계들이 컴퓨터 네트워크와 자동 물류 시스템에 의해 연결되고, 기계에 장착된 공구들은 자동적으로 상호교환이 가능한 자동화된 제조시스템을 말한다. 본 연구에서는 준비비용 최소화 목적의 FMS 공정계획문제를 다룬다. FMS 공정계획문제는 부하할당문제와 부품경로문제의 두 부분문제들로 구성된 통합문제이다. FMS 공정계획문제를 설계할 때에는 자원의 효율적인 이용을 위하여 다양한 유연성을 고려하는 것이 중요하다. 또한 FMS 공정계획문제는 대칭형 다계층 통합문제의 구조를 갖는다. 본 연구에서는 FMS 공정계획문제를 해결할 수 있는 새로운 탐색 기법을 제안한다. 이 기법은 SCAFP라 부르며, 유연성과 문제의 구조를 효과적으로 다룰 수 있도록 설계하였다. 제안한 알고리즘은 해의 수준과 수렴속도의 측면에서 기존의 기법들과 비교하였다. 실험결과 제안한 SCAFP는 좋은 성능을 보였다