잡샵 스케줄 설정

JSP(Job-shop Scheduling) 또는 Job-shop 문제(JSP)는 컴퓨터 과학 및 운영 연구의 최적화 문제입니다.이것은 최적의 작업 스케줄링의 변형입니다.일반적인 작업 스케줄링 문제에서는 작업 시간₁ J, J₂, ..., J를_n n개 부여하고, 작업 시간 J, J는 일정의 총 길이(즉, 모든 작업이 처리가 완료된 시점)를 최소화하면서 다양한 처리 능력을 가진 m개의 기계로 스케줄링해야 합니다.job-shop scheduling이라고 불리는 특정 바리안트에서는 각 작업은 특정 순서(우선순위 제약)로 처리되어야 하는 일련의 조작₁ O, O₂, ..., O로_n 구성됩니다.각 작업에는 처리해야 하는 특정 시스템이 있으며 한 번에 처리할 수 있는 작업은 1개뿐입니다.일반적인 릴렉스로는 플렉시블 잡샵이 있습니다.여기서 각 작업은 특정 세트의 모든 기계에서 처리할 수 있습니다(각 세트의 기계는 동일합니다).

이 이름은 원래 잡샵의 작업 예약에서 유래했지만 테마에는 이러한 유형의 인스턴스 외에도 다양한 응용 프로그램이 있습니다.이 문제는 가장 잘 알려진 조합 최적화 문제 중 하나이며,^[1] 1966년 Graham에 의해 경쟁 분석이 제시된 첫 번째 문제였다.makespan 목표를 가진 기본 모델의 가장 좋은 문제 사례는 Taillard ^[2]때문입니다.

최적의 작업 스케줄링 문제를 위한 표준 3필드 표기법에서 Job-shop variant는 첫 번째 필드에서 J로 나타난다.예를 들어 " $p_{ij}$ $p_{ij}$ i $\$ style $p_{ij}$ $C_{\max }$ max $\$ 로 나타나는 문제는 유닛 처리 시간의 3 기계 작업 작업장의 문제이며 최대 완료 시간을 최소화하는 것이 목표입니다.

문제의 종류

다음과 같은 다양한 문제가 존재합니다.

머신에는 중복된 머신(복제 머신으로 유연한 작업소)이 있을 수도 있고 동일한 머신 그룹(유연한 작업소)^[3]에 속할 수도 있습니다.
기계에는 작업 간에 일정한 갭이 필요할 수도 있고 유휴 시간이 필요하지 않을 수도 있습니다.
기계는 시퀀스에 의존한 설정을 가질 수 있습니다.
목적 함수는 메이크스판, L 노름_p, 지각, 최대 지연 등을 최소화하는 것일 수 있습니다.다목적 최적화 문제일 수도 있습니다.
작업 j를 시작하기 전에 완료해야 하는 작업 등 작업에 제약이 있을 수 있습니다(워크플로우 참조).또, 목적 함수는 멀티 ^[4]기준일 수도 있다.
작업 집합은 다른 시스템 집합과 관련될 수 있습니다.
결정론적(고정) 처리 시간 또는 확률론적 처리 시간.

NP-경도

순회 세일즈맨 문제는 NP-hard이기 때문에, TSP는 JSP의 특수한 경우(도시는 기계, 세일즈맨은 직업)^{[citation needed]}이기 때문에, 시퀀스에 의존한 설정의 잡숍 문제도 NP-hard이다.

문제의 표현

분리^[5] 그래프는 작업 공간 스케줄링 문제 ^[6]인스턴스를 설명하는 데 사용되는 인기 있는 모델 중 하나입니다.

문제의 수학적 설명은 다음과 같습니다.

$M=\{M_{1},M_{2},\dots ,M_{m}\}$ $M=\{M_{1},M_{2},\dots ,M_{m}\}$ { $M=\{M_{1},M_{2},\dots ,M_{m}\}$ , $M=\{M_{1},M_{2},\dots ,M_{m}\}$ 2 , $M=\{M_{1},M_{2},\dots ,M_{m}\}$ , $M=\{M_{1},M_{2},\dots ,M_{m}\}$ $}$ { $displaystyle$ M = \ { $M$ _ { $1$ } , $M$ _ { $2$ } , \ $dots$ , $M$ _ { $m$ } 、 $J=\{J_{1},J_{2},\dots ,J_{n}\}$ $J=\{J_{1},J_{2},\dots ,J_{n}\}$ { $J=\{J_{1},J_{2},\dots ,J_{n}\}$ $J=\{J_{1},J_{2},\dots ,J_{n}\}$ , $J=\{J_{1},J_{2},\dots ,J_{n}\}$ 2 , $J=\{J_{1},J_{2},\dots ,J_{n}\}$ , $J=\{J_{1},J_{2},\dots ,J_{n}\}$ $J=\{J_{1},J_{2},\dots ,J_{n}\}$ { $displaystyle$ J = \ { J _ $1$ } , { J _ 1 } , { J $_$ { J _ { 1 } , { J _ { 1 $}$ , { J _ 1 } , { J $J=\{J_{1},J_{2},\dots ,J_{n}\}$ { 1 } , { J _ { 1 } , { J _ { J _ { J _ { 1 } ,이 문제의 산업적 원인에 따라 $\displaystyle M_{i}$ 는 $\displaystyle M_{i}$ 기계, $\displaystyle J_{j}$ 는 $\displaystyle J_{j}$ 작업이라고 불립니다.

$(\$ $x\in {\mathcal {X}}$ { $X})$ 는 $\displaystyle \ \mathcal{X}$ 모든 작업이 모든 기계에서 정확히 한 번 수행되도록 모든 작업의 순차적 할당 집합을 나타냅니다. $x\in {\mathcal {X}}$ (\ $displaystyle x\in\mathcal$ {X $})$ 는 $x\in {\mathcal {X}}$ $n\times m$ n $n\times m$ × $n\times m$ (\ $displaystyle n\times$ m $n\times m$ ) $n\times m$ 로 기록될 수 있습니다.여기서 $\displaystyle i$ 은 다음과 같습니다. $\displaystyle \displaystyle$ i는 기계 $\displaystyle i$ $\$ 가 $\displaystyle M_{i}$ 수행하는 작업을 순서대로 나열합니다.예를 들어, 행렬은

({displaystyle x=pmatrix}1&2&3&1&end{pmatrix})

$\displaystyle M_{1}$ $({$ 은 $\displaystyle M_{1}$ $\displaystyle J_{1},J_{2},J_{3}$ J1 $\displaystyle J_{1},J_{2},J_{3}$ $\displaystyle J_{1},J_{2},J_{3}$ $(\$ 의 $\displaystyle J_{1}, J_{2}, J_{3}$ 3가지 $\displaystyle J_{1},J_{2},J_{3}$ 을 J1 $\displaystyle J_{1},J_{2},J_{3}$ $\displaystyle J_{1},J_{2},J_{3}$ $(\$ 의 $\displaystyle J_{1},J_{2},J_{3}$ 로 수행하는 것을 의미합니다 $\displaystyle J_{1},J_{2},J_{3}$ 는 $\displaystyle J_{2},J_{3},J_{1}$ $\displaystyle J_{2},J_{3},J_{1}$ $(\$ J_{ $1$ $\displaystyle J_{2},J_{3},J_{1}$ 으로 작업을 $수행합니다.$

$C:{\mathcal {X}}\to [0,+\infty ]$ 비용 $C:{\mathcal {X}}\to [0,+\infty ]$ C : X $C:{\mathcal {X}}\to [0,+\infty ]$ [ $C:{\mathcal {X}}\to [0,+\infty ]$ , + $C:{\mathcal {X}}\to [0,+\infty ]$ ]{ $displaystyle$ C : { \ $mathcal$ { $X$ } $}$ \ $to$ [ 0 , + \ infty $C:{\mathcal {X}}\to [0,+\infty ]$ ]} 가 있다고 가정합니다.비용 함수는 "총 처리 시간"으로 해석될 수 있으며, $C_{ij}:M\times J\to [0,+\infty ]$ $C_{ij}:M\times J\to [0,+\infty ]$ j $C_{ij}:M\times J\to [0,+\infty ]$ : $C_{ij}:M\times J\to [0,+\infty ]$ × $C_{ij}:M\times J\to [0,+\infty ]$ [ $C_{ij}:M\times J\to [0,+\infty ]$ 0 , + $C_{ij}:M\times J\to [0,+\infty ]$ {\ $C_{ij}:M\times J\to [0,+\infty ]$ ](\ $displaystyle C_$ {ij $}):$ $M\times$ J $\$ $to$ [ $0,+\infty$ $\displaystyle M_{i}$ $(\$ $style$ \ $displaystyle$ M_ $\displaystyle M_{i}$ { $i})$ 가 $(\displaystyle\displaystyle$ J_ ${j$ 작업을 수행하기 위한 비용/시간.

작업장의 문제는 C $\displaystyle C(x)>C(y)$ $x)\displaystyle$ C $(x)$ 가 $x\in {\mathcal {X}}$ $\displaystyle C(x)$ 최소가 $\displaystyle C(x)$ $x\in {\mathcal {X}}$ 할당 x $($ $x)\displaystyle$ $y\in {\mathcal {X}}$ C(x $)$ 를 찾는 $것$ 입니다 $\displaystyle C(x)>C(y)$ 즉, C( $\displaystyle C(x)>C(y)$ style Y(x)\ $display$ style $\displaystyle C(x)>C(y)$ C $)$ 가 $y \in \mathcal{X}$ $\displaystyle C(x)>C(y)$ 하지 않습니다.

스케줄링 효율

스케줄 효율은 다음과 같이 총 처리 시간에 대한 총 기계 유휴 시간의 비율을 통해 정의할 수 있습니다.

$C'=1+{\sum _{i}l_{i}\over \sum _{j,k}p_{jk}={C.m \over \sum _{j,k}p_{jk}}}$

$l_{i}$ 서 l $({$ })은 $l_{i}$ $기계$ i({ $displaystyle$ i $i$ 의 아이돌 시간,C({ $displaystyle$ C $)$ 는 $C$ 제조 간격, $({displaystyle$ m})은 $m$ 기계 수입니다.위의 정의에 따르면 스케줄링 효율은 단순히 머신의 수와 총 처리 시간에 따라 정규화된 제작 기간입니다.이를 통해 크기가 ^[7]다른 JSP 인스턴스 간에 리소스 사용량을 비교할 수 있습니다.

무한 비용 문제

JSP에서 대처해야 할 첫 번째 문제 중 하나는 많은 제안 솔루션이 무한대 비용이 든다는 것입니다. 즉, {\ $mathcal {X}에$ x $x_{\infty }\in {\mathcal {X}}$ $x$ $C(x_{\infty })=+\infty$ $x_{\infty }\in {\mathcal {X}}$ X가 $C(x_{\infty })=+\infty$ 하며, $C(x_{\infty })=+\infty$ {\ $displaystyle$ C $(x_{\$ $infty$ $=$ displaystyle C(x_ ${\$ infty $})})$ 는 $=\fty$ 에 있습니다. $(\displaystyle x_{\infty$ }}) 2대의 $x_{\infty }$ 머신이 교착 상태가 되어 각 머신이 다른 스텝의 출력을 대기하도록 합니다.

주요 결과

Graham은 이미 1966년에 ( $2$ - 1/m $) 경쟁적인$ List Scheduling 알고리즘을 제공했습니다.여기서 m은 ^[1]기계 수입니다.또한 List Scheduling이 2대 및 3대의 최적의 온라인 알고리즘임을 증명하였습니다.균일 길이 작업에 대한 Cofman-Graham 알고리즘(1972)도 두 대의 기계에 최적이며 (2- 2 $/ m)$ ^[8]^[9] 경쟁력이 있습니다 $.$ 1992년, Bartal, Fiat, Karloff 및 Vohra는 1.986의 ^[10]경쟁 알고리즘을 제시했습니다.1994년에 ^[11]Karger, Philips 및 Torng에 의해 1.945의 경쟁 알고리즘이 제시되었습니다.1992년에 Albers는 1.923-경쟁력 ^[12]있는 다른 알고리즘을 제공했습니다.현재 가장 잘 알려진 결과는 플라이셔와 월이 제공한 알고리즘으로 1.9201의 ^[13]경쟁률을 달성했습니다.

Albers는 ^[14]하한 1.852를 제시했다.Taillard 인스턴스는 makespan 목표를 가지고 Job-shop Scheduling을 개발하는 데 중요한 역할을 수행합니다.

1976년에 Garey는 이 문제가 m>2에 대해 NP-완전이라는 증거를^[15] 제공했다. 즉, 3개 이상의 기계에 대한 결정론적 다항식 시간에는 최적의 해를 계산할 수 없다(P=NP가 아닌 경우).

2011년 Xin Chen 등은 이전 ^[17]결과를 개선한 두 개의 관련^[16] 기계에 최적의 온라인 스케줄링을 위한 알고리즘을 제공하였다.

오프라인 제작 시간 최소화

원자적인 작업

오프라인의 makespan 최소화 문제의 가장 단순한 형태는 원자적인 작업, 즉 여러 작업으로 세분화되지 않은 작업을 다룬다.이것은 다양한 크기의 아이템을 고정 개수의 빈에 패킹하는 것과 같기 때문에 필요한 최대 빈 사이즈는 가능한 한 작아집니다(빈의 수를 최소화하고 빈 사이즈를 고정하는 경우 문제는 빈 패킹 문제로 알려져 있는 다른 문제가 됩니다).

도릿 S. Hochbaum과 David Shmoys는 1987년에 원자 작업의 오프라인 메이크스판 최소화 문제에 대한 근사 솔루션을 원하는 ^[18]정확도로 찾는 다항식 시간 근사 체계를 제시했다.

여러 작업으로 구성된 작업

첫 번째 모든 조작이 첫 번째 머신에서, 두 번째 모든 조작이 두 번째 머신에서 수행되어야 하며 단일 작업을 병렬로 수행할 수 없도록 M 머신을 통해 작업을 스케줄링하는 문제의 기본 형식을 플로우샵 스케줄링 문제라고 합니다.유전자 ^[19]알고리즘을 포함한 다양한 알고리즘이 존재합니다.

존슨 알고리즘

S. M. Johnson의 휴리스틱 알고리즘을 사용하여 모든 작업이 동일한 ^[20]순서로 처리될 때 2 머신 N 작업 문제를 해결할 수 있습니다.알고리즘의 순서는 다음과 같습니다.

작업_i P에는 머신 M1, M2에서 실행되는 기간_i1 P, P의_i2 두 가지 조작이 있습니다.

단계 1. 목록 A = { 1, 2, …, N }, 목록 L1 = {}, 목록 L2 = {}.
2단계. 사용 가능한 모든 작동 시간 중에서 최소를 선택합니다.

최소값이 P에_k1 속한다면

목록 A에서 K를 삭제하고 목록 L1의 끝에 K를 추가합니다.

최소값이 P에_k2 속한다면,

목록 A에서 K를 삭제하고 목록 L2의 선두에 K를 추가합니다.

스텝 3. 리스트A가 비워질 때까지 스텝2를 반복합니다.
스텝 4. 리스트 L1, 리스트 L2에 가입합니다.이것이 최적의 순서입니다.

Johnson의 방법은 두 대의 기계에서만 최적으로 작동합니다.다만, 최적이며 계산도 간단하기 때문에, 일부의 연구자는, M머신(M > 2)에 채용하려고 하고 있습니다.

아이디어는 다음과 같습니다.각 작업에 M1, M2 … Mm의 순서로 m개의 연산이 필요하다고 가정합니다. 우리는 첫 번째 m/2 기계를 (가상의) 기계 센터, MC1, 나머지 기계를 기계 센터 MC2로 결합합니다.다음으로 MC1 = sum의 작업 P의 총 처리시간(첫 번째 m/2 머신의 작업시간)과 MC2 = sum의 작업 P의 처리시간(마지막 m/2 머신의 작업시간)을 나타냅니다.

이를 통해 m-Machine 문제를 Two Machining center scheduling 문제로 줄였습니다.우리는 Johnson의 방법으로 이것을 해결할 수 있다.

메이크스판 예측

머신러닝은 실제로 최적의 ^[7]스케줄을 작성하지 않고 JSP 인스턴스의 최적의 메이크 스팬을 예측하기 위해 최근 사용되고 있습니다.예비 결과는 평균 대비 최적의 스케줄링 효율성을 바탕으로 무작위로 생성된 소규모 JSP 인스턴스를 분류하기 위해 감독 기계 학습 방법을 적용했을 때 약 80%의 정확성을 보였다.

예

다음으로 인디케이터 제약이 있는 혼합 정수 프로그래밍 문제로 AMPR에서 공식화된 잡샵 스케줄링 문제의 예를 나타냅니다.

매개 변수 N_JOBS, 매개 변수 N_MACHINES, JOBS 순서 설정 = 1..N_JOBS. 순서가 지정된 시스템을 = 1로 설정합니다.N_MACHINES; 파라미터 처리 시간{JOBS,MACHINES} > 0, 매개 변수 누적 시간 {i, j in JOBS} = 총 {machines: ord(machines): <= ord(j)} 처리 시간[i,j], 매개 변수 TimeOffs {i1 in JOBS: i1 <> i2} = max[J]OBS}>=0;precedes{JOBS에 i1, JOBS에 i2:ord(i1)<>ord(i2)}2진 var,makespan:끝을 줄이makespan_def{나는 JOBS에}에 subj:끝>)start[나는]+sum{MACHINES에서 j}ProcessingTime[i,j], no12_conflict{JOBS에 i1, JOBS에 i2:ord(i1)<>ord(i2)}에 subj:precedes[i1,i2]==>, start[i2]>)start[i1]+TimeOffset[i1,i2], subj시는 말씀은 아니라는 말21_conflict{i1에JOBS, i2 in JOBS: ord(i1) < ord(i2): !https[i1] => start[i2] + TimeOffset[i2,i1]; 데이터; 매개 변수 N_JOBS:= 4, 매개 변수 N_MACHINES: 4; 매개 변수 처리 시간 1: 4: 4: 3:

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Graham, R. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x.
^ "Taillard Instances".
^ Maccarthy (1993). "Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling".
^ Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5.
^ B. 로이, B.Sussmann, Les problémes d'ordonnancement avec 제약조건 디스존티브, SEMA, Note D.S., No. 9, 파리, 1964.
^ Jacek Bwaewewicz, Erwin Pesch, Mawgorzata Sterna, 잡샵 스케줄링 문제의 분리 그래프 머신 표현, 유럽 운영 연구 저널, 제127권, 제2호, 2000년 12월 1일, 페이지 317-22-17, ISSN 07-17-17-10S.
^ ^a ^b Mirshekarian, Sadegh; Šormaz, Dušan N. (2016). "Correlation of job-shop scheduling problem features with scheduling efficiency" (PDF). Expert Systems with Applications. 62: 131–147. doi:10.1016/j.eswa.2016.06.014.
^ 를 클릭합니다Coffman, E. G. Jr.; Graham, R. L. (1972), "Optimal scheduling for two-processor systems" (PDF), Acta Informatica, 1 (3): 200–213, doi:10.1007/bf00288685, MR 0334913, S2CID 40603807.
^ 를 클릭합니다Lam, Shui; Sethi, Ravi (1977), "Worst case analysis of two scheduling algorithms", SIAM Journal on Computing, 6 (3): 518–536, doi:10.1137/0206037, MR 0496614.
^ Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). "New Algorithms for an Ancient Scheduling Problem". Proc. 24th ACM Symp. Theory of Computing. pp. 51–58. doi:10.1145/129712.129718.
^ Karger, D.; S. Phillips; E. Torng (1994). "A Better Algorithm for an Ancient Scheduling Problem". Proc. Fifth ACM Symp. Discrete Algorithms.
^ Albers, Susanne; Torben Hagerup (1992). "Improved parallel integer sorting without concurrent writing". Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. Symposium on Discrete Algorithms archive. pp. 463–472.
^ Fleischer, Rudolf (2000). Algorithms – ESA 2000. Berlin / Heidelberg: Springer. pp. 202–210. doi:10.1007/3-540-45253-2_19. ISBN 978-3-540-41004-1.
^ Albers, Susanne (1999). "Better bounds for online scheduling". SIAM Journal on Computing. 29 (2): 459–473. CiteSeerX 10.1.1.685.8756. doi:10.1137/S0097539797324874.
^ Garey, M.R. (1976). "The Complexity of Flowshop and Jobshop Scheduling". Mathematics of Operations Research. 1 (2): 117–129. doi:10.1287/moor.1.2.117. JSTOR 3689278.
^ Chen, Xin; Lan, Yan; Benkő, Attila; Dósa, György; Han, Xin (2011). "Optimal algorithms for online scheduling with bounded rearrangement at the end". Theoretical Computer Science. 412 (45): 6269–6278. doi:10.1016/j.tcs.2011.07.014.
^ Liu, M.; Xu, Y.; Chu, C.; Zheng, F. (2009). "Online scheduling on two uniform machines to minimize the makespan". Theoret. Comput. Sci. 410 (21–23): 2099–2109. doi:10.1016/j.tcs.2009.01.007.
^ Hochbaum, Dorit; Shmoys, David (1987). "Using dual approximation algorithms for scheduling problems: theoretical and practical results" (PDF). Journal of the ACM. 34 (1): 144–162. CiteSeerX 10.1.1.125.5753. doi:10.1145/7531.7535. S2CID 9739129.
^ Khuri, Sami; Miryala, Sowmya Rao (1999). "Genetic Algorithms for Solving Open Shop Scheduling Problems". Proceedings of the 9th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence. London: Springer Verlag. CiteSeerX 10.1.1.29.4699.
^ S.M. 존슨, 설정 시간을 포함한 최적 2단계 및 3단계 생산 일정, 해군 대장.쿼트 I(1954)61-68

외부 링크

Vienna 대학 동적 최적화를 위한 방법론, 시스템 및 소프트웨어 디렉토리.
테일라드 인스턴스
브루커 P. 스케줄링 알고리즘하이델베르크, 스프링거제5회ISBN 978-3-540-24804-0

[graham1966-1] Graham, R. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x.

[TaillardIns-2] "Taillard Instances".

[3] Maccarthy (1993). "Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling".

[4] Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5.

[5] B. 로이, B.Sussmann, Les problémes d'ordonnancement avec 제약조건 디스존티브, SEMA, Note D.S., No. 9, 파리, 1964.

[6] Jacek Bwaewewicz, Erwin Pesch, Mawgorzata Sterna, 잡샵 스케줄링 문제의 분리 그래프 머신 표현, 유럽 운영 연구 저널, 제127권, 제2호, 2000년 12월 1일, 페이지 317-22-17, ISSN 07-17-17-10S.

[:0-7] Mirshekarian, Sadegh; Šormaz, Dušan N. (2016). "Correlation of job-shop scheduling problem features with scheduling efficiency" (PDF). Expert Systems with Applications. 62: 131–147. doi:10.1016/j.eswa.2016.06.014.

[8] 를 클릭합니다Coffman, E. G. Jr.; Graham, R. L. (1972), "Optimal scheduling for two-processor systems" (PDF), Acta Informatica, 1 (3): 200–213, doi:10.1007/bf00288685, MR 0334913, S2CID 40603807.

[9] 를 클릭합니다Lam, Shui; Sethi, Ravi (1977), "Worst case analysis of two scheduling algorithms", SIAM Journal on Computing, 6 (3): 518–536, doi:10.1137/0206037, MR 0496614.

[10] Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). "New Algorithms for an Ancient Scheduling Problem". Proc. 24th ACM Symp. Theory of Computing. pp. 51–58. doi:10.1145/129712.129718.

[11] Karger, D.; S. Phillips; E. Torng (1994). "A Better Algorithm for an Ancient Scheduling Problem". Proc. Fifth ACM Symp. Discrete Algorithms.

[12] Albers, Susanne; Torben Hagerup (1992). "Improved parallel integer sorting without concurrent writing". Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. Symposium on Discrete Algorithms archive. pp. 463–472.

[13] Fleischer, Rudolf (2000). Algorithms – ESA 2000. Berlin / Heidelberg: Springer. pp. 202–210. doi:10.1007/3-540-45253-2_19. ISBN 978-3-540-41004-1.

[14] Albers, Susanne (1999). "Better bounds for online scheduling". SIAM Journal on Computing. 29 (2): 459–473. CiteSeerX 10.1.1.685.8756. doi:10.1137/S0097539797324874.

[garey1976-15] Garey, M.R. (1976). "The Complexity of Flowshop and Jobshop Scheduling". Mathematics of Operations Research. 1 (2): 117–129. doi:10.1287/moor.1.2.117. JSTOR 3689278.

[16] Chen, Xin; Lan, Yan; Benkő, Attila; Dósa, György; Han, Xin (2011). "Optimal algorithms for online scheduling with bounded rearrangement at the end". Theoretical Computer Science. 412 (45): 6269–6278. doi:10.1016/j.tcs.2011.07.014.

[17] Liu, M.; Xu, Y.; Chu, C.; Zheng, F. (2009). "Online scheduling on two uniform machines to minimize the makespan". Theoret. Comput. Sci. 410 (21–23): 2099–2109. doi:10.1016/j.tcs.2009.01.007.

[hs-18] Hochbaum, Dorit; Shmoys, David (1987). "Using dual approximation algorithms for scheduling problems: theoretical and practical results" (PDF). Journal of the ACM. 34 (1): 144–162. CiteSeerX 10.1.1.125.5753. doi:10.1145/7531.7535. S2CID 9739129.

[ossp-ga-19] Khuri, Sami; Miryala, Sowmya Rao (1999). "Genetic Algorithms for Solving Open Shop Scheduling Problems". Proceedings of the 9th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence. London: Springer Verlag. CiteSeerX 10.1.1.29.4699.

[20] S.M. 존슨, 설정 시간을 포함한 최적 2단계 및 3단계 생산 일정, 해군 대장.쿼트 I(1954)61-68

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[17]

[16]

[18]

[19]

[20]

v t 최적의 작업 스케줄링 문제
1단계 작업	싱글 머신 동일 기계 균일한 기계 관련 없는 기계
다단계 작업	병렬 태스크 오픈 숍 플로우 숍 잡샵
최적화 목표	메이크스판 귀기울림 지각 지각 스루풋
기타 요건	인터벌 스케줄링 정확한 작업 스케줄링

Search

잡샵 스케줄 설정

네임스페이스

더

목차

문제의 종류

NP-경도

문제의 표현

스케줄링 효율

무한 비용 문제

주요 결과

오프라인 제작 시간 최소화

원자적인 작업

여러 작업으로 구성된 작업

존슨 알고리즘

메이크스판 예측

예

관련 문제

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

잡샵 스케줄 설정

문제의 종류

NP-경도

문제의 표현

스케줄링 효율

무한 비용 문제

주요 결과

오프라인 제작 시간 최소화

원자적인 작업

여러 작업으로 구성된 작업

존슨 알고리즘

메이크스판 예측

예

관련 문제

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.