This thesis considers logistics scheduling problems in supply chain management. They include logistics scheduling problems for coordination between job sequencing at a production stage and job delivery at its subsequent delivery stage under supply chain environment. In the analysis, the problem complexities are characterized. For example, if the problems are proved to be solvable in polynomial time, then the associated optimal polynomial algorithms are derived. Otherwise, if the problems are NP-hard, then the associated solution properties are characterized, based on which efficient heuristic algorithms are derived.
Three logistics scheduling problems are considered in this thesis. The first problem is concerned with a logistics scheduling problem with stage-dependent inventory holding costs incorporated. In the problem, jobs are processed on a single machine and delivered by a capacitated vehicle to a single customer. The objective is to find a schedule to minimize the total weighted cost of the associated WIP inventory, finished product inventory and delivery, where inventory costs are characterized in terms of weighted flowtime and the delivery cost is proportional to the required number of delivery batches. It is proved that the problem is NP-hard in the strong sense and some solution properties are characterized. Thereupon, two heuristic algorithms are derived. To test the effectivenesses of the two derived heuristic algorithms, a lower bound based on the Lagrangian relaxation technique is derived. Numerical experiments are conducted to evaluate performance of the derived heuristic algorithms, which shows that the heuristic algorithms work quite well.
The second and third problems are concerned with logistics scheduling problems with outsourcing allowed where each job can be either delivered via in-house vehicles or outsourced through outside delivery. They are concerned with due date related measures and inventory holding costs, respectively. The objective is to find a schedule to minimize the weighted sum of the outsourcing cost and the scheduling measure represented by either one of maximum lateness, total tardiness and sum of completion times, subject to outsourcing budget. It is proved that the considered problems are NP-hard and some solution properties are characterized. Thereupon, heuristic algorithms and also branch-and-bound algorithms are derived. Numerical experiments are conducted to evaluate performance of the derived algorithms, which show that the heuristic algorithms work quite well.
본 연구는 공급사슬 관리에서의 물류 일정계획 수립을 주제로 다루고 있다. 생산단계에서는 작업 순서를 결정하고, 이후의 배송단계에서는 배송순서 및 조합을 결정하는 공급사슬 환경을 고려하고 있다. 각 장의 분석은 문제의 복잡도를 고찰하는 것으로 시작한다. 즉, 고려하고 있는 문제가 다항시간 안에 쉽게 풀리는 문제라면, 다항시간 내에 최적해를 구할 수 있는 알고리즘을 제시하고, 만일 NP-hard 문제라면, 효율적인 휴리스틱 알고리즘을 제시하는 것을 주요 연구내용으로 한다.
본 연구는 세가지 물류 일정계획 문제를 고려하고 있다. 첫 번째 문제는 단계에 따라 유지비용이 차별화 되어 부과되는 상황에 관한 생산-배송 문제를 고려하고 있다. 고려하고 있는 문제에서, 제품들은 단일설비에서 가공되어서 완제품화되고, 이후에 용량의 제한이 있는 운송수단에 의해서 고객에게 배송된다. 연구의 목적은 각 단계별 유지비용과 배송비용의 합을 최소화하는 것으로 한다. 본 문제는 NP-hard임이 증명되었고, 최적해가 가지는 특성을 추가적으로 규명하였다. 라그랑지안 완화기법에 기반한 lowerbound를 제시하였고, 세 개의 휴리스틱 알고리즘들을 제안하였다. 수치 실험의 결과로 제시된 휴리스틱 알고리즘들이 우수한 성능을 보여줌을 알 수가 있었다.
본 연구가 고려하는 두 번째, 세 번째 문제는 아웃소싱을 고려하는 물류 일정계획 문제들이다. 즉, 제품들이 보유중인 운송수단에 의해서 배송되거나, 외부의 택배회사 외주를 통해서 배송이 가능한 상황을 고려한다. 제품의 배송을 택배회사에 위탁했을 경우에는 그에 따른 아웃소싱 비용이 발생하고, 배송시간이 소요된다. 회사는 아웃소싱 비용으로 지출할 수 있는 최대 예산을 정책적으로 설정하고 있어서, 최대 예산 내에서 아웃소싱을 위탁할 수 있다. 연구의 목적은 제품 유지비용과 아웃소싱 비용의 최소화하는 배송일정 계획을 수립하는 것이다. 고려하고 있는 문제는 NP-hard 문제임을 증명되었고, 몇 가지 최적성질들도 함께 규명되었고, 그에 기반한 휴리스틱 알고리즘들과 분지한계 알고리즘을 유도하였다. 실험결과를 통해서 유도된 휴리스틱 알고리즘이 훌륭한 성능을 보여줌을 알 수 있었다.
