작업투입시점과 순서의존적인 준비시간이 존재하는 병렬기계 일정계획을 위한 개선 개미군집 시스템

다국어 초록 (Multilingual Abstract)

This paper considers a parallel-machine scheduling problem with job release times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines so as to minimize the weighted sum of setup times, delay times, and tardy times. A mathematical model for optimal solution is derived and a meta heuristic algorithm based on the improved ant colony system is proposed in this paper. The performance of the meta heuristic algorithm is evaluated through compare with optimal solutions using randomly generated several examples.

참고문헌 (Reference)

1 Bobrowski, P. M., "The impact of sequence dependent setup time on job shop scheduling performance" 32 : 1503-1520, 1994

2 Flynn, B. B., "The effects of setup time on output capacity in cellular manufacturing" 25 : 1761-1772, 1987

3 Dorigo, M., "The Ant System：Optimization by a Colony of Cooperating Agents" 26 : 29-41, 1996

4 Dorigo, M., "The Ant Colony Optimization Meta-heuristic, New Ideas in Optimization" McGraw-Hill 1999

5 Pinedo, M., "Scheduling theory, algorithms, and systems" Prentice-Hall 1995

6 Behnamian, J., "Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm" 36 : 9637-9644, 2009

7 Nessah, F., "New heuristics for identical parallel machine scheduling with Sequence-dependent setup times and dates" 32-41, 2005

8 Hahn, C. K., "Impact of the setup variable on capacity and inventory decisions" 13 : 91-103, 1989

9 Garey, M., "Computers and intractabilit y：A guide to the theory of NP-completeness" W. H. Freeman 1997

10 Mendes, A. S., "Comparing metaheuristic approaches for parallel machine scheduling problems" 13 : 143-154, 2002

11 Frederickson, G., "Approximation algorithm for some routing problems" 7 : 178-193, 1978

12 Shyu, S. J., "Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time" 47 : 181-193, 2004

13 Dorigo, M., "Ant colony optimization theory：A survey" 344 : 243-278, 2005

14 Solimanpur, M., "Ant colony optimization algorithm to the inner-cell layout problem in cellular manufacturing" 157 : 592-606, 2004

15 Dorigo, M., "Ant Colony System： A cooperative learning approach to the traveling salesman problem" 1 : 53-66, 1997

16 Dorigo, M., "Ant Colony Optimization：Artificial Ants as a Computational Intelligence Technique" University Libre De Bruxelles 2006

17 Bell, J. E., "An colony optimization technique for the vehicle routing problem" 18 : 41-48, 2004

18 Ying, K., "An ant colony system for permutation flow-shop sequencing" 31 : 791-801, 2004

19 Cheng, C., "A modified ant colony system for solving the traveling salesman problem with time window" 46 : 1225-1235, 2007

20 Tahar, D. N., "A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times" 99 : 63-73, 2006

21 Gharehgozli, A. H., "A fuzzy-mixed-integer goal programming mode for a parallel-machine scheduling problem with sequence- dependent setup times and relaeas dates" 25 : 853-859, 2009