계측 관련 제약 사항을 고려한 유전 알고리즘 기반 플로우샵 스케줄링

Abstract

This paper addresses a scheduling problem aimed at minimizing makespan in a permutation flow shop with two machines and an inspection process that must be conducted at least once every certain number of outcomes from the first machine. A mathematical programming approach and a genetic algorithm, incorporating Johnson's rule and a specific mutation process, were developed to solve this problem. Johnson's rule was used to generate an initial population, while the mutation process ensured compliance with the inspection constraints. The results showed that within a computation time limit of 300 seconds, the mathematical programming approach often failed to provide optimal or feasible solutions, especially for larger job sets. For instance, when the process times of both machines were similar and the inspection time was longer, the mathematical programming approach failed to solve all 10 experiments with just 15 jobs and only had a 50% success rate for 100 jobs. In contrast, the proposed genetic algorithm solved all instances and delivered equal or superior results compared to the mathematical programming approach.