West_Cold

확률과정
-time step: 이벤트 발생 시점
-간격:시간 간격이 일정(현실은 다르지만)
-수:이벤트 수가 유한함(무한할 수 있는 경우도 존재)
-T:발생하는 이벤트의 총 숫자

State
-존재 가능한 모든 state의 집합
-개수가 유한하다고 가정

Action
-존재 가능한 모든 Action의 집합
-Discrete Action space:action유한하고 그중 한개를 택
-Continuous Action space:action이 무한하고 n차원 백터로 표현됨

Reward
-r t+1:st에서 at를 수행하였을 때의 가치


Transition Probability(전이 확률)
-P(궁금l조건)->확실하지 않아 확률 도입
-MDP시점에서는 다음 상태의 값은 직전 상태에서만 액션을 받고 그 이전 히스토리는 관계가 없다
-MDP가 강화학습에 성능이 좋음


감가상각
-reward는 항상 고유한가?
-적용: (rt)*(r의 T-t-1승)

Markov Decision Process(MDP)
-5개 듀플로 정의:M=(S,A,R,r,P)
-S:State
-A:Action
-R:Reward
-P:Transition probability
-r:감가상각


MDP의 목적
-reward합을 최대화 하고 싶음
-그러려면 action을 적절하게 잘 선택해야 함
-잘 선택하려면 현재 상황에 맞는 액션을 선택
-적절한 액션 선택이란 현재 상태에서 기워드 합을 최대화 하는 액션을 선택
-당장 근시안적으로 reward가 아닌 합을 최대화

Value Function
-state-value function: state의 가치 함수
state value를 최대화 하면서 행동을 수행해 나가고 싶음

-**Action-value function:state-action 쌍의 가치함수
-st에서 at를 수행한 뒤,지 속적으로 action을 수행해 sT에 도달했을때,discount facor를 고려한 미래 reward 총합
Q-value라 부른다:optimal action-value function(최적의 reward총합)

Value function 구하는 방법
Dynamic Programming(DP)-동적계획법
-최적화 분야 방법론 중 하나
-데이터가 많을 수록 계산량이 폭발하여 현실적으로 사용하기 힘듬
Reinforcement Learning(RL)-강화학습
-최적해를 근사하도록 가치 함수를 학습
-머신러닝 3분류 중 하나

강화학습이란
-연속적 의사결정 문제를 풀기 위한 머신러닝 기법
-(State, Action, Reward, Next state)->training data
-요소:Time(이산적), st, at, rt+1

transition(st, at, st+1, at+1...)
episode:싸이클(s1,a1,r2,s2)/a2....
-agent의 목표: 매st마다 미래 리워드 총합을 최대화 하는 at수행
-RL의 목표:agent의 목표를 만족하도록 학습시킴
-강화학습의 철학->Approximation(근사)
-Exploration
-Exploitaion

왜 지도학습보단 강화학습일까?
-현실에선 고급 데이터 구하기 힘드니 환경만 세팅해줘서 학습시킴
-연속적 의사결정 문제의 속성을 가진 문제를 해결하고자 할때
-환경 구축하여 데이터를 생성할 수 있을 때

선택연산

-교차에 쓰이는 두 개의 부모해를 고르기 위한 연산
-선택압을 이용하여 해의 선택 확률을 조절 할 수 있음
*선택압:우수한 해들과 열등한 해들 사이의 적합도 차이(높을 수록 exploit/낮을 수록 explore)
*적합도: 풀고자 하는 문제에 주어진 해가 적합한 정도->평가

품질 비례 룰렛휠 선택
-각 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절함
-해집단 내의 i번째 해의 적합도 fi는 다음과 같이 계산됨
fi=(Cw-Ci)+(Cw-Cb)/(k-1),k>1
Cw:해집단 내에서 가장 나쁜 해의 비용
Cb:해집단 내에서 가장 좋은 해의 비용
Ci:해의 i의 비용
k를 높이면 선택압이 높아짐->우수한 해가 선택될 확률과 열등한 해가 선택될 확률의 차이가 커짐

-각 염색체는 룰렛휠 상에 자신의 적합도 만큼의 공간을 배정 받음
-대부분의 경우 해집단에서 가장 좋은 해와 나쁜 해의 품질의 차이가 굉장히 크기 때문에, k를 사용하지 않고 해의 품질을 그대로 적합도로 사용하면 나쁜 해들의 선택 기회가 박탈됨->엄청나게 큰 선택압을 주어 해의 다양성을 급속히 떨어트리는 결과를 초래함


토너먼트 선택
-편해서 가장 많이 사용
-두개의 염색체를 임의로 선택하여 0과 1 사이의 난수를 발생시켜서, 이 값이 t보다 작으면 두 염색체 중 품질이 좋은 것을 선택하고 그렇지 않으면 품질이 나쁜 것을 선택
-t는 파라미터화 할 수 있는 값으로, t 값이 높을 수록 선택압이 높아짐
-t가 0.5 근처이거나 이보다 작은 것은 비합리적임
-일반적으로는 2의k승개의 염색체를 선택한 다음 이들을 토너먼트 형식으로 걸러내어 마지막으로 남은 것을 선택하는 방법도 존재(k가 크면 선택압이 높아짐)

순위 기반 선택
-간격은 같게 해주겠다
-품질 비례 선택에서는 k값을 조정함으로써 좋은 품질과 나쁜 품질의 해들의 적합도 차이의 지나친 증가를 막을 수 있음/다만 해들의 적합도 분포는 조절할 수 없음
-순위 기반 선택은 해집단 내의 해들을 품질 순으로 '순위'를 매긴 다음 가장 좋은 해부터 일차 함수적으로 적합도를 배정함
-n개의 염색체 중 i번째 순위를 가진 염색체의 적합도는 다음과 같이 계산됨/
fi-max+(i-1)*(min-max)/(n-1)/이 식에서 max와 min의 값 차이를 바꿈으로써 선택압을 조절할 수 있음
-해들의 적합도는 max와 min 사이에서 균일한 간격으로 분포하게 됨

교차연산

-유전 알고리즘의 대표적인 연산이며, 연산 중 가장 다양한 대안이 존재함
-선택연산을 통해 선택된 두개의 해를 부분 결합하여 새로운 해를 만들어냄
-해의 표현은 교차 연산과 관계되어 있을 때만 의미가 있음
  -A라는 방법으로 해를 표현했는데 교차 연산에서 이름 바꾸어 사용한다면 염색체가 A라는 방법으로 표현되었다고 할 수 없음
-가장 대표적인 일점교차 가 있음(자르는 방법은 n-1개)

산술적 교차 연산
-거의 사용하지 않는다
-실수 염색체를 사용하는 경우에 사용할 수 있는 교차 연산
-염색체의 각 위치에 대해 두 부모 염색체의 두 유전자 값의 평균을 구해 자식해의 해당 위치로 배정함
-산술적 교차는 수의 '크기'라는 개념을 교차 연산에 사용한다는 점에서 매력있는 연산임
-하지만, 산술 평균을 지향하므로 매우 빠른 수렴을 보이는 경향이 있음->변이 등을 적절히 조절하여 설익은 수렴에 이르지 않도록 유의해야 함

TSP와 GA
chromosome 표현(1)
-위치 기반 표현: 유전자의 위치가 해당 유전자의 속성을 결정함
-순서 기반 표현: 인접한 유전자의 값들이 무엇인지 중요함

chromosome 표현(2)
-순서 기반 표현:이해하기 쉽고 밀접한 관계를 갖는 도시들이 염색체에 가까운 위치에 자리하여 교차 연산시 중요한 스키마의 생존 확률 증가
-위치 기반표현: 하나의 해는 단 하나의 염색체에 대응됨/위치i는 다음도시j의 다음 방문도시를 나타냄


싸이클 교차-TSP와 같이 염색체가 순열로 표현되는 경우 적용 가능한 교차 연산
-중복x/빠뜨리기x
-그림보기

순서교차
-싸이클 교차와 마찬가지로 염색체 순열로 표시되는 경우 사용될 수 있는 교차연산
-그림

PMX
-그림

변이연산

-부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산
-교차 연산이 만들어 놓은 자식해를 미소하게 변형하여 새로운 해를 만들어 내는 연산
-전형적인 변이 연산은 각각의 유전자에 대해[0,1) 범위의 난수를 생성하여 미리 정한 임의의 임계값 미만의 수가 나오면 해당 유전자를 임의로 변형시키고 그 이상의 수가 나오면 변형하지 않음
-전형적인 임계값으로 0.015, .0.01등이 있는데, 문제의 성격과 유전 알고리즘의 다른 연산들의 종류에 따라 변할 수 있음
-변이 연산은 임의로 일어나므로 변이는 절대적인 비율로 해의 품질을 저하시킴
-변이로 잘못만들어진 유전자는 시간이 흐르면서 사라지고 가끔 발생하는 성공적인 변이는 해집단의 품질을 향상시키는데 기여함
-변이의 확률을 높이면 다양한 해를 생성할 수 있으므로 유전 알고리즘의 역동성은 늘어나지만 해집단의 수렴성이 떨어져 알고리즘의 수행시간이 길어지고 개선 속도가 느려짐


전통적인 변이
-염색체를 2진수 형태로 바꾸어 변이를 수행
-변이 연산을 수행할 때는 염색체의 구조가 문제의 정의 혹은 제약을 위반하지 않는지 고려해야 함

cut mutataion
-염색체가 순열로 표시되는 경우 사용될 수 있는 변이 연산


inverse mutation
exchange mutation
scramble mutation(임의)

대치연산

-교차와 변이 연산으로 새로운 해를 반든 후에 이를 해집단 내의 어떤 해와 대치할지 결정하는 연산
-한 세대에서 만들어지는 해의 개수 k는 해집단에서 대치되는 해의 개수이기도 함-세대차:k/n

세대형 유전 알고리즘
-대다수 물갈이라 대치 연산에 큰 고민을 할 필요가 없음

안정 상태 유전 알고리즘
-세대차가 1/n에 가까운 유전 알고리즘, 새로운 해가 생기자마자 해집단에 넣어주는방식
-해집단을 빨리 수렴시키는 경향이 있는 대신 설익은 수렴의 가능성도 큼
-한 개 또는 소수의 해가 생기는 즉시 해집단 내의 해와 대치되므로 대치될 대상을 고르는 것이 매우 중요함
방법(1)엘리티즘
방법(2)두 부모 해 중 품질이 나쁜 해와 대치하는 방법
방법(3)해집단 전체를 비교하여 자신과 가장 가까운 해를 대치하는 방법

뻐꾸기 번식

-Levy flight
해당 지점 주위에서 맴돌다가 일정 시간 이후에 멀리 떨어진 지점을 이동하는패턴이 반복됨
exploitation:짧은 이동
exploration:긴 이동

pso

-물고기나 새들이 군집을 지어 이동하는 패턴에서 착안된 메타유리스틱 알고리즘
-최초로 연구되었을 때는 사회적인 행동을 시뮬레이션 하기 위해 개발되었음
-유전알고리즘과 다르게 해의 표현이 연속적인 형태일때 적합함
-식-그림

-pso는 자신 교차가 없으니 대체가 없다

w:입자의 속도에 대한 가중치
c1:자신의 최고 위치에 대한 가중치
c2:집단의 최고 위치에 대한 가중치
r1,r2:0과1 사이의 난수
위치 업데이트 식:그림



w이 증가하면->움직임 활발함
c1이 감소하면 exploration이 감소->입자들이 수렴함
c2가 증가하면 exploitaion->개인 행동에 치중

NP-hard Problem

TSP
-하나의 도시에서부터 시작해서 모든 도시를 한 번씩만 방문하여 다시 시작점을 돌아오는 최단 거리를 구하기
-열거말고는 방법이 존재하지 않음(ex 70개 도시(70-1)!/2)
-고유한 구조 때문에 효율적인 알고리즘이 존재하지 않음
-이런 문제들 중 한 문제라도 효율적을 풀 수 있으면, 다른 모든 문제들도 풀 수 있음
-이런 문제들을 NP-hard문제라고 한다


serach algorithm
-Brute Force seach:어떤 주어진 문제를 해결하기 위해 정해진 규칙을 위반하지 않는 모든 규칙을 나열
-dynamic programming

np-hard problem
-어떤 문제가 주어지면 그 문제가 np-hard문제인지 판단이 필요
-맞다면 정확한 최적해를 구하는 알고리즘을 추구하는 것은 시간 낭비
-그렇다면 해를 얻는것은 불가능?->no->근사해
-데이터가 특별한 구조를 가지고 있어서 해법이 존재할 수도 있음
-최적해는 아니지만 근사해를 효율적으로 구하는 방법이 존재함


knapsack problem
-여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제->수리적 모형

T최소화
-spt/edd/slack 다 안되는 경우도 있다

->너무 어렵다 보니 메타휴리스틱 알고리즘이 나왔다
metaheuristic

정의
▪ 컴퓨터 과학 및 수학적 최적화에서 메타휴리스틱은 다음을 수행하도록 설계된 상위 수준 절차 또는 휴리스틱
문제에 대해 "충분"히 좋은 솔루션을 제공할 수 있는 "경험적 방법"(부분 검색 알고리즘)을 찾고 생성하거나 선택합니다.
특히 불완전하거나 "불완전한 정보" 또는 "제한된 계산 용량"으로 인해 최적화 문제가 발생합니다.
메타휴리스틱스는 너무 커서 완전히 샘플링할 수 없는 솔루션 세트를 샘플링합니다.

속성
▪ 최적화 알고리즘과 비교하여 메타휴리스틱은 전역적으로 최적의 솔루션을 보장하지 "않는다."
▪ 메타휴리스틱으로 찾은 솔루션은 생성된 "무작위 변수 세트에 따라 달라진다."
▪ 조합 최적화에서는 실현 가능한 솔루션의 큰 집합을 검색함으로써 메타휴리스틱이 종종 좋은 점을 찾을 수 있다.
최적화 알고리즘, 반복 방법 또는 간단한 경험적 방법보다 "계산 노력이 덜 드는 솔루션"




메타휴리스틱 예시들
-Genetic algorithm(popolation, evolutionary algorithm, naturally inspired)
-Tabu seach(trajectory, short time memory)
-cuckoo seach(popolation, evolutinonary algorithm, naturally inspired, levy flights)


진화 알고리즘
-생물의 진화과정을 문제 해결 과정에 적용한 알고리즘
-세대를 거듭할 수록 우수한 성능의 해는 살아남고, 열등한 성능의 해는 도태됨(하나의 해가 하나의 개체에 대응됨)
-해공간이 넓고 복잡한 문제에서 우수한 해를 탐색하기 위해 사용됨


GA
-근간이 되는 알고리즘
-집단 유전학의 개체 진화 원리를 이용하여 해 공간을 탐색하는 방법
-집단 유전학의 개체 진화 원리를 이용하는 solution sapce search 방법
-key features
적자생존/교차연산/돌연변이/집단(population)/대체/평가
-염색체:임의의 해를 GA가 이해할 수 있는 형태로 표현한 것/해/solution
-population(해집단):정해진 수로 운영되는 염색채들의 집단
-gene(유전자):염색체의 각 인자
-generation:GA의 하나의 루프


구조
(1)initalization
-n개의 초기 염색체 집단 랜덤으로 생성
-문제에 맞게 알고리즘들 이용
(2)evaluation and selection
-평가하고 부모 고르기
-각 해의 성능을 평가
-정의한 문제의 목적함수에 따른 성능을 계산
(3)crossover
-유전자 수는 같지만 적당한 부분만 교차로 받을 수 있다
-exploitation
-두해의 특징을 부분 결합하여 하나의 새로운 해를 만드는 연산
-두 부모해의 동일한 위치에 자름선을 정한 후, 각 부모해로부터 한 부분씩 가져와 합치면 새로운 해가 생성됨
(4)mutation
-랜덤으로 부모에게 없는 유전자를 수정해봄
-exploration
-해를 임의로 변형시키는 연산
-교차와 달리 부모해에 없는 속성을 도입하여 해의 다양성을 높이는 역할
-대부분 해의 품질이 낮아지는 결과로 이어짐
(5)replacement
-못하는 애들은 없애고 잘하는 대들을 복제
-해집단의 일부가 새로운 해로 대체됨(도태와 생존을 위해)
-교차와 돌연변이와 연관되어서 결정해야 함
-해를 대체하지 않고 특정 비율만큼만 생존시키는 방식도 존재


염색체 표현
-모든 해는 염색체로 표현되어야 함
-전형적인 유전 알고리즘은 해를 이진 스트링 모양의 염색체로 표현함(01010001)
-정수를 해로 삼을 때 이진수로 나타내면 자연스럽게 이진수로 표현 가능

스키마
-패턴
-임의의 염색체는 많은 부분적 패턴을 포함하고 있음
-1101은 16개의 패턴이 포함됨 1***/****/1*01
-유전 알고리즘은 작은 스키마들이 결합하여 점점 더 큰 스키마를 이루어가는 과정
초기 단계는 해의 품질은 좋지 않음
-그러나 이런 염색체들 속에 나중에 좋은 염색체를 구성할 부분 패턴(스키마)가 숨어있음
-작은 스키마에는 존재하지 않는 특성이 큰 스키마에서 창발하는 것이 유전 알고리즘의 중요한 특징

스케줄:어떤 것이 언제 일어나기로 되어 있는 지 알려줌
스케줄링: 스케쥴을 생성하는 프로세스/가지고 있는 자원을 어떤 과업을 수행하기 위해 시간에 따라서 활당하자 /일상에서 자원이 한정되어 있기에 스케쥴링은 필수적

제조업에서 스케쥴링이란
-자원: 기계
-업무: 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(잡샵 스케줄링)
▪ 작업 흐름이 단방향이 아닙니다.
▪ 작업의 첫 번째 작업만 수행하는 초기 머신도 없고, 작업의 마지막 작업만 수행하는 터미널 머신도 없습니다.
▪ 작업 𝑖의 작업 𝑗에는 기계 𝑘이 필요함을 나타내기 위해 세 개의 기호(𝑖,𝑗, 𝑘)를 사용하여 작업을 설명합니다.

인공지능
-함수(머신러닝)
-인간의 학습능력,지각능력 등을 컴퓨터 프로그램을 실현한 기술
-컴퓨터의 동작이 지적이고 상황에 따라 적절히 변하며 안정적이길 원함

머신러닝
-데이터를 이용한 모델링 기법(수리적 모델링이 어려운 문제를 주로 적용)
-인식 관련 정의가 어려운 문제들

learning problem
-사람이 할 수 있는 특정한 작업을 수행하는 완벽한 알고리즘을 설계는 사실상 불가능
-그럴싸하게 도출하는 알고리즘을 찾을 수 있다고 하더라도,, 이외의 다른 모든 작업마다 그럴싸한 알고리즘을 설계하는데 과도한 시간과 비용이 소모됨
->예시(데이터)에 기반한 학습의 필요성
-생성형 ai/강화학습/노래 알고리즘

머신러닝의 핵심요소
(1)데이터(example과 label) 가장 중요하다
-규칙을 알려주지 않고 데이터만 넣어준다
(2)러닝 모델과 러닝 알고리즘
러닝모델:예시를 입력으로 받아 예측 레이블을 출력하는 함수
러닝 알고리즘:예측 정확성이 높아지는 방향으로 러닝 모델을 개선하는 알고리즘
(3)요인 추출
러닝 모델의 예측 정확도를 보다 효과적이고 효율적으로 향상시키기 위해, 기존의 예시로부터 새로운 요인을 추출하여 이를 러닝 모델의 입력값으로 대신사용하는 것
-정답은 없다


-주어진 데이터 값과 함수가 예측한 값의 차이를 나타내는 손실함수를 감소시키는 것이 학습의 목적
-데이터를 통해 경험적 러닝이 되는 중요요소(데이터/패턴=함수/수학적으로 해결할 수 없는 문제)
-국지해가 아닌 전역최적해를 찾아야함


머신러닝의 세가지 분류
-지도학습
분류/회귀

-분류
cofusion matrix
-관심있는 값이 중심이 되어 positive가 된다(ex 오류에 관심이 있으면 오류가 positive)

precision
recall
두개의 조화평균:F1score높게 나와야 좋다/못하는 쪽으로 가중치

모델의 데이터 세팅
training-모델의 파라미터 정하기 위해
validation->overfititing 방지
test-최종 성능을 평가하지 앟기 위해 사용


-비지도 학습->정답이 없을 때 ngiht도출
군집화
연관분석


-강화학습
나중에 더 큰 상을 위해 희생한다-순차적 의사결정/감독 없이 오직 상으로만 관리

인공신경망
특징
-예를 통한 학습
-일반화:학습되지 않은 입력에도 올바른 결과를 출력
-연상기억: 새로운 입력, 일부 유실된 정보->유사한 출력
-결함 허용성->병렬
-기본작업:학습-신경망의 연결가중치 조정/재생: 학습된 가중치와 입력벡터와의 거리 계산하여 가장 가까운 클래스로 분류

입력은 다수 출력은 하나
층이 쌓일수록 비선형이 커진다
선형분리성의 문제로 다층 퍼셉트론 사용(다층 퍼셉트론 및 오류역적파 알고리즘의 기반 모델)

딥러닝:은닉층이 2개 이상
아주 많은 데이터와 아주 오랜 시간의 최적화를 통해 데이터 학습/인간의 입력이 아닌 컴퓨터가 학습
특징
다층구조
문제해결 과정을 학습을 통해 자동화분산 표현/정보처리

모델의 역사
-하드웨어(GPU)
-빅데이터 출현(대량의 데이터 확보 가능)
-획기적 알고리즘의 발전
-개발 환경의 진화(클라우드/공개 소프트웨어..등등)

지능형 제어시습템

제어 자동화

산업혁명4.0은 기계와 사람, 서비스가 상호 연결되는 지능형 생산체계
기계의 지능화와 자율제어실현

제조인공지능
-설비 지능화-빅데이터 분석을 통해 언제 고장나는지 예측하여 필요한 경우 조치(계획보전->예지보전)
-공정 지능화-인공지능 기반 공정 제어-전체 공정의 최적화,공정 품질 향상
-검사 지능화-결함 유형 분류 자동화, 정확도 향상
-자재 및 물류 지능화-실시간 제조 상황 판단, 자재물류 최적 제어

통계

1.확률
동시발생개념:주사위

상대빈도개념:횟수

주관적 확률 개념

확률변수:0~1:통계적 사건의 결과를 실수로 변환
확률분포:일정한 확률분포(패턴)을 가진다는가정

이산분포:정수/이항분포,포아송분포,기하분포->확률질량함수
연속분포:실수/정규분포/지수분포->확률밀도함수

확률질량함수:이산확률변수가 특정한 값을 취할 확률
-X-는 정수
-합은 1
-확률은 0이상
-유한개의 확률변수

확률밀도함수
-적분 필요
-한점에 대응되는 확률을 구할 수 없음=p(x=x)=0
-특정 구간에 대하여
-무한개의 확률변수

대표값
산포도-분산=정보의 양

시스템-모델
모집단-표본

표본평균의 분포->정규분포

중심극한의정리

가설:경험적으로 또는 논리적으로 검정되는 조건 또는 명제-귀납적+연역적

귀무가설:품질관리 측면에서는 기각되지 않길 바람
대립가설:신제품 입장에서는 기각되길 바람

통계적 가설검정의 절차
1가설설정
2유의수준(1종오류를 범할 확률)과 임계치 결정
3.귀무가설의 채택영역과 기각영역의 결정
4통계량 계산
5통계량과 임계치의 비교 및 결론

유의수준0.1~0.01 사이면 2종오류 발생확률이 있을 수 있다

품질경영
전통적 품질관리(QC)-
-사후적 좋은 품질 만들어지는지 검사 및 관리
현대적 품질경영(QM)
-소비자 또는 사용자 중심
-사전적 계획

품질의 의미
전통-사전에 정의된 규격에 적함/생산자 입장
현대-고객 및 이해관계자들의 요구사항을 충족/소비자 관점+생산자 관점

제품/서비스 수명주기 단계
-요구품질:고객의 요구를 얼마나 잘 인식하고 있는지를 나타내는 품질
-설계품질: 설계가 수행하기에 적합한지 나타내는 품질
-제조품질: 제조된 제품이 설계기준과 어느 정도 일치하는지
-사용품질:고객이 원하는 목적과 용도에 제품이 얼마나 적합하는지

품질경영의 목적
-품질비용의 최소화(예방비용, 평가비용, 실패비용)



품질경영의 효과
-제품자체의 품질 향상효과
-내부시스템의 품질 향상 효과-재작업 및 정체시간의 감소 효과/재고 감소

품질검사의 분류
-전수검사(머신)
-파괴검사(마네킹으로 안전검사)
-소비자 의견 조사(설문조사)
-표본추출검사(반도체)

공정관리도
배경:표본추출 검사의 한계->불량 판정은 가능 하지만 원인 추출은 불가능
원인: 품질문제의 근본 원인-> 품질변동 또는 산포현상
-우연원인
-이상원인->통제가 가능한 분명한 요인
기법: 공정관리도->이상원인을 발견하여 공정을 관리상태로 유지하기 위한 기법

중심선 관리상한선 하향선

관리도 유형
(1)변량관리도
특성치-연속적이고 정량적인 지표(제품 크기, 길이..)
관리도 종류-평균 관리도/범위 관리도/평균-범위 관리도

(2)속성관리도
특성치-불량품의 빈도와 같은 이산적 지표(오타의 수, 섬유 한 롤의 결점 수)
관리도 종류-불량품 관리도(불량의 비율)/결점수 관리도(단위 크기당 결점 수)

1. 생산성과 산업혁명

1-1생산성의 문제
생산성의 고려-애덤스미스->자유경쟁/분업...
생산성 향상의 개념: 예전에는 얼마 정도 투입해서 업무를 완성했다면 지금은 얼마정도 생산요소 투입
정보기술 자동화기술 운영기술 모두 중요

1-2 산업혁명
-농경사회->(공업화)->산업사회
-주요계기: 200년 전 영국에서 시작된 산업혁명(증기기관,전기)
-산업혁명:증기기관-도시의 진화: 전기-3차 산업혁명: 컴퓨터-4차 산업혁명:인공지능
1-3 4차 산업혁명
iot cps ai를 핵심 기술로 4차산업 발생->스마트공장이 핵심적인 역활을 할것으로 본다

CPS 최적의 제어 가능하는 기술=사이버세계와 물리세계가 동기화되게 하는 기술

2. 산업환경과 제조시스템의 변화

2-1 제조환경의 변화
-초고령화->제조업 생산인구 급감->자동화 필수
-제조분야에 대한 업무기피 심화->해외이전
-그럼에도 리쇼어링 분위기 확산(인건비가 싼 국가로 생산기지를이전했던 기업을 다시 국내로 불러들이는 정책)
-대량맞춤형->개인화를 통한 다품종소량 생산

2-2 생산관리/제조혁신 방법론의 발전
분업->과학적관리(테일러)->연속적 조립생산(포드 컨베이어 벨트)->통계적품질관리와 경영과학->린생산시스템->유연생산시스템->글로벌 경쟁시대

-과학적 관리(제조혁신의 시초): "시간 연구"와 "동작연구"를 기초로 노동의 표준량 산정+임금 지급 방법 연구/솔선과 격려의 경영/과학=객관적->현대사회에서는 데이터가 중요

-포드생산시스템: 컨베이어 시스템을 이용한 "이동조립작업"과 대량생산 그리고 혁신적 "인적자원경영"
3S 대량생산의 일반원칙->작업의 단순화/부품 표준화/기계와 공구 전문화
작업의 원칙-허리 굽히지 않기/한발이라도 움직이지 않기


2-3 제조혁신의 원동력
-생산시스템: 셀 생산시스템(컨베이어+유연성)/gt 공정보단 제품 중심/jit 다기능 공화 기계설비의 합리적 배치(u자형)/유연생산시스템(fms) 순서 없이 생산/재구성형생산시스템(rms) 재구성이 가능한 기계들과 제어장치

-정보시스템: erp 경영 프로세스들을 통합적으로 연계해 관리/ scm 공급사슬의 통합적 관점에서 관리/crm 판매실적 등 고객과의 관계 데이터 분석/mes 현장의 활동을 관리/ plm 제품 설계부터 최종생산까지 이르는 전체과정을 일관적으로 관리

3. 스마트공장의 개념과 사례

3-1 스마트공장의 정의, 목표 및 요건
-스마트 공장: 비즈니스 전반에 "최적화"를 가능하게 하며 유연한 운영을 통합하고 개방을 통해 "고객과 소통하는 공장"/비즈니스 프로세스의 정보화 및 생산시스템의 "자동화=지능화"를 실현하는 공장
-스마트공장 목표: 생산시스템을 "지능화 유연화 최적화 효율화"를 통해 고객요구에 능동적으로 대응할 수 있는 제조기업을 구현하는 것
-요건 (4m1e: men, machinery, material, method enviroment)의 디지털화 지능화 통합 엔지니어링 지식의 창출 타 스마트 시스템과의 연결


3-2 스마트공장의 범위
-모든 제조 관련 과정을 포함
-일반과정+ICT 기술 및 기업정보시스템의 적용도 포함

3-3 스마트 제조 기술

8대 스마트 제조기술

생산시스템혁신기술
스마트센서/사이버물리시스템/3D프린팅/에너지절감 기술

정보통신기반기술
사물인터넷/클라우드/빅데이터/홀로그램

-사물인터넷
-빅데이터(정/비정)
-클라우드
-인공지능