작업순서 및 기계 의존적인 준비시간을 고려한 제약이 주어진 이종병렬기계의 일정계획에 관한 연구 = Scheduling of Restricted Non-identical Parallel Machine with Sequence and Machine Dependent Setup Times

다국어 초록 (Multilingual Abstract)

This paper considers a restricted non-identical parallel machine scheduling problem with sequence and machine dependent setup times. The objective of this problem is to determine the allocation of jobs and the scheduling of machines to minimize the makespan. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two meta-heuristic algorithms based on ant colony system and genetic algorithm are proposed. The performance of the proposed algorithms are evaluated using randomly generated several examples.

참고문헌 (Reference)

1 주철민, "작업투입시점과 순서의존적인 준비시간이 존재하는 병렬기계 일정계획을 위한 개선 개미군집 시스템" 대한산업공학회 35 (35): 218-225, 2009

2 Hop, N. V, "The scheduling problem of PCBs for multiple non-identical parallel machines" 158 : 577-594, 2004

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

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

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

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

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

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

9 Balin,S, "Non-identical parallel machine scheduling using genetic algorithm" 38 : 6814-6821, 2011

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

11 Agarwal, A, "Heuristics and augmented neural networks for task scheduling with non-identical machines" 175 (175): 296-317, 2006

12 Gen, M, "Genetic Algorithms and Engineering Optimization" Wiley 2000

13 Tavakkoli-Moghaddam, R, "Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints" 36 : 3224-3230, 2009

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

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

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

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

18 Yalaoui, F, "An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times" 35 (35): 183-190, 2003

19 Holland,J.H, "Adaptation in natural and artificial systems" University of Michigan Press 1975

20 Allahverdi, A., "A survey of scheduling problems with setup times and costs" 187 : 985-1032, 2008

21 Nait, T. D., "A new approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times based on linear programming" 3 : 266-274, 2003

22 Sveltana, A., "A heuristic algorithm for minimizing mean flow time with unit setups" 79 : 291-296, 2001

23 Vallada,E.and Ruiz,R, "A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times" 211 : 612-622, 2011

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