오픈 숍 스케줄

Open-shop scheduling

오픈샵 스케줄링 또는 오픈숍 스케줄링 문제(OSSP)는 컴퓨터 과학 및 운영 연구의 최적화 문제입니다.이것은 최적의 작업 스케줄링의 변형입니다.일반적인 작업 스케줄링 문제에서는 일정의 총 길이(즉, 모든 작업이 처리가 완료된 시점)를 최소화하면서 다양한 처리 능력을 가진 m대의 기계에서 스케줄링해야 하는 다양한 처리 시간의 작업1 J, J2, ..., J가n n개 주어집니다.오픈샵 스케줄링이라고 불리는 특정 변형에서는 각 작업은 임의의 순서로 처리해야 하는 일련의 조작1 O, O2, ..., O로n 구성됩니다.이 문제는 Teofilo F에 의해 처음 연구되었다. 곤잘레스와 [1]사르타즈 사니 1976년

최적의 작업 스케줄링 문제를 위한 표준 3필드 표기법에서 오픈샵 변형은 첫 번째 필드에서 O로 표시됩니다.예를 들어 " j style max{\max로 나타나는 문제는 유닛 처리 시간의 3 기계 작업 작업장의 문제이며 최대 완료 시간을 최소화하는 것이 목표입니다.

정의.

오픈샵 스케줄링 문제에 대한 입력은 n개의 작업 세트, 다른 m개의 워크스테이션 세트 및 각 작업이 각 워크스테이션에서 소비해야 하는 시간의 2차원 표(가능성이 0)로 구성됩니다.각 작업은 한 번에 하나의 워크스테이션에서만 처리할 수 있으며 각 워크스테이션은 한 번에 하나의 작업만 처리할 수 있습니다.다만, 잡샵의 문제와는 달리, 처리 순서는 자유롭게 다릅니다.목표는 각 워크스테이션에 의해 처리되는 각 작업의 시간을 할당하는 것입니다.이것에 의해, 동시에 2개의 워크스테이션에 2개의 작업이 할당되지 않고, 모든 작업이 각 워크스테이션에 필요한 시간만큼 할당됩니다.솔루션의 품질에 대한 통상적인 척도는 제조시간입니다.이것은 스케줄의 개시로부터(워크스테이션에의 최초의 할당) 종료까지의 시간(마지막 워크스테이션에서의 마지막 작업의 종료시간)입니다.

계산의 복잡성

오픈샵 스케줄링 문제는 워크스테이션이 2개만 있거나 작업이 2개뿐인 경우 다항식 시간에 해결할 수 있습니다.또한 0이 아닌 모든 처리 시간이 동일한 다항식 시간에도 해결할 수 있습니다. 이 경우 이 문제는 작업과 워크스테이션을 정점으로 하는 초당 그래프에 엣지 색칠을 하는 것과 같아지며, 처리 시간이 0이 아닌 모든 작업-워크스테이션 쌍에 대해 엣지를 갖는 것과 같아집니다.색상의 가장자리 색상은 작업-워크스테이션 쌍이 처리되도록 예약된 시간 세그먼트에 해당합니다.이분 그래프의 선 그래프는 완벽한 그래프이기 때문에, 이분 그래프는 다항식 시간에 에지 색상이 될 수 있습니다.

처리시간이 다른3대 이상의 워크스테이션 또는3대 이상의 작업의 경우 오픈샵 스케줄링은 NP [2]하드입니다.

관련 문제

  • Job-shop 스케줄링도 비슷한 문제이지만 아직 추가적인 제약이 있습니다. 즉, 작업은 특정 순서로 수행해야 합니다.
  • 플로우 숍 스케줄링은 작업 숍 스케줄링이지만 흐름 제약이 추가되어 각 작업은 특정 머신에서 수행해야 합니다.

레퍼런스

  1. ^ 를 클릭합니다Gonzalez, Teofilo; Sahni, Sartaj (1976), "Open shop scheduling to minimize finish time", Journal of the ACM, 23 (4): 665–679, CiteSeerX 10.1.1.394.1507, doi:10.1145/321978.321985, MR 0429089.
  2. ^ Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast'janov, S. V.; Shmoys, D. B. (1997), "Short shop schedules", Operations Research, 45 (2): 288–294, doi:10.1287/opre.45.2.288, JSTOR 171745, MR 1644998