작업이 제약 조건을 갖는 병렬 기계의 온라인 스케줄링

Abstract

In practical situations, all machines may not be suitable for processing of jobs. The service provision problem in service industry is a good example of such cases. In service industry, service provider provides differentiated services to the customers according to their promised grade of service(GoS) levels, resulting in an assignment restriction. Another application of the problem is an application in loading and unloading cargoes of a vessel, where there are multiple non-identical loading/unloading cranes working in parallel. The cranes have identical operating speed but different weight capacity limits. Each piece of cargo can be handled by any crane with a weight capacity limit no less than the weight of the cargo. The problem which deals with such situations is called scheduling problem with eligibility constraints. In this problem, each job can be processed only by machines in a job-dependent subset of the set of all machines, which is referred to as the eligible set of the job. Thus, we consider scheduling problems with eligibility constraints. First, we consider the online parallel machine scheduling problem of minimizing the makespan under eligibility constraints that restrict each job to be processed only on one of its eligible machines. The greedy algorithm AW is known to be optimal for this problem when the number of machines is a power of 2. However, in other cases, the gap between the best known competitive ratio and its lower bound can be as large as 1. In this dissertation, we construct new competitive ratio and its lower bound and show that the gap between them is no more than an irrational number which is approximately 0.1967 and establish optimality for the cases when the number of machines can be written as a sum of two powers of 2. We further analyze the case with seven machines showing that their gap is no more than 1/180. Moreover, we present new lower bounds of the competitive ratio for the cases with interval and nested eligibility as well as improved competitive ratios for several cases with GoS eligibility. Second, we consider four semi-online parallel machine scheduling problems of minimizing the makespan given a priori information about the total processing time, the largest processing time, the combination of the previous two and the optimal makespan. We propose a unified algorithm that can be applied to all the cases, and prove an improved competitive ratio for the cases with a small number of machines. We also provide improved lower bounds of the competitive ratio by presenting unified adversary lower bound examples. Finally, we consider four semi-online scheduling problems on small number of machines subject to GoS eligibility constraints with different information. We discuss the semi-online scheduling problems with known total processing time and known the largest processing time. Then, we investigate the semi-online scheduling problems with known total and largest processing times. Lastly, we discuss the semi-online scheduling with known the optimal makespan. For each semi-online problem, we present new bounds of the competitive ratio for the problem on small number of machines.

전통적인 스케줄링 문제에서는 작업의 배치를 정하기 전에 모든 정보가 주어졌다는 가정을 하고 있다. 하지만 실제 상황에서는 정보가 주어지지 않거나 부분적인 정보가 제공되고 있다. 이러한 이유로 온라인 혹은 세미 온라인 스케줄링의 연구의 필요성이 대두되기 시작하였다. 그리고 실제 현실에서는 작업들이 특정 기계에서만 처리 가능한 경우가 발생하기도 한다. 스케줄링 이론에서는 이 문제를 scheduling with eligibility constraints 라 한다. 그래서 본 논문에서는 다음과 같은 세 가지 주제를 다루었다. 첫째, 작업이 제약 조건을 갖는 상황에서의 온라인 스케줄링 문제들을 다루었다. 그 중에서도 작업이 기계들의 임의의 부분 집합에서만 작업가능한 scheduling with general eligibility 을 다루었다. Scheduling with general eligibility 에 대해서 Y.Azar et al.(1995)가 알고리즘 AW을 제안하였고, 기계의 대수가 m = 2^k 으로 표현되는 경우에 알고리즘 AW가 최적이라는 것을 증명하였다. 하지만 이번 연구를 통해서 알고리즘 AW은 m = 2^k + 2^{k'} 인 경우에도 최적임을 알게 되었고, 그 결과 기계의 대수가 10대 이하에서는 7 대인 경우만 빼고 모두 최적임을 알게 되었다. 그리고 7대의 경우도 lower bound와 upper bound의 gap을 집중적으로 분석하여 1/180까지 줄였다. 그리고 general eligibility constraints 뿐만 아니라 GoS eligibility constraints, nested constraints, interval constraints 등도 연구하였고, 기존 결과물들보다 향상된 결과를 도출하였다. 둘째, 작업을 배치하기 전에 부분적으로 정보가 주어지는 세미 온라인에 대해서 다루었다. 본 논문에서 다룬 세미 온라인 문제는 총 4 문제로 총 작업 시간이 알려진 경우, 작업 중에서 가장 긴 시간이 알려진 경우, 총 작업 시간 및 가장 긴 시간이 알려진 경우와 최적해가 알려진 경우에 대해서 다루었다. 이 문제들의 competitive ratio을 개선하기 위해서 우리는 통합 알고리즘인 FBL(m, r)을 제안하였고, 기존의 결과보다 향상된 결과를 얻었다. 그리고 총 작업 시간이 알려진 경우, 작업 중에서 가장 긴 시간이 알려진 경우, 총 작업 시간 및 가장 긴 시간이 알려진 경우에 대해서는 통합된 하나의 lower bound의 예제를 만들었다. 마지막으로 총 작업 시간이 알려진 세미 온라인 스케줄링이 최적해가 알려진 세미 온라인 스케줄링보다 더 일반적임을 증명하였다. 마지막으로, 작업이 특정 기계에 대해서 작업 가능한 경우의 세미 온라인에 대해서 연구하였다. 여기에서 연구한 것은 앞 장에서 연구한 4가지 세미 온라인이고, 여기에서도 기존보다 향상된 결과를 얻었다.