Bottleneck Identification in Resource-Constrained Project Scheduling via Constraint Relaxation
원문 초록
In realistic production scenarios, Advanced Planning and Scheduling (APS) tools often require manual intervention by production planners, as the system works with incomplete information, resulting in suboptimal schedules. Often, the preferable solution is not found just because of the too-restrictive constraints specifying the optimization problem, representing bottlenecks in the schedule. To provide computer-assisted support for decision-making, we aim to automatically identify bottlenecks in the given schedule while linking them to the particular constraints to be relaxed. In this work, we address the problem of reducing the tardiness of a particular project in an obtained schedule in the resource-constrained project scheduling problem by relaxing constraints related to identified bottlenecks. We develop two methods for this purpose. The first method adapts existing approaches from the job shop literature and utilizes them for so-called untargeted relaxations. The second method identifies potential improvements in relaxed versions of the problem and proposes targeted relaxations. Surprisingly, the untargeted relaxations result in improvements comparable to the targeted relaxations.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
학생 학습 자원 배분을 위한 유전 알고리즘
A genetic algorithm for student academic resource allocation
개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.
LazyAgent: 수요 기반 구체화 및 에이전트 프로그램의 물리적 최적화
LazyAgent: Demand-Driven Materialization and Physical Optimization of Agentic Programs
행동에 앞서 계획을 세우는 에이전트 런타임은 각 단계가 준비되는 즉시 실행한다. 이러한 런타임도 그 벤치마크도 준비된 단계와 요청이 필요로 하는 단계를 구별하지 않으며, 그 차이는 크다. 154개의 프로덕션 워크플로에 대한 303개 요청에서, 목표가 달성되면 멈추는 즉시 실행(eager) 런타임은 CPU의 62.2%를 요청이 전혀 필요로 하지 않은 작업에 소비한다. LazyAgent는 우리가 아는 한 에이전트 런타임을 위한 수요 기반 실행의 최초의 완전한 정식화이다. 그 규칙은 준비된 단계를 현재 요청이 필요로 할 때만 실행하고, 계획이 바뀌어도 그 답을 정확하게 유지하는 것이다. 프로그램에서 도출된 수요 집합이 모델 호출 없이 한 번의 순회로 이를 결정하므로, LazyAgent는 요청 밖에서는 아무것도 소비하지 않는다. 수요가 정확하게 정의되기 때문에 그 동작이 증명되며, 빌더는 어떤 실행 이전에도 수요가 어디에서 절감해야 하고 어디에서 동률이어야 하는지 알 수 있다. 계획이 실행되기 전에 비용이 알려지므로, LazyAgent는 쿼리 옵티마이저로서 후보 워크플로 중에서 선택할 수 있다. 해당 즉시 실행 런타임과 비교한 실측에서, LazyAgent는 최첨단 LLM이 패치를 작성하는 릴리스 게이트에서 컨테이너 시간을 51.7%와 52.1% 절감하고, 동일한 품질의 DataSciBench 계획에서 토큰을 12.8%, 실제 LangGraph 애플리케이션에서 비용을 24.0% 절감하며, 손실은 없다. LLM이 실제 코드 실패 후 재계획할 때는 해결 가능한 모든 목표를 목표당 토큰 11.7% 적게 사용하여 해결한다. 프로덕션 워크플로에서는 CPU를 42.0% 절감하고, 요청이 전체 그래프를 필요로 하는 경우에는 정확히 동률이며, 오버헤드는 최대 0.43%이다. 동일한 집합이 모든 물리적 연산을 조정하는데, 프로젝션은 공유 CI 단계의 80-89%를 절감하는 반면 동일한 즉시 실행 대조군은 0.0%를 절감한다. 공개 에이전트 벤치마크는 즉시 실행 런타임과 같은 방식으로 설계되어 있어 이 차이를 보여줄 수 없다. 우리는 이들의 과제로 테스트 프로그램을 구성하였으며, 업계에 에이전트 워크플로가 얼마나 효율적으로 실행되는지를 측정하는 벤치마크를 구축할 것을 촉구한다.
ARGOS: 컴퓨팅 연속체에서의 서비스 오케스트레이션을 위한 강화학습 기반 다차원 탄력성
ARGOS: Reinforcement Learning-Driven Multidimensional Elasticity for Service Orchestration in the Computing Continuum
컴퓨팅 연속체(Computing Continuum)의 데이터 집약적 서비스는 용량이 제한적이고 불균등한 이기종 노드 전반에서 분석 품질, 자원 사용량, 비용 간의 균형을 유지해야 합니다. 자원 스케일링이 용량 한계에 도달하면 수요 변화와 클러스터 압박을 클라이언트가 정의한 품질 범위를 위반하지 않으면서 흡수해야 하므로 이러한 균형을 맞추기가 특히 어려워집니다. 기존 오케스트레이터는 주로 자원, 배치 또는 복제본을 조정하는 반면, 커버리지, 샘플, 최신성과 같은 분석 요구사항은 고정된 상태로 유지합니다. 본 논문에서는 용량 인식 승인 제어(capacity-aware admission)의 지원을 받아 분석 품질 및 클러스터 압박에 대한 요청별 마르코프 결정 과정(MDP)으로 다차원 탄력성을 정형화하는 엔드투엔드 컨트롤러인 ARGOS(Adaptive Reinforcement Learning-Driven Governance for Orchestrated Services)를 제시합니다. ARGOS는 이기종 클러스터에서 통제된 워크로드와 시간에 따라 변하는 다중 테넌트 유입 환경을 바탕으로 평가되었습니다. 통제된 시나리오 전반에서 심층 강화학습 정책은 비학습 기반 베이스라인을 일관되게 능가하며 독립적으로 튜닝된 최적 고정 참조 모델에 근접했습니다. 별도의 실제 환경 평가에서는 현실적이고 포화된 유입 조건에서 정적 중간값 대비 성능 향상을 보였으며, 기록된 CPU 또는 메모리 위반은 없었으나 커버리지 위반은 일부 남아 있었습니다. 이러한 결과는 자원 스케일링만으로는 불충분할 때 심층 강화학습이 다차원 탄력성을 위한 적응형 메커니즘으로 유효함을 뒷받침합니다.
스킬 기반 스마트 제조를 위한 LLM 기반 다중 에이전트 제어
LLM-Driven Multi-Agent Control for Skill-Based Smart Manufacturing
공장은 높은 수준의 제품 맞춤화를 갖춘 소량 생산 체제로 전환되고 있으며, 이에 따라 유연하고 재구성 가능한 자동화 시스템의 빈번한 재프로그래밍이 요구됩니다. 대규모 언어 모델(LLM) 기반 에이전트(agent)는 상호보완적인 두 가지 역할로 배치될 수 있습니다. 오프라인에서는 결정론적 생산 시퀀스를 생성하여 프로그래밍 노력을 줄이고, 온라인에서는 실제 기계를 운영하며 정적 프로그램이 예측할 수 없는 런타임 오류를 처리합니다. 본 논문에서는 각 공장 모듈을 전용 LLM 기반 에이전트 및 OPC UA 메서드 호출을 통해 모듈의 스킬을 노출하는 MCP 툴 서버와 결합하고, 에이전트들이 MQTT를 통해 조율하며 공장 상태의 실시간 업데이트를 바탕으로 그라운딩(grounding)되는 솔루션을 제안합니다. 실제 6개 모듈 육각형 공장의 시뮬레이션 환경에서 무음 하드웨어 결함 감지를 포함하여 복잡성이 증가하는 9가지 생산 과제를 대상으로 세 가지 에이전트 아키텍처(오케스트레이터, 피어투피어, 모놀리식)를 비교합니다. 모놀리식 및 피어투피어 아키텍처는 모두 가장 높은 평균 해결률(93%)을 달성한 반면, 오케스트레이터는 차단된 구간 주변으로 플레이트 경로를 자율적으로 재지정함으로써 10회 실행 모두에서 무음 컨베이어 벨트 결함을 유일하게 해결했습니다. 모든 아키텍처는 명시적인 장애 처리 로직 없이도 창발적(emergent) 결함 진단 동작을 보이며, 표준화된 MCP 툴링, MQTT 기반 에이전트 간 통신, 실시간 상태 주입이 LLM으로 프로그래밍되는 스마트 제조를 위한 실용적이고 재현 가능한 기반임을 입증합니다.
SlackDrive: 적응형 주행 추론을 위한 런타임 슬랙 회수
SlackDrive: Reclaiming Runtime Slack for Adaptive Driving Inference
주행 world-action 모델은 다중모달 추론과 미래 예측을 결합해 계획(planning)을 개선하지만, 커지는 추론 비용은 차량 제어의 실시간 지연(latency) 요구와 점점 더 충돌한다. 기존 가속 방법은 배포 전에 선택된 정책으로 토큰, 레이어, 또는 샘플링 단계를 줄이지만, 공유 온보드 컴퓨트에서 오프라인 프로파일링과 정적 스케줄링 이후 잔여 런타임 변동은 대부분 활용하지 못한다. 우리는 허용 가능한 최대 컴퓨트 예산이 잔여 런타임 상태에 따라 체계적으로 달라지며, 최근 실현 지연(latency)이 가용 컴퓨트 슬랙(slack)에 대한 직접적인 신호를 제공함을 관찰한다. 이 관찰에 기반해, 우리는 실현 지연을 재사용하여 모델 실행 전 각 제어 단계의 컴퓨트 예산을 고르는 추론 전(pre-inference) 컴퓨트 할당기 SlackDrive를 제안한다. SlackDrive는 작은 이산 예산 집합에 대한 지연과 계획(planning) 유틸리티를 한 번 프로파일링하고, 완료된 forward로부터 온라인 컴퓨트 상태를 추정하며, 허용 가능한 지연(latency) envelope 안에 남을 것으로 예측되는 최고 유틸리티 예산을 선택해 주행 백본과 그 컴퓨트 액추에이터는 유지한 채 기존 프로파일링 및 리소스 스케줄링을 보완한다. NAVSIM v2에서 DriveDreamer-Policy와 함께 평가할 때 SlackDrive는 엄격한 지연 체제 하에서 최강 기준선 대비 지연 제약 EPDMS를 21.7% 개선했으며, 전체 예산 모델과 사전 구성된 토큰 가지치기 기준선은 런타임 경합 하에서 허용 가능한 지연 envelope를 초과했다.
HiLLTS: 지속 가능한 교통을 위한 제로샷 계층적 LLM 기반 교통 신호 제어
HiLLTS: Zero-Shot Hierarchical LLM-Guided Traffic Signal Control for Sustainable Transportation
도시 교통 혼잡은 연료 소비, 온실가스 배출, 통근자 지연을 크게 증가시켜 현대 도시에서 상당한 경제적 손실과 환경 피해를 초래한다. 고정 시간 스케줄링, 감응형 제어, 강화학습(RL) 기반 방법과 같은 전통적인 교통 신호 제어 전략은 서로 다른 수준의 적응성을 제공하지만, RL 기반 방법은 네트워크나 수요 체제 간 전이 시 광범위한 재학습, 신중한 보상 설계, 상당한 시뮬레이션 데이터를 필요로 할 수 있다. 이러한 과제를 해결하기 위해, 중앙 조정 에이전트, 구역 층, 다수의 클러스터 수준 교차로 에이전트로 구성된 계층적 3층 아키텍처를 사용하는 LLM 기반 교통 신호 제어 프레임워크인 HiLLTS를 제안한다. 실험 결과는 혼잡 및 환경 성능 모두에서 일관된 개선을 보여준다. 각 시나리오에서 가장 강력한 비-LLM 기준선과 비교했을 때, HiLLTS는 저혼잡 시나리오에서 평균 대기 시간을 36.73% 감소시키고 고혼잡 시나리오에서 14.71% 감소시키며, 평균 CO2 배출량을 각각 7.87% 및 8.57% 감소시킨다. 더 약한 기준선 대비 더 큰 이득이 관찰된다: 저혼잡 조건에서 HiLLTS는 Fixed-Time 제어 대비 배출량 최대 18.00%, 대기 시간 62.07% 감소를 달성하고, 고혼잡 조건에서는 Max Pressure 대비 배출량 최대 28.89%, 대기 시간 40.36% 감소가 관찰된다. 절제 연구는 규칙 기반 제어보다 LLM 기반 조정의 기여를 추가로 검증한다
토론
이 논문과 연결된 포럼 글이 아직 없습니다.