처리시간의 합 기반 에이징 효과를 갖는 tardiness를 고려한 단일기계 two 에이전트 스케줄링
Single-machine two-agent scheduling with sum-of-processing-times-based aging effects under tardiness consideration
- 발행기관 아주대학교
- 지도교수 최진영
- 발행년도 2015
- 학위수여년월 2015. 2
- 학위명 석사
- 학과 및 전공 일반대학원 산업공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000019347
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
In recent studies of scheduling, a multi-agent scheduling problem has been recognized as an important issue, where multiple decision makers perform scheduling while considering their own objectives and competing for resources. Limited scheduling resources can be efficiently utilized by a suitable solution for the multi agent scheduling problem. Meanwhile, there is another element that should be considered, namely learning and aging effect. The actual processing time in real industry can be increased or decreased by them. In recent years, multi-agent scheduling and learning/aging effect are considered simultaneously. However, they did not consider the due date. Although the due date is as important as cost, there are few studies considering the due date because of its high computational complexity. Motivated by these remarks, we consider a single-machine two-agent scheduling problem with the aging effect based on sum-of-processing-times, where one agent wants to minimize total weighted tardiness, not allowing tardy job for the other agent. We develop a branch-and-bound (B&B) algorithm and a genetic algorithm (GA). We propose dominance properties and lower bound for an efficient B&B algorithm and consider four initial populations to improve the performance of the GA. We implemented the suggested algorithms using MATLAB and performed a numerical experiment to show the superiority of them.
more목차
Table of Contents
Acknowledgement i
Abstract ii
List of tables v
List of figures vi
Chapter 1. Introduction 1
1.1 Purpose and need for research 1
1.2 Previous studies and approaches 4
1.3 Organization of thesis 8
Chapter 2. Problem definition and branch-and-bound algorithm 9
2.1 Problem definition 9
2.2 Branch-and-bound algorithm 13
Chapter 3. Genetic algorithm 22
3.1 Representation of chromosome 23
3.2 Initial population 23
3.3 Fitness function 24
3.4 Crossover operation 24
3.5 Mutation 26
3.6 Population update and termination criteria 27
Chapter 4. Numerical experiment 29
4.1 Experimental design 29
4.2 Analysis of experimental results 31
Chapter 5. Conclusion 38
Bibliography 40
Appendix A. MATLAB Code for proposed B&B algorithm and GA 46
List of tables
Table 1. A scheduling example to calculate lower bound 21
Table 2. Experimental results of B&B and GA 32
Table 3. Results of paired T-test between two GAs 36
List of figures
Figure 1. The concept of multi-agent scheduling 1
Figure 2. Complexity hierarchies of scheduling problems 4
Figure 3. Two schedules and including two adjacent jobs and 14
Figure 4. The procedure of genetic algorithm 22
Figure 5. Representation of chromosome using permutation encoding 23
Figure 6. Examples of crossover operator 25
Figure 7. Range of due dates generated by two and three parameters 30
