Job Shop Scheduling에 대한 Review

Job Shop Scheduling에 대한 Review

0. 참고 출처

Chaudhry, Imran Ali, and Abid Ali Khan. "A research survey: review of flexible job shop scheduling techniques." International Transactions in Operational Research 23.3 (2016): 551-591.

 

 

.

1. Job shop 이란

- 소량, 혹은 중간 수준의 양을 가진, 다양한 제품들을 생산하는 단속적 생산시스템.

- 다양한 제품군에 대응해야 하므로, CNC와 같은 범용 기계 사용

- 여러 제품군이 제품 별 상이한 공정계획, setup 등에 기반하여 운용이 되기 때문에 생산 효율 제고 위해서는 정밀한 생산계획 요구

 

 

.

2. Job shop scheduling 문제의 정의

- Job shop scheduling 문제는 Job, operation, machine 간 관계를 아래와 같이 설정하고, 개별 Job들을 수행할 수 있도록 구성 operation을 machine에 할당해주는 문제라고 정의할 수 있음.

Job shop scheduling 문제 정의

 

- 해당 문제 정의에 따라 수행 시, 아래와 같은 결과물 (예시) 이 도출됨. 즉, 시간대별로 개별 기기마다 어떤 job 의 operation 들을 수행하는지 표기가 되어야 함.

job shop scheduling 문제 결과 (출처: google developers)

 

 

.

3. Job shop scheduling에서 일반적으로 가정(제한)하는 사항

- Job shop scheduling의 경우, 학문적 관점에서 문제를 풀다보니 문제 복잡성의 제한을 위해 대개 아래와 같은 가정사항을 설정하며, 실전 적용 시에는 해당 사항들에 대해 handling할 수 있도록 조치가 필요.

- 크게 파랑색 글귀로 가정 사항을 제시하였으며, 가정 사항 밑에 -> 부분을 추가해 , 실제 해당 가정 사항을 준수하지 않을 경우 어떤 방향으로 스케줄링 전략을 수정해야 하는지 명기.

Job shop scheduling 에서의 가정 사항 및 가정 사항 별 미준수 시 대안 전략

 

 

.

4. Job shop scheduling의 성과 지표

- 일반적으로, job shop scheduling 을 작성하는 데 있어 나올 수 있는 solution 의 개수는 셀 수 없이 많으며, 특히 수많은 대안 solution 중에서 무엇이 최적인지를 고르는 것은 더더욱 어려움. (Job shop scheduling 같은 문제 부류를 흔히 NP-hard problem 이라 부름)

- 최적의 solution을 찾는 것은 후술할  5. 장에서 수행하나, solution을 선정하는 기준은 여기서 언급. 이를 통해 solution의 선정 기준을 명세함으로써, 어떤 관점에서 최적인지를 알고리즘 작성 전에 명확화하는 것임. (모든 관점에서 최적인 해를 찾는 게 더 좋겠지마는 현실적으로도 어렵고 비효율적임.)

- 여러 지표들이 있지마는, 가장 범용적으로 활용되는 지표들은 아래와 같음.

- 최적 solution 을 선정할 때, 아래의 지표 중 하나만을 활용할 필요는 없으며 여러 지표가 동시에 활용될 수도 있음.

지표 명	설명
makespan	할당된 job이 모두 끝나는 시점
mean completion time	job 별 끝나는 시점의 평균
maximum flow time	job 별 shop floor에서 작업하는 시간을 합산하였을 때, 가장 최대 값
mean flow time	job 별 shop floor에서 작업하는 시간을 합산하였을 때, 이들의 평균 값
total tardiness	job 별 마감 기한과 실제 completion time 간 차이를 다 합산한 것
average tardiness	job 별 마감 기한과 실제 completion time 간 차이의 평균
total weighted tardiness	job 별 중요성에 따라, job 별 마감 기한과 실제 completion time 간 차이 값에 가중치를 부여하여 합산한 것
maximum lateness	job 별 마감 기한과 실제 completion time 간 차이 중 최대 값
number of tardy jobs	마감 기한보다 실제 completion time 이 늦은 job 개수
total workload of machines	machine 별 실제 가동한 시간의 합
critical machine workload	machine 중, 가장 오래 가동한 machine의 가동 시간

 

 

.

5. Job shop scheduling에 대한 다양한 접근법

- Job shop scheduling 에 적용되는 제 접근법은 아래와 같이 정리할 수 있으며, 각각의 접근법마다 활용하는 지표, 가정 사항 등은 얼마든지 자유롭게 적용 가능.

Job shop scheduling에 대한 접근법

.

번호	활용된 hybrid 기법
1	Taboo search + disjunctive graph
2	Genetic algorithm + Constraint logic programming
3	Simulated annealing + Giffler and Thompson priority rule
4	Localization approach + Genetic algorithm
5	Pareto-optimality + fuzzy system
6	Genetic algorithm + priority dispatching rule
7	Taboo search + Giffler and Thompson priority rule
8	Particle Swarm Optimization + Simulated Annealing
9	Genetic Algorithm + Local Search
10	Genetic Algorithm + heuristics
11	Taboo search + heuristics
12	Ant Colony Optimization + Taboo Search
13	Genetic Algorithm + Local Search
14	Genetic Algorithm + Local Search + Shifting Bottleneck
15	Taboo Search + Simulated Annealing
16	Genetic Algorithm + Variable neighborhood descent
17	Genetic algorithm + dispatching rule
18	Particle Swarm Optimization + Taboo Search
19	Genetic Algorithm + Ant Colony Optimization
20	Genetic Algorithm + Simulation ( Stochastic Breakdown )
21	Particle Swarm Optimization + Taboo Search
22	Genetic Algorithm + hill climbing
23	Genetic Algorithm + Variable neighborhood search
24	Genetic Algorithm + immune/entropy principle
25	Genetic algorithm + simulated annealing
26	Particle Swarm Optimization + Taboo Search
27	Simulation + Decision Support System
28	Taboo Search + Variable Neighborhood Search
29	Pareto-based Artificial Bee Colony
30	Particle Swarm Optimization + local search
31	Shuffled frog-leaping + local search

 - 보다시피 일반적으로 스케줄링 알고리즘에 관련된 문건에 한하여서는 meta-heuristic 기법이 압도적이며, 이러한 meta-heuristic 기법 외 두 개 이상의 기법을 혼재한 Hybrid 접근이 대세.

- 실제 현장 적용 시에는 현장 고유의 업무 노하우들이 존재하기 때문에 실질적으로는 heuristic 혹은 이와 meta-heuristic 알고리즘 등을 융합하여 개발.

출처: https://m.blog.naver.com/ppepajbw432/221532219346

.