셋업을 고려한 이종병렬기계 일정계획

Abstract

This thesis studies three scheduling problems for non-identical parallel machine systems that can be easily found in small and medium sized manufacturing companies. Common features of the three problems are as follows; 1) minimizing the makespan, 2) machine dependent setup times, and 3) machine dependent processing times. For all the problems, this thesis proposes mixed integer linear programming models, and using the models, the optimal solutions for relatively small example problems can be found by a commercial optimization software. However, since all of the three problems are NP-hard and the size of a real problem is large, some heuristic algorithms including genetic algorithm to solve the practical big-size problems in a reasonable computational time are proposed for each problem. And then, to assess the performances of the algorithms, a computational experiment is conducted in each chapter. After an introduction to the non-identical parallel machine scheduling problem and literature review for the problems in chapter 1 and a brief explanation for the setup operations in chapter 2, the first problem out of the three problems is studied in chapter 3. A special feature of this problem is that the setup times are sequence dependent. For the problem, a mathematical model and four heuristic algorithms are proposed. Through a computational experiment, it is found that the heuristic algorithms show different performances as the problem characteristics are changed and some simple heuristics show better performances than genetic algorithm based heuristics for the case when the numbers of jobs and/or machines are large. A special feature of the second problem in chapter 4 is that the setup operations for all machines are performed by a single setup operator. For the problem, a mathematical model and three genetic algorithm based heuristics are proposed. From a computational experiment, it is found that some heuristic algorithms show very good performances. Lastly, the third problem, in which the machine dependent setup time of each job can be divided into internal and external setup times, is studied in chaper 5. The internal setup refers to those setup actions that inevitably require that the machine be stopped, and the external setup refers to actions that can be taken while the machine is operating. To solve the problem, another mathematical model is developed and a genetic algorithm based heuristic is proposed. Through a computational experiment, the heuristic algorithm shows very good performances.

Keywords : non-identical parallel machine, internal and external setup, scheduling, single setup-operator, genetic algorithm