Common Due-Date Assignment and Scheduling in Single and Parallel Machines with Sequence Independent and Dependent Setup Times

Abstract

본 논문은 순서 종속적/비종속적 작업준비시간을 고려하여 납기결정(Due date assignment), 미리 생산(Earliness) 그리고 납기지연(Tardiness) 관련비용의 총합을 최소화하도록 공통 납기일 및 일정계획을 결정하는 문제를 다루고 있다. 납기일을 결정하는 것은 한 회사가 고객들의 주문에 납기일을 제안하거나 또는 회사가 제안한 납기일이 고객이 요구하는 납기일보다 멀어질수록 제품의 가격을 할인해주는 경우와 같이 중요한 결정사항이 된다. 사실 납기일이 고객에 의해 단순히 결정되어지기보다는 고객과 협의과정을 통해서 납기일을 결정하는 다양한 상황들이 존재하고 있다. 일반적으로, 제시간에 제품의 생산을 완료하거나 고객에서 제품을 인도하는 것이 어렵기 때문에 납기일이 빠르면 빠를수록 고객의 신용을 잃어버릴 가능성이 높아진다. 반대로, 납기일이 늦어지면 늦어질수록 생산 완료된 제품들에 대해 높은 재고비용이 발생할 가능성이 높아진다. 그러므로, 납기결정에 관한 의사결정이 고객의 주문을 만족시키기 위한 중요한 요인들 중의 하나이다. 첫 번째로, 단일기계에서 납기결정, 미리 생산 그리고 납기지연 관련 비용의 총합을 최소화는 공통 납기일 및 일정계획을 결정하는 문제를 다루었다. 이전의 납기결정 및 일정계획 문제들과 달리 순서 종속적 작업준비시간을 가지는 문제를 고려하였으며, 이 제약은 본 장에서 고려하고 있는 문제를 더욱 복잡하게 한다. 본 문제의 소규모문제에 대해서 최적해를 구할 수 있는 분지한계 방법(branch and bound algorithm)을 개발하였다. 본 장에서는 해의 탐색 영역을 줄이기 위한 방법으로 해의 우월성질(dominance property), 하한(lower bound) 및 상한(upper bound)을 개발하였으며 이를 제안하는 분지한계방법에 이용하였다. 또한 대규모 문제에 대해서는 2 단계로 구성된 발견적 기법들을 제안하였다. 분지한계 방법과 발견적 기법의 성능 평가를 위해 임의로 생성한 문제에 대하여 실험을 수행하였다. 추가적으로 수주형 생산 체제(make-to-order)라는 가정하에 고지를 수거한 후 재처리를 통하여 포장용 골판지를 생산하는 한 제지회사의 재제조시스템에 대한 사례연구를 수행하였다. 포장용 골판지를 생산하는 시스템이 직선적으로 일관되게 흘러가는 연속생산 공정이고, 순서 종속적 작업준비시간을 가지기 때문에 단일기계에서 순서 종속적 작업준비 시간을 고려한 공통 납기일 및 일정계획을 결정하는 문제로 접근 할 수가 있다. 본 장에서 다루는 문제의 목적함수에서 미리 생산과 납기지연과 연관되는 비용들은 재고비용 (inventory cost)과 추후납품비용(backorder cost)으로 부터 얻을 수 있다. 본 문제에 대해서 앞장에서 제안한 두 가지 형태의 알고리듬을 적용하였다. 즉, 소규모 문제에 대해서 최적해를 구할 수 있는 분지 한계 방법과 대규모 문제에 대해서는 적절한 해를 주는 2 단계로 구성된 발견적 기법들을 적용하여 사례연구를 수행하였다. 두 번째로, 병렬기계에서 납기결정, 미리 생산 그리고 납기지연 관련 비용의 총합을 최소화는 공통 납기일 및 일정계획을 결정하는 문제를 고려하였다. 이 문제는 첫 번째 문제를 확장한 것으로 어려운 문제(NP-hard)에 속한다고 알려져 있다. 그러므로, 최적해를 구하는 방법 대신에 문제의 특성을 분석하여 개발한 2 단계로 구성된 발견적 기법과 search 알고리듬들을 제안하였다. 먼저, 계산시간측면에서 효율적인 2 단계로 구성된 발견적 기법은 초기해를 구하는 단계와 이를 개선하는 단계로 구성되어 있다. 그리고, 본 문제에 대한 새로운 이웃해 생성방법을 제안하고 이를 기반으로 하는 tabu search 알고리듬과 simulated annealing 알고리듬을 제안하였다. 성능 평가를 위해 임의로 생성한 문제에 대하여 실험을 수행하였으며, 두 가지 형태의 알고리듬들이 각각 기존 알고리듬들보다 우수함을 보였다. 마지막으로 고려한 문제는 두 번째 문제를 확장한 것으로 병렬기계에서 순서 종속적 작업준비 시간을 고려한 공통 납기일 및 일정계획을 결정하는 문제를 다루었다. 결정변수로는 1) 공통 납기일결정, 2) 병렬기계에 작업 할당, 그리고 3) 각 기계에 할당된 작업의 순서 결정 하는 것이다. 병렬기계에서 납기결정, 미리 생산 그리고 납기지연 관련 비용의 총합을 최소화는 공통 납기일 및 일정계획을 결정하는 문제에 대해서 순서 종속적 작업준비 시간을 고려한 이전 연구가 이루어지지 않았다. 비록 순서 종속적 작업준비 시간이 실제 생산 시스템들에서 중요한 관심사항중의 하나이지만, 문제를 보다 복잡하게 만든다. 그러므로, 본 장의 주요한 목적은 성능이 우수한 효율적인 발견적 기법들을 제안하는 것이며, 이는 순서 종속적 작업준비 시간을 고려한 공통 납기일 및 일정계획을 결정하는 문제에서 크게 기여하였다고 하겠다.; This dissertation focuses on common due-date assignment and scheduling problems with sequence independent and dependent setup times. Assigning due-dates has a certain practical implication when a company offers due-dates to its customers’ orders during sale negotiations or a sales person offers a price reduction when due-dates are far away from the expected ones. In fact, there may be various situations in which due-dates are negotiated rather than simply set by customers. In the first chapter, we consider the problem on single machine for the objective of minimizing the sum of the penalties associated with assigning the common due-date, earliness, and tardiness. Unlike the previous research articles on the single machine problem, we consider sequence-dependent setup times that make the problem much more difficult. Although the sequence-dependent setup is one of important concerns in real production systems, it makes the problem much more complicated. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Also, heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of the algorithms, computational experiments on randomly generated test instances and results are reported. In addition, we report a case study in a paper remanufacturing system that produces corrugated cardboards using waste papers under the make-to-order environment. Since the system produces corrugated cardboards in an integrated process and has sequence-dependent setup times, we adopt the solution algorithms for the single machine problem considered in this chapter. In the objective function, the penalties associated with earliness and tardiness can be obtained from inventory holding and backorder costs, respectively. Computational experiments were done on the case data and the results are reported. In the second chapter, we consider the problem on parallel machines with sequence-independent setup times. The main decisions are: (a) fixing the common-due-date; (b) allocating jobs to parallel machines; and (c) sequencing the jobs assigned to each machine. The objective is to minimize the sum of the penalties associated with assigning the common due-date, earliness, and tardiness. Due to the complexity of the problem, we suggest two types of heuristics, a two-stage heuristic and search heuristics, after characterizing the solution properties. The two-stage heuristic, which is useful when computation time is critical, solves the problem with two stages: obtaining an initial solution and improvement. The search heuristics, tabu search and simulated annealing algorithms, are based on the neighborhood generation methods devised for the problem. Computational experiments were done on a number of test problems and the results show that both types of algorithms outperform the existing ones, respectively. The last chapter extends the problem considered in the second chapter by considering sequence-dependent setup times. Since it is not appropriate to develop optimal algorithm, we suggest heuristic algorithms in which an initial solution is obtained and then it is improved. Computational experiments were done on a number of test problems and the results are reported.