작업군 및 작업순서에 종속적인 작업 준비시간을 고려한 개별공정 일정계획 알고리즘: 총 작업 군 흐름시간의 최소화

Abstract

This thesis considers job shop scheduling in which jobs are grouped into job families, but they are processed individually. As an extension of the previous study, we consider sequence-dependent setups, i.e., setup times depend on the type of job just completed and the next job to be processed. This type of job shop scheduling can be found in various manufacturing systems, especially in remanufacturing systems with disassembly, reprocessing and reassembly shops. In other words, the reprocessing shop can be regarded as the job shop with job families since it performs the operations required to bring parts or sub-assemblies disassembled back to like-new conditions before reassembling them. To minimize the deviations of the job completion times within each job family, we consider the objective of minimizing the total family flow time. Here, the family flow time implies the maximum among the completion times of the jobs within a job family. To describe the problem mathematically, a mixed integer programming model is suggested, and then, due to the complexity of the problem, we suggest two iterated greedy algorithms with different neighborhood generation methods. Computational experiments were done using benchmark instances, and the results are reported.|본 연구는 조립 공정을 위한 작업군이 있는 개별공정에 대한 일정계획 문제를 다루고 있다. 이전 연구의 확장으로서 본 연구에서는 작업순서에 종속적인 작업 준비시간 또한 고려했다. 이러한 유형의 개별공정은 다양한 제조시스템에서 찾아볼 수 있다. 특히 사용된 제품을 분리 했을 때나, 수명이 다한 제품의 부속품들을 처리하는 재제조 작업장에서 유용하다. 본 논문의 주요 결정변수로는 각각의 기계에서의 작업순서 결정이며, 이것은 기본적으로 전형적인 개별공정의 일정관리 문제와 같다. 또한, 각 작업군 내의 작업 완료시간에 대한 편차를 줄이기 위하여, 최대 작업군 체류시간의 합을 최소화 시키는 것을 목적으로 한다. 본 연구를 좀 더 명확히 하기 위하여 정수계획 모형이 사용되었다. 문제의 복잡도로 인하여 이웃해 생성기법을 달리한 두 가지의 Iterated Greedy 알고리듬을 사용하였다. 마지막으로 제안된 알고리듬들의 성능 평가를 위하여 벤치마크 문제를 본 문제에 맞게 수정하여 계산실험을 수행하였으며, 실험 후 결과에 대하여 보고하였다.; This thesis considers job shop scheduling in which jobs are grouped into job families, but they are processed individually. As an extension of the previous study, we consider sequence-dependent setups, i.e., setup times depend on the type of job just completed and the next job to be processed. This type of job shop scheduling can be found in various manufacturing systems, especially in remanufacturing systems with disassembly, reprocessing and reassembly shops. In other words, the reprocessing shop can be regarded as the job shop with job families since it performs the operations required to bring parts or sub-assemblies disassembled back to like-new conditions before reassembling them. To minimize the deviations of the job completion times within each job family, we consider the objective of minimizing the total family flow time. Here, the family flow time implies the maximum among the completion times of the jobs within a job family. To describe the problem mathematically, a mixed integer programming model is suggested, and then, due to the complexity of the problem, we suggest two iterated greedy algorithms with different neighborhood generation methods. Computational experiments were done using benchmark instances, and the results are reported.