Non-Identical Parallel Machine Scheduling with Sequence and Machine Dependent Setup Times Using Meta-Heuristic Algorithms

다국어 초록 (Multilingual Abstract)

This paper considers a 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 each machine to minimize 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-heuristics, genetic algorithm (GA) and a new population-based evolutionary meta-heuristic called self-evolution algorithm (SEA), are proposed. The performances of the meta-heuristic algorithms are evaluated through compare with optimal solutions 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 Pinedo, M., "Scheduling theory, algorithms, and systems" Prentice-Hall 1995

4 Pfund, M., "Scheduling jobs on parallel machines with setup times and ready times" 54 : 764-782, 2008

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

6 Cheng, R., "Parallel Machine Scheduling Problems Using Memetic Algorithms" 33 (33): 761-764, 1997

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

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

9 Gen, M., "Genetic Algorithms and Engineering Optimization" Wiley 2000

10 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

11 Garey, M., "Computers and intractability: A guide to the theory of NP-completeness" W. H. Freeman 1997

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

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

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

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

16 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

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

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

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