안전 필수 (Safety-critical) 임베디드 제어 프로그램은 각 제어 주기를 제한된 기간 내에 완료해야 합니다. 프로그램의 의존성 구조에 병렬로 실행 가능한 하위 작업들이 포함되어 있을 때, 기존 프로세서에서의 순차적 실행은 병목 현상이 될 수 있습니다. 본 논문은 단계별 배치 (staged batching) 모델 하에서의 직렬-병렬 (series-parallel) 작업 그래프에 대한 최대 병렬 실행 (Maximum Parallel Execution, MPE) 문제를 연구합니다. 이 모델에서 하나의 배치 내의 호환 가능한 작업들은 병렬로 실행되는 반면, 선택된 배치들은 선행 관계를 유지하는 위상 순서 (topological order)에 따라 순차적으로 시작됩니다. 우리는 MPE를 각 배치의 비용이 해당 배치 내에서 가장 느린 작업에 의해 결정되는, 배치 실행 시간의 합을 최소화하는 가중 클리크 분할 (weighted clique-partitioning) 문제로 정식화합니다. 이 문제를 효율적으로 해결하기 위해, 우리는 라그랑주 기반 반복 휴리스틱 (Lagrangian-based Iterative Heuristic, LIH)을 제안합니다. LIH는 단일 열 (singleton columns)과 무작위 탐욕적 클리크 생성 (random greedy clique generation)을 통해 가격 책정 필터링이 적용된 실행 가능한 후보 배치들의 제한된 풀을 구축합니다. 그런 다음, 열 선택을 안내하기 위해 라그랑주 가격 책정 (Lagrangian pricing)을 적용하고, 합법적인 클리크 분할을 복구하기 위해 복구 절차 (repair procedure)를 사용합니다. 가중 혼합 그래프 채색 (weighted mixed-graph-coloring) 분기 한정법 (branch-and-bound) 베이스라인 및 무작위 탐욕적 (randomized greedy) 베이스라인과의 실험 결과, LIH는 유사한 인스턴스의 91.25%에서 정확한 최적해와 일치하였으며, 평균 격차(gap)는 0.073%, 평균 실행 시간은 18.19 ms였습니다. 가장 큰 정확한 참조 노드 설정에서 정확한 베이스라인은 평균 수백 초가 소요되는 반면, LIH는 50 ms 미만을 유지합니다. 나아가 우리는 PLCOpen 스타일의 프로그램을 MPE 그래프로 변환하고, LIH로 최적화하며, FPGA 지향 HDL로 번역한 뒤, 원래의 PLC 스캔 실행과 비교 시뮬레이션하는 엔드-투-엔드 PLC 래더 로직 (ladder-logic) 사례 연구를 제시합니다.