Open Source Robotics

고품질 오픈소스 로봇 프로젝트, 도구 및 소프트웨어의 엄선된 컬렉션.

Job-Shop Scheduling

  • 다른 이름: JSSP, JSP, job-shop problem
  • 카테고리: Planning & manipulation › Task-level
  • 태그: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning

각 작업이 자신만의 고정된 기계 경로를 따르는 상황에서 공유 기계 위 공정들의 순서를 정하는 조합 최적화 문제로, 보통 모든 작업이 끝날 때까지의 시간(메이크스팬)을 최소화하는 것이 목적이다.

정의

잡숍 스케줄링(Job-shop scheduling)은 공유된 기계 집합에서 각 공정이 언제 실행될지 결정하는 문제다. n개의 작업과 m대의 기계가 있다. 각 작업은 정해진 순서대로 수행해야 하는 공정의 시퀀스이며, 각 공정은 특정한 기계 하나를 알려진 처리 시간 동안 필요로 한다. 기계는 한 번에 하나의 공정만 처리할 수 있으며, 고전적인 버전에서는 공정이 일단 시작되면 중단될 수 없다. 과제는 목적 함수가 최소화되도록 모든 기계에서 공정의 순서를 선택하는 것이며, 목적 함수는 대개 마지막 작업이 끝나는 시각인 메이크스팬(makespan)이다. 다른 목적 함수로는 납기 대비 총 납기 지연과 총 흐름 시간이 있다.

이 문제는 일반적으로 NP-난해이며, 작은 인스턴스조차 입증된 최적성까지 풀기 어려울 수 있다. 자유도가 얼마나 있는지에 따라 달라지는 가까운 변형들이 있다. 플로숍(flow shop)에서는 모든 작업이 같은 순서로 기계를 거치고, 오픈숍(open shop)에서는 작업 내 공정의 순서가 자유로우며, 유연 잡숍(flexible job shop)에서는 각 공정이 허용된 집합의 어느 기계에서든 실행될 수 있으므로 솔버가 기계 배정도 해야 한다. 이 문제를 모델링하는 표준적인 방법은 이접 그래프(disjunctive graph)로, 고정된 호가 각 작업 안의 순서를 나타내고, 무방향 호의 쌍이 공유 기계에서 어느 공정이 먼저 갈지에 대한 아직 열린 선택을 나타낸다.

해법은 처리 시간이 가장 짧은 것을 먼저 하는 것 같은 단순한 디스패칭 규칙(dispatching rules)부터, 혼합 정수 계획법, 제약 프로그래밍, 분기 한정법에 기반한 정확한 방법, 그리고 타부 탐색, 담금질 기법, 유전 알고리즘 같은 메타휴리스틱까지 다양하다. 더 최근의 연구는 강화학습으로 디스패칭 정책을 학습하며, 흔히 이접 그래프 위에서 그래프 신경망을 사용한다. 로봇공학에서 잡숍 정식화는 셀 안의 여러 로봇, 기계, 워크스테이션이 시간을 나눠 써야 할 때 등장한다. 로봇은 기계나 자원 역할을 하고, 태스크는 공정이 되며, 그렇게 나온 스케줄은 이후 모션 계획과 로봇 프로그램으로 바뀐다.

중요한 이유

여러 로봇이나 기계가 순서 제약이 있는 작업을 나눠 할 때는, 태스크의 순서가 개별 로봇의 속도만큼이나 처리량과 유휴 시간을 좌우한다. 계획 문제를 잡숍이나 유연 잡숍 인스턴스로 인식하면, 평가하기 어려운 수작업 휴리스틱 대신 성숙한 솔버, 벤치마크 인스턴스, 알려진 한계를 활용할 수 있다.

주요 응용

  • 제조 셀에서 여러 로봇과 기계에 걸친 태스크 순서 결정
  • 로봇 팔들 사이에 공유 워크스테이션과 고정구 할당
  • 가공, 조립, 시험 라인의 생산 계획
  • 학습 기반 계획기와 언어 모델 계획기를 포함한 태스크 계획기를 최적 스케줄과 비교하는 벤치마킹
  • 공장에서 여러 기계를 담당하는 이동 로봇의 스케줄링

실제 사례

한 조립 셀에 로봇 팔 두 대, CNC 기계 한 대, 고정구 스테이션 하나가 있다. 각 제품은 정해진 단계 순서가 필요하다. 소재를 CNC에 넣고, 가공하고, 고정구로 옮긴 다음, 부품 두 개를 삽입한다. 엔지니어는 각 제품을 작업으로, 각 단계를 그것을 수행하는 로봇이나 기계에 묶인 공정으로 모델링하고, 라인에서 측정한 처리 시간을 추가한다. 구간 변수와 자원별 비중첩 제약을 사용하는 제약 프로그래밍 솔버가 메이크스팬을 최소화하는 스케줄을 반환한다. 엔지니어는 이어서 스테이션 사이의 이동 시간과 진입 금지 규칙을 추가해 두 팔이 동시에 공유 고정구 영역에 배정되지 않도록 하면서 스케줄이 물리적으로 실행 가능한지 확인하고, 스케줄은 각 로봇의 프로그램으로 바뀐다.

흔한 오해

  • 잡숍 스케줄링은 태스크 할당과 같다 — 할당은 누가 태스크를 할지 정하는 반면, 잡숍 스케줄링은 각 공유 자원에서 공정의 순서와 시점까지 정한다
  • 모든 작업은 같은 순서로 기계를 거친다 — 그것은 플로숍이며, 잡숍에서는 각 작업이 자신만의 경로를 가진다
  • 유효한 스케줄은 곧바로 로봇에 쓸 수 있다 — 고전적인 모델은 추가 제약으로 넣지 않는 한 로봇 간의 이동, 준비, 충돌을 무시한다
  • 최적 스케줄은 항상 얻을 수 없다 — 제약 프로그래밍과 혼합 정수 솔버는 실제 인스턴스에 대해 흔히 최적 또는 최적에 가까운 스케줄을 찾으며, 최적성을 증명하기 어려운 것은 주로 크거나 제약이 빡빡한 인스턴스다

알아야 할 사람

  • 다중 로봇 셀을 설계하는 제조 및 자동화 엔지니어
  • 과제 계획과 다중 로봇 협조를 연구하는 로봇공학 연구자
  • 생산 스케줄러를 만드는 운영 연구 엔지니어
  • 산업용 로봇을 위한 언어 모델 기반 또는 학습 기반 계획기 개발자

관련 기술

  • 제약 프로그래밍(Constraint Programming)
  • Google OR-Tools CP-SAT
  • 혼합 정수 선형 계획법(Mixed-Integer Linear Programming)
  • 디스패칭 규칙(Dispatching Rules)
  • 타부 탐색(Tabu Search)
  • 유연 잡숍 스케줄링(Flexible Job-Shop Scheduling)

관련 용어

  • Task Planning
  • Mixed-Integer Programming
  • Task and Motion Planning
  • Multi-Agent Path Finding
  • Digital Twin

관련 프로젝트

  • BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
  • Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
  • IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
  • X-VLA: Cross-embodiment VLA model with soft-prompted scaling
  • Swarm-SLAM: Decentralized collaborative SLAM for robot swarms with bandwidth-aware loop closing
  • PlanSys2: The PDDL-based task planning system for ROS 2 — symbolic AI planning on real robots

동영상

  • Operations Research 09D: Job Shop Scheduling Problem: Yong Wang
  • Mod-07 Lec-28 Job shop scheduling -- Gantt chart, Different dispatching rules: nptelhrd

이 웹사이트는 JavaScript가 필요합니다. 오픈소스 로봇 프로젝트를 탐색하려면 JavaScript를 활성화하세요.