Job Shop Scheduling

Job shop scheduling은 일련의 작업(task)들을 일련의 기계(resource)들에 시간적으로 할당하는 문제로, 선행 조건 및 용량 제약 조건을 만족시키면서, makespan (총 완료 시간), 지연 시간, 또는 비용과 같은 성능 지표를 최적화하는 것을 목표로 합니다. Job shop 문제는 운영 연구 분야의 고전적인 조합 최적화 문제이며, 휴리스틱(탐욕적 디스패칭 규칙, 시뮬레이티드 어닐링, 유전 알고리즘)과 정확한 알고리즘(분기 한정법, 제약 프로그래밍)을 통해 해결됩니다. 이는 제조, 프로젝트 관리, 그리고 계산 스케줄링의 기본이 됩니다.