In this thesis, the single machine job scheduling problem with arbitrary weights is considered and the optimal timing algorithm which is the modification of the algorithm of Garey et. al. is presented. Given a sequence, the optimal timing algorithm locates each job, one at a time. It produced the cost of a sequence. To solve the single machine job scheduling problem, Genetic Algorithm is used as a meta-heuristic. Various operators, a representation scheme of a feasible solution and reproduction rules are examined and compared. In the computational results, it is shown that N best reproduction without duplicates method and Blockwise Recombination with Uniform Crossover are better than others. With these operators, Genetic Algorithm is compared with other heuritic, INT procedure. In this comparison, Genetic Algorithm performs well.
이 논문에서는 작업마다 납기일이 서로 틀리고 조속성의 페널티율과 지연성의 페널티율 이 임의적으로 주어진 작업스케쥴링 문제를 다루었다. 이러한 형태의 문제는 "Just In Time" 생산방식에 현실적으로 적용 될 수 있는 문제이다. 먼저, 이러한 문제의 해결을 위해 작업순서가 주어졌을 때 페널티를 최소화하는 알고리즘을 제시하였다. 이 알고리즘은 Garey et. al.의 알고리즘을 임의의 페널티율을 가지는 경우를 위해 수정한 것이다. 또, 이 알고리즘은 주어진 작업순서의 총 페널티를 계산한다. 최적작업순서의 탐색에는 유전알고리즘이 사용되었다. 유전알고리즘을 스케쥴링문제에 적용하기위해 여러가지 유전 연산자와 가능해의 유전적 표현방법, 유전자 복제 방법이 개발되었다. 실험결과에서 N best reproduction without duplicates 복제법과 Uniform Crossover를 이용한 블럭단위 재결합 연산자가 다른 연산자나 복제방법에 비해 우월함을 알수 있었다. 이러한 연산자와 복제방법을 사용한 유전알고리즘을 INT 알고리즘과 비교하였는데, 이 실험에서 유전알고리즘의 성과가 좋음이 밝혀 졌다.
