Scheduling
스케줄:어떤 것이 언제 일어나기로 되어 있는 지 알려줌
스케줄링: 스케쥴을 생성하는 프로세스/가지고 있는 자원을 어떤 과업을 수행하기 위해 시간에 따라서 활당하자 /일상에서 자원이 한정되어 있기에 스케쥴링은 필수적
제조업에서 스케쥴링이란
-자원: 기계
-업무: job이란 opreations으로 구성->ex.10개의 오퍼를 끝내야 하나의 잡이 끝난다
-shop: 일정을 계획하는 환경/생산라인
scheduling
-제조업에서 생산 실행하기 전 마지막 단계
-생산하기 전 마지막 단계
-여러개의 기계를 순서에 맞게 동시에 진행
-시간에 따라 여러기계
-셋업 체인지
-시간 개념o
-시간의 흐름에 따라 여러 기계를 어떻게 할당할지
sequencing
-오직 하나의 기계에 job 주문
-우선순위 job
-순서만 정한다(시간개념x)
제조 시스템의 운영단계
목표 계획 시스템
factory planning
factory planner
실행계획 시스탬
scheduling
scheduler
(생산 시작)
dispatching
dispatcher
간트차트
-x=시간/y=기계
-시간의 흐름에 따른 각 기계의 job들에 대한 작업 순서와 시간을 파악 가능
-복잡한 job 묘사 혹은 job들간의 상호 유기적 관계를 나타내느데 한계가 존재
-시각화에 기능이 중요한거지 너무 믿으면 안된다(로우 데이터를 확인하던가 해야한다)
-특정 lot의 흐름만 관찰 가능
-하얀색 공백-설비가 노는 시간
-빗금-intentional delay-나중을 위해 잠깐 기다렸다가 하는 시간
liveGantt:거대한 생산시스템
스케줄링의 기본적으로 알아야 하는 내용
input
-스케줄링 전 알고 있는 정보이며 소문자로 표현
-pj(processing timer): job j에게 요구 되는 실행 양
-rj(release date):작업 시작 가능 시간
-dj(due date):만기일(넘어가면 지각)
*single machine sequencing에서,
c3에 의해 pj는 processing time과 setup time도 포함
c1에 의해 rj는 arrival time과 유사한 의미,rj=0
output
-스케줄링 의사결정의 결과로 생성되는 정보이며, 대문자로 표현
-Cj(completion time):processing time이 끝난 시간
-Fj(flowtime):시스템에 job이 머문 시간=Fj=Cj-rj(single machine=Cj-0->Fj=Cj)
-Lj(lateness):초과한 시간=Lj=Cj-dj/음수면 작업을 빨리 끝낸것이고 양수면 작업을 늦게 끝낸것
-Tj(tardiness):지각=max{0,Lj}->음수면 0 양수면 Lj
모든 job에 대한 종합적인 성능 지표(중요도에 따라 사용된다)
-F=Fj의 합
-T=Tj의 합
-Fmax
-Tmax
-U=Tj의 갯수
-Cmax->단축시키는게 스케줄링에서 중요
Single Machine Sequencing(시간개념x)
*single machine problem의 조건
-c1:싱글 오퍼레이션은 job은 프로세싱 동시에 가능/어떤잡도 문제를 풀기 시작하는 순간에 다 바로 활당 가능->rj=0
-c2:기계는 한번에 하나의 job만 가능하다
-c3:setup times는 Pj에 포함되어 있다
-c4:job 표현은 미리 결정되어 알려져 있어야 한다/원래는 릴리즈 타임 같은게 확률에 따라 바뀐다(멀티)
-c5:기계는 계속적으로 가능하다(고장이 일어나지 않고)
-c6:기계는 쉴수없다(일이 계속 있으면)-intension delay 고려하지 않는다
-c7:작업이 시작 되면 방해없이 계속 진행된다-한번 일 시작하면 끝까지
n개의 job의 sequence는 각 job의 index들의 permutation과 대응됨
싱글머신의 해결의 숫자n!
premutation schedule-정수들의 나열(7가지 조건이 성립되어야 가능)
대괄호가 sequence안의 위치를 나타내는데 사용될 수 있음
[5]=2는 sequence의 5번째 job은 job 2
d[1]:sequence의 첫 번째 job의 납기
single machine problem의 의의
-매우 간단하며 다양한 shop들 중 특별한 case(모든 job이 하나의 오퍼로 구성)
-설비가 여러 대 있지도 않으며 연속된 단계도 존재하지 않음
-그러나 single machine problem의 분석 결과는 복잡한 shop의 문제에 적용될 heuristc의 기초가 될 수 있음
-복잡한 스케쥴링 문제는 간단한 single machine problem으로 분해될 수 있음
heuritic이란
-최적이 보장되진 않지만 실용적인 방법으로 완벽하진 않지만 충분히 즉각적인(빠른) 목표에 도달 할 수있다
-다양한 분야에 사용(법,ai)
-스케쥴링에서 dispatching rule도 일종
dispatching rule
-간단하게 구현 가능하며, 빠른 시간 내에 만족할 만한 수준의 solution을 얻을 수 있음
-제한적으로 사용이 가능하며, 특정 경우에는 매우 안 좋은 품질의 solution을 산출함
-FIFO:first in first out/min r
-SPT:shortest p
-LPT:longest p
-EDD:earliest d
-MST:min (slack time(dj-pj-t))
-CR:min (dj-t)/pj/ 남은시간/남은 일 / CR>1 여유/ = t=dj/ <1 늦음
-MOR:남은 공정의 수가 많은 job부터 할당
-LOR:남은 공정의 수가 적은 job부터
-SSU:setup time이 짧은 job부터 할당
-SPTSSU: setup+processing time이 짧은 job부터 할당
rj가 없어야 single machine sequencing
납기가 없는 문제들
flowtime
-제품이 고객에게 도달하기까지의 시간(TAT)
-시간을 최소화하면 비용을 최소화 할 수 있음
inventory
-shop에 물리적으로 투자된 비용(저장공간의 확보)
-시스템에 존재하는 평균 job의 수를 최소화하면 inventory레벨을 낮게 유지할 수 있음
두 문제의 관계
-job의 순서는 F를 최소화 하면서 동시에 J를 최소화한다
-j(t):t시점에 잡의 갯수
-J:j(t)의 평균
-F:F[]의 합
-F[1]=p[1]
-F[2]=p[1]+p[2]
-A=F=J x Fmax
J와 F는 비례
-F는 달라질 수 있지만 Fmax는 상수
-F(t)의 면적은 경사가 점점 완만해질수록 최소화 됨
-짧은거 먼저 하는게 효율적=경사가 완만해짐
->F를 최소화 하려면SPT(증명은 35pg보기)
납기가 있는 문제
L최소화
-L과 F가 dj의 합이 상수라 비례한다
-SPT가 최소화 시켜준다
-납기 신경쓰지 않는 dispatching rule임에도 납기 문제의 최적해를 산출한다
-EDD는 최소화를 보장하지 못한다
Lmax최소화
-EDD가 가능하다(Tmax도 최소화 시켜준다)
U의 수를 최소화
-EDD는 U가 0or1일 때 최선 그러나 2이상 일때는 EDD가 최선을 보장하지 못한다
-U의 수를 최소화 하는 알고리즘
(1)A와 B 집합을 나눠서 B에 EDD순서로 넣어준다
(2)순서에 맞게 pj를 합쳐주고 합이 dj를 넘는 순간 멈춘다
(3)pj중 가장 큰 수를 A집합에 넣어준다
-계속 반복하다가 더 이상 지각이 없는 순간 멈춘다
-B안의 순서(EDD)는 그대로 A는 알아서 나열해도 상관없다(F or Tmax 최소화 하고 싶은데로 계산해서 나열)
the other shops
flow shop scheduling(플로우 샵 스케줄링)
▪ 작업은 초기 시스템에서 여러 중간 시스템을 거쳐 최종 시스템으로 흐릅니다.
완료하기 전에
▪ 작업은 별도의 작업으로 나누어지고 각 작업은 다른 시스템에서 수행됩니다.
▪ 첫 번째 이후의 각 작업에는 정확히 하나의 직접 선행 작업이 있고 마지막 작업 이전의 각 작업에는 정확히 하나의 선행 작업이 있습니다.
직계 후계자 1명
▪ 작업 𝑗의 동작: (1, 𝑗), (2, 𝑗), …, (𝑚, 𝑗)
job shop scheduling(잡샵 스케줄링)
▪ 작업 흐름이 단방향이 아닙니다.
▪ 작업의 첫 번째 작업만 수행하는 초기 머신도 없고, 작업의 마지막 작업만 수행하는 터미널 머신도 없습니다.
▪ 작업 𝑖의 작업 𝑗에는 기계 𝑘이 필요함을 나타내기 위해 세 개의 기호(𝑖,𝑗, 𝑘)를 사용하여 작업을 설명합니다.