An Improved Genetic Algorithm for Integrated Planning and Scheduling Algorithm Considering Tool Flexibility and Tool Constraints
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper proposes an improved standard genetic algorithm (GA) of making a near optimal schedule for integrated process planning and scheduling problem (IPPS) considering tool flexibility and tool related constraints. Process planning involves the selection of operations and the allocation of resources. Scheduling, meanwhile, determines the sequence order in which operations are executed on each machine. Due to the high degree of complexity, traditionally, a sequential approach has been preferred, which determines process planning firstly and then performs scheduling independently based on the results. The two sub-problems, however, are complicatedly interrelated to each other, so the IPPS tend to solve the two problems simultaneously. Although many studies for IPPS have been conducted in the past, tool flexibility and capacity constraints are rarely considered. Various meta-heuristics, especially GA, have been applied for IPPS, but the performance is yet satisfactory. To improve solution quality against computation time in GA, we adopted three methods. First, we used a random circular queue during generation of an initial population. It can provide sufficient diversity of individuals at the beginning of GA. Second, we adopted an inferior selection to choose the parents for the crossover and mutation operations. It helps to maintain exploitation capability throughout the evolution process. Third, we employed a modification of the hybrid scheduling algorithm to decode the chromosome of the individual into a schedule, which can generate an active and non-delay schedule. The experimental results show that our proposed algorithm is superior to the current best evolutionary algorithms at most benchmark problems.
Abstract
This paper proposes an improved standard genetic algorithm (GA) of making a near optimal schedule for integrated process planning and scheduling problem (IPPS) considering tool flexibility and tool related constraints. Process planning involves the selection of operations and the allocation of resources. Scheduling, meanwhile, determines the sequence order in which operations are executed on each machine. Due to the high degree of complexity, traditionally, a sequential approach has been preferred, which determines process planning firstly and then performs scheduling independently based on the results. The two sub-problems, however, are complicatedly interrelated to each other, so the IPPS tend to solve the two problems simultaneously. Although many studies for IPPS have been conducted in the past, tool flexibility and capacity constraints are rarely considered. Various meta-heuristics, especially GA, have been applied for IPPS, but the performance is yet satisfactory. To improve solution quality against computation time in GA, we adopted three methods. First, we used a random circular queue during generation of an initial population. It can provide sufficient diversity of individuals at the beginning of GA. Second, we adopted an inferior selection to choose the parents for the crossover and mutation operations. It helps to maintain exploitation capability throughout the evolution process. Third, we employed a modification of the hybrid scheduling algorithm to decode the chromosome of the individual into a schedule, which can generate an active and non-delay schedule. The experimental results show that our proposed algorithm is superior to the current best evolutionary algorithms at most benchmark problems.
참고문헌 (25)
- Atashpaz-Gargari, E., "Imperialist competitive algorithm : An algorithm for optimization inspired by imperialistic competition", 2007 IEEE Congress on Evolutionary Computation, pp.4661~4667 (2007)
- Ausaf, M.F., "Optimization Algorithms for Integrated Process Planning and Scheduling Problem-A Survey", 5278~5283 (2014)
- Bierwirth, C., "Production scheduling and rescheduling with genetic algorithms", Evolutionary computation, 7(1), pp.1~17 (1999)
- Blanton Jr, J.L., "Multiple vehicle routing with time and capacity constraint using genetic algorithms", Proceedings of the Fifth International Conference on Genetic Algorithms, pp.452~459 (1993)
- Chaudhry, I.A., "A research survey :Review of flexible job shop scheduling techniques", International Transactions in Operational Research, 23(3), pp.551~591 (2016)
- 이상완, "유연생산시스템 환경 하에서의 동적 일정계획에 관한 연구", 산업경영시스템학회지, 27(2), pp.17~23 (2004), 한국산업경영시스템학회
- Cinar, D., "A priority-based genetic algorithm for a flexible job shop scheduling problem", Journal of Industrial and Management Optimization, 12(4), pp.1391~1415 (2016)
- Giffler, B, "Algorithms for Solving Production-Scheduling Problems", Operations Research, 8(4), pp.487~503 (1960)
- Ho, Y.-C., "Solving cell formation problems in a manufacturing environment with flexible processing and routeing capabilities", International Journal of Production Research, 34(10), pp.2901~2923 (1996)
- Kim, Y. K., "An asymmetric multileveled symbiotic evolutionary algorithm for integrated FMS scheduling", Journal of Intelligent Manufacturing, 18(6), pp.631~645 (2007)
- Kim, Y. K., "A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling", Computers & Operations Research, 30(8), pp.1151~1171 (2003)
- 이동주, "선행관계를 가진 다중프로세서 작업들의 Makespan 최소화를 위한 변형타부검색", 산업경영시스템학회지, 27(4), pp.42~48 (2004), 한국산업경영시스템학회
- Li, X., "An active learning genetic algorithm for integrated process planning and scheduling", Expert Systems with Applications, 39(8), pp.6683~6691 (2012)
- Li, X., "Mathematical modeling and evolutionary algorithmbased approach for integrated process planning and scheduling", Computers & Operations Research, 37(4), pp.656~667 (2010)
- Li, X., "An effective hybrid algorithm for integrated process planning and scheduling", International Journal of Production Economics, 126(2), pp.289~298 (2010)
- Lian, K., "Integrated process planning and scheduling using an imperialist competitive algorithm", International Journal of Production Research, 5015(15), pp.4326~4343 (2012)
- Liu, M., "An adaptive annealing genetic algorithm for the job-shop planning and scheduling problem", Expert Systems with Applications, 38(8), pp.9248~9255 (2011)
- MORAD, N., "Genetic algorithms in integrated process planning and scheduling", Journal of Intelligent Manufacturing, 10(2), pp.169~179 (1999)
- Nasr, N., "Job shop scheduling with alternative machines", International Journal of Production Research, 28(9), pp.1595~1609 (1990)
- Park, B.J., "Job Shop Scheduling with Evolutionary Algorithms", Journal of The Korean Institute of Plant Engineering, 5(2), pp.95~102 (2000)
- Petrovic, M., "Integration of process planning and scheduling using chaotic particle swarm optimization algorithm", Expert Systems with Applications, 64, pp.569~588 (2016)
- Shao, X. Y., "Integration of process planning and scheduling-A modified genetic algorithm-based approach", Journal of Computers &Operations Research, 36(6), pp.2082~2096 (2009)
- Thomalla, C. S., "Job shop scheduling with alternative process plans", International Journal of Production Economics, 74(1-3), pp.125~134 (2001)
- Zhang, L., "An object-coding genetic algorithm for integrated process planning and scheduling", European Journal of Operational Research, 244(2), pp.434~444 (2015)
- Zhang, S., "An Extended Genetic Algorithm for Distributed Integration of Fuzzy Process Planning and Scheduling", Mathematical Problems in Engineering, 2016, pp.2016~2011 (2016)