스케쥴링 최적화 프로젝트

소개

jobshop scheduling 이란 계획된 생산량을 최소의 비용과 시간으로 소화하기 위한 각 기계에 대한 작업의 순서결정과, 부하(負荷)의 배분, 또는 인풋(input) ·아웃풋(output) 규칙의 선택이 이루어진다. 경험이나 시뮬레이션(simulation)에 의한 계획이 시행되고 있으나 최적계획(最適計畵)의 충분한 이론은 아직 확립되어 있지 않다.
위에서도 알수 있듯이,아직 jobshop scheduling은 충분한 이론이 확립되지 않은상태이다.바로 우리가 그것을 확립시키기위해 노력해야한다.

목차

1. Jobshop Scheduling 3
1) 서론 3
2) Coding 4
3) Coding concept for scheduling rules 7
4) Scheduling rules 9
 SPT(Shortest Processing Time) 12
 LTWK(Least Total Work) 13
 LWKR(Least Work Remaining) 16
 SRM(Shortest Remaining Time) 17
 SPT/TWK 18
 SPT/TWKR 19
 LPT(Longest Processing Time) 20
 MTWK(Most Total Work) 21
 MWKR(Most Work Remaining) 24
 LRM(Longest Remaining Work) 25
 LPT/TWK 26
 LPT/TWKR 27
 FOPR( Fewest Number of Operations Remaining ) 28
 MPOR( Most Number Of Operations Remaining ) 29
5) 스케줄링 룰에 대한 분석 및 접근. 29
6) Conclusion 39
2. Crew Scheduling 40
1) Pattern 생성 40
2) 생성된 패턴중 최적값 찾기 55
3) 조종사 할당 57
4) conclusion 60
<Appendix: 프로젝트의 원 문제>

본문내용

3. 해법절차 2단계(조종사 할당)
 2단계에서 생성되어 선택된 승무경로를 조합함으로 4주간 동안의 조종사의 운항스케줄을 작성하는 단계이다. 좋은 운항스케줄은 조종사별로 할당되는 경로에 대해 승무시간이 공평하게 배당하는 것이다. 접근방법은 여러 가지가 있고 이 또한 본 해법을 찾는 과정에서 개발해야 하는 부분이다. 본 문제는 81명의 기장에 대해서만 운항스케줄을 작성하는 것으로 한다.
 우선 가능한 모든 운항스케줄을 생성한다. 1주일간의 생성/선택된 승무경로가 40개라면 4주간의 운항가능스케줄은 40*40*40*40=2,560,000개에 이른다. 각 운항스케줄별로 1명 또는 2명의 조종사가 필요한 것을 고려하여 81명의 기장에 대한 운항스케줄을 선택한다. 1주간의 단위운항구간의 데이터를 통해 4주간 평균 승무시간을 계산할 수 있고 따라서 평균승무시간에 가까운 운항스케줄을 선택하는 과정을 실행한다. 이때 이 과정을 1단계에서 사용한 수리모델을 적절하게 변형하여 사용할 수 있다. 즉, 각 운항스케줄에 대해 승무시간과 평균시간의 차이를 각 운항스케줄의 비용으로 가정하여 적용할 수 있다. 그러나 수백만개의 모든 운항 가능 스케줄을 대상으로 수리모델의 해를 구할 수는 없기 때문에 이중에서 일정조건을 만족시키는 운항스케줄의 일부분을 골라서 수리모델을 적용하여 해를 구하는 것도 한 방법이다.

참고자료

· 출처 : 두산세계대백과 EnCyber