This thesis considers a single machine scheduling problem to maximize total job value subject to machine availability constraint where each job is represented by a nonincreasing stepwise value function. In the analysis, some solution properties are characterized, based on which two solution algorithms including a branch-and-bound algorithm and a heuristic algorithm are derived. Numerical experiments show that the heuristic algorithm is efficient and effective.
전통적인 스케쥴링 문제에서는 모든 작업들이 완료된다는 가정하에 최대 작업 완료시간, 총 작업시간, 총 납기 지연 등을 최소화 하는 문제를 고려하였다. 그러나 근로자의 근무시간의 제한이나, 일정 계획 기간의 제한으로 인하여, 고려하는 모든 작업을 완료할 수 없는 상황도 빈번히 발생한다. 더불어 서비스 산업에서는 고객 만족도가 작업 완료 시간에 의존한 함수로 나타내어질 수 있다. 예를 들어, 고객의 주문이 완료되는 시간이 늦어질수록 고객의 만족도는 낮아진다. 따라서 제한된 시간 내에 고객의 주문을 선택적으로 그리고 어떠한 순서로 처리해야 기업이 얻는 이익을 최대화할 것인가에 대한 의문을 해결해야 될 필요성이 대두되었다.
본 논문에서는 각각의 작업들이 작업 완료 시간에 의존한 nonincreasing stepwise value function 으로 표현되어지며, 제한된 시간 안에 단일기계가 어떠한 순서로 작업들을 처리해야 기업의 이윤을 최대화할 수 있는가를 다루고 있다. 제시된 문제를 풀기 위해 분지한계법(branch-and-bound)과 휴리스틱(heuristic)이 적용 되었으며, 제안된 알고리즘의 특성을 비교하여, 각각의 알고리즘을 적용 가능한 분야를 제시하였다.
