우리는 convex resource consumption와 job rejection을 결합한 단일 기계 스케줄링 문제군을 연구한다. 여기서 성능 척도는 채택된 작업들의 총 완료 시간(total completion time)이다. 자원 소비 비용과 작업 거절 비용이 목적함수에 포함되는지, 혹은 예산 제약으로 주어지는지에 따라 구분되는 네 가지 자연스러운 변형에 대해, 우리는 각 문제의 계산 복잡도를 분석하고 효율적인 알고리즘을 개발한다. 그 결과, 하나의 변형은 다항 시간에 해결 가능함을 보였으며, 두 변형은 약한 NP-hard 문제이지만 완전 다항시간 근사 알고리즘(FPTAS)을 적용할 수 있음을 보였다.
1. Introduction
각 작업의 처리시간이 추가 자원 할당을 통해 단축될 수 있는 문제를 고려함. (single-machine scheduling)
구체적으로, 각 작업의 처리 시간은 다음 3가지 요소에 의해 결정되는 작업별 함수로 주어짐:
작업량 workload
할당된 자원의 양
스케일링 계수 multiplier
처리 시간은 작업량은 자원 사용량으로 나눈 후, 작업별 특성을 반영하기 위해 multiplier를 적용하여 계산됨.
각 작업은 accept하거나 reject 가능
작업을 거절하면, 해당 요청을 거부하거나 취소함으로써 발생하는 손실이나 불편을 반영하는 패널티 비용이 발생함.
반면, 작업을 수행하는 경우에는 시스템 성능 향상을 위해 투입된 자원에 대한 운영 비용이 발생함.
본 연구에서 고려하는 성능지표는 수락된 작업들의 총 완료 시간
이 연구의 동기는 제조 시스템에서 흔히 발생하는 다음과 같은 문제에서 출발
수요가 생산 능력을 초과하는 상황에서 최대 효율을 달성해야 하는 문제
이 경우 의사결정자는 다음 2가지 전략 중 하나를 선택:
일부 작업 외주처리 outsourcing
추가 자원을 투입해 내부 생산 속도 높임.
따라서, 자원 및 예산 제약 하에서 총 비용을 최소화하려면
어떤 작업을 외주로 돌릴지(=거절)
내부에서는 자원을 어떻게 배분할지
결정해야 함. 이러한 trade-off는 실제 제조 환경에서 매우 흔하며, 본 연구 문제의 중요성을 잘 보여줌.
문제를 수식적으로 정의하면 다음과 같음:
작업 집합: J = {1,2,...,n}에 대하여 각 작업 j는 다음을 가짐: 작업량 wj, 거절비용 rj(정수)
작업 집합을 다음과 같이 나눔:
A: accept 작업
R = J \ A: reject 작업
각 수행된 작업 j∈A에 대해 uj > 0: 할당된 자원량
자원은 전체 스케줄 동안 연속적이며 재사용되지 않는 자원으로 가정함.
각 작업의 처리 시간은 다음과 같이 주어짐:
(여기서 k>0는 상수)
자원이 많으면 처리시간이 줄어들지만 비용은 높아짐.
자원 사용 비용 = uj
거절 비용 = rj
하나의 스케줄을 다음과 같이 표현:
A*: 수행 작업 집합
u*: 자원 할당
π*: 작업 순서
작업 순서는 처리시간 짧은 순으로 정렬됨. 각 작업 j의 완료시간을 Cj(σ)라고 하자.
다음 3가지 값 정의:
4가지 문제 정의:
시간 + 자원 + 거절 비용 모두 minimize
거절 비용은 예산 제한
자원 + 거절 비용 둘 다 constraint
자원은 constraint, 나머지는 objective
2. Literature Review
본 연구와 밀접하게 관련된 두 가지 연구 흐름 살펴보기
1. 처리시간이 조절 가능한 scheduling 2. 작업 거절이 가능한 scheduling
이후 두 흐름 통합한 연구들도 소개됨. (single-machine scheduling 관련 문헌으로 한정)
1. 처리 시간을 조절할 수 있는 스케줄링 연구
Vickson[31]에 의해 시작
일반적으로 처리 시간은 linear / convex 함수로 모델링됨.
본 논문은 convex 모델을 사용하므로 볼록 자원 소비 함수 기반 연구에 집중
관련 연구:
프로젝트 스케줄링: Monma et al.
병렬 스케줄링: Choi & Lee, Shabtay & Kaspi
flow-shop 스케줄링: Cheng & Janiak, Choi & Park, Shabtay et al.
Choi and Chung [6]
작업에 대한 자원 할당이 하한과 상한으로 제한되는 세 가지 경우 연구
makespan과 총 자원 소비 비용의 합 최소화
총 자원 소비 비용 제약 하에서 makespan 최소화
총 완료시간과 총 자원 소비 비용의 합 최소화
이들은 모두 다항시간에 해결 가능함을 보임.
Shabtay and Kaspi [23]
자원 소비 제약 하에서 총 가중 완료시간을 최소화하는 문제를 고려
총 완료시간 최소화와 같은 몇 가지 경우에서 다항시간 해결이 가능함을 밝힘.
휴리스틱과 함께 동적 계획법 제안
BUT. 일반 문제의 계산 복잡도는 여전히 해결 x
Choi and Chung [7]
총 지연 작업량과 총 자원 소비 비용의 합 최소화
자원 소비 제약 하에서 총 지연 작업량 최소화
이 두 문제 모두 NP-hard임을 보였지만, 모든 납기일이 동일한 경우에는 다항시간에 해결 가능함을 보임.
Shabtay and Zofi [28]
단일 비가용 기간이 존재하는 경우 자원 소비 제약 하에서 makespan 최소화하는 문제 연구
NP-hard 문제임을 보이고, 근사 알고리즘 + FPTAS 개발함.
Choi and Park [9]
여러 개의 비가용 기간이 존재하는 경우 고려 (확장)
makespan과 총 자원 소비 비용의 합 최소화
자원 소비 제약 하에서 makespan 최소화
두 경우 모두 strong NP-hard임을 보이고, 근사 가능성과 근사 불가능성에 대해 분석
2. 작업 거절이 포함된 스케줄링 연구
Bartal et al. [1]에서 시작
작업 거절 및 주문 수락 스케줄링에 대한 종합적 리뷰는 Palakiti et al. [19], Shabtay et al. [21], Slotnick [29]를 참고
병렬 스케줄링에 대한 연구는 Bartal et al. [1], flow-shop 스케줄링은 Choi and Chung [5]를 참고
Cao and Zhang [2]와 Zhang et al. [32]
release time이 있을 때 makespan과 총 거절비용의 합을 최소화하는 문제 고려
[2]에서는 NP-hard임을 증명 + 근사 알고리즘 제안
[32]에서는 weakly NP-hard임이 밝혀지고 FPTAS가 제시됨.
Sengupta [20]
maximum lateness와 거절 비용의 합을 최소화하는 문제 연구
weakly NP-hard이고 FPTAS를 가짐을 보임.
Engels et al. [11]
총 가중 완료시간과 총 거절 비용의 합을 최소화하는 문제 고려
weakly NP-hard이지만 모든 가중치가 동일한 경우에는 다항시간에 해결 가능함을 보임.
Lee and Sung [17]
총 완료시간을 최소화하되 거절 비용에 대한 제약이 있는 문제의 NP-hard성 증명
Shabtay et al. [22]
작업 거절과 위치 기반 패널티를 포함하는 단일 기계 스케줄링에 대해 bicriteria 접근법 제안
다양한 거절 기반 모델을 일반화하는 통합 분석 프레임워크 제공
이 모델은 다양한 단일 기계 스케줄링 문제를 유도할 수 있는 기본 참조 모델로 활용
최근 연구들은 자원 소비와 작업 거절을 통해 다룸.
Choi [4], Karhi and Shabtay [15], Shabtay and Steiner [26]은 볼록 자원 소비 함수와 작업 거절을 포함하는 단일 기계 스케줄링을 연구
[26]: makespan, 총 자원 소비 비용, 총 거절 비용의 합을 최소화하는 문제 (다항시간에 해결 가능)
[4]:
두가지 목적 고려
자원 소비와 거절 비용의 합에 대한 예산 제약 하에서 makespan 최소화
각 비용에 대해 개별적인 예산 제약 하에서 makespan 최소화
이 두 문제는 NP-hard이지만, 작업량이 비증가 순서 + 거절비용이 비증가 순서인 경우에는 다항시간에 해결 가능함.
Karhi and Shabtay [15]
makespan과 총 거절 비용의 합에 대한 제약 하에서 총 자원 소비 비용을 최소화하는 문제를 고려
NP-hard임을 보이고 FPTAS 제안
특히, makespan과 총 자원 소비 비용의 합을 최소화하면서 거절 비용 제약이 있는 경우의 계산 복잡도는 아직 해결 x
그러나 [4]의 reduction을 이용하면 이 문제 역시 NP-hard임을 직접 보이기 가능
총 완료시간, 자원 소비 비용, 그리고 거절을 동시에 고려한 스케줄링 문제를 다룬 연구는 아직 존재 x
3. Results
introduction에서 제안한 문제 4가지의 계산 복잡도 분석
→ π의 역순(reverse sequence)이라고 하자.
즉, τ(h)는 π에서 뒤에서부터 h번째 위치에 있는 작업
(이후부터는 논문 전반에서 π 대신 τ 사용)
식 （１）
여기서 H = {1,2,...,n}은 스케줄에서 가능한 위치 집합
그러면 다음이 성립함:
식 （２）
작업 집합 A의 역순 τ가 주어졌을 때, 문제 P1과 P2에서의 최적 자원 할당 u는 다음과 같이 주어짐.
<Proof>
식 （２）와 Ｌｅｍｍａ１로부터 최적 자원 할당 하에서 문제 P1은 다음 문제로 단순화됨;
작업을 A와 R로 분할하고, A 내 작업 순서를 정해 다음을 최소화:
비슷한 방식으로 문제 P2도 다음 문제로 단순화됨:
→ 여기서 중요한 점은 다음과 같음:
고정 집합 A에 대해 목적함수 값은 오직 작업 순서에만 의존함.
총 완료시간은 처리시간이 non-decreasing 정렬 시 최소가 되므로, 최적순서 쉽게 결정
따라서 '어떤 작업을 선택할 것인가(accept vs reject) 결정만 남음.
결론적으로, 문제 P1, P2는 모두 partitioning problem(작업 분한 문제)로 볼 수 있음.
단순화를 위해, 작업들이 다음과 같이 정렬되어 있다고 가정: w1≥w2≥⋯≥wn
이때, 수행된 작업들은 τ에서 인덱스 증가 순서로 정렬된다고 가정
3.1 Problem P1
polynomial time에 해결 가능함 보이기
<Proof> 인덱스 쌍 (j,h) (단, 1≤j≤n, 0≤h≤j)에 대해, z(j,h)를 처음 j개의 작업을 고려하고 그 중 정확히 h개를 선택했을 때 얻을 수 있는 최소 목적값이라고 하자.
이 DP는 다음 관찰에 기반함: 작업 j는 h번째로 선택되어 수락되거나, 거절되어야 함.
* DP 테이블 초기화: 식 (6)
여기서 1) 첫 번째 항: 작업 j를 accept하여 h번째 위치에 배치하는 경우 2) 두 번째 항: 작업 j를 거절하는 경우
최대 n개의 작업 선택 가능 → P1의 최적 목적값은 다음과 같음:
DP 테이블은 O(n^2)개의 항을 갖고, 각 항은 식 (6)에 의해 상수 시간에 계산됨. 따라서 전체 알고리즘 수행 시간은 O(n^2)
3.2 Problem P2
P2가 weakly NP-hard임을 보이고, FPTAS를 가지는 것도 보이기
Problem P2는 k=1 인 특수한 경우에서도 NP-hard이다.
<Proof> decision version은 다음과 같음: 주어진 threshold Z2에 대해, 다음을 만족하는 feasible schedule σ가 존재하는가?식 (***)
잘 알려진 partition 문제로부터의 reduction을 통해 NP-hard성을 보임. → partition 문제는 다음과 같다: 정수 집합 {a1, a2, ... , ab}가 있고,
partition 문제의 인스턴스 I가 주어졌다고 하자. 이를 이용해 P2의 인스턴스 I'를 다음과 같이 구성함: 작업 수(n=2b), 작업 집합: J = {1, 2, ..., 2b}
여기서 M:=A+2임. 이 때 M은 다음을 만족:
또한, 다음을 정의하자.
이 reduction은 polynomial time에 수행이 가능하다. 그러므로, 이제 다음을 보이면 된다: I가 해를 갖는다는 것 + I'가 식(***)을 만족하는 feasible schedule을 갖는 것이 동치
(=>)
j가 N에 속해 있으면, job 2j는 reject / job 2j-1은 accept j가 N에 속해 있지 않으면, job 2j-1은 reject / job 2j는 accept
이 때 constructed schedule은 feasible하며, 총 rejection cost와 objective function은 다음과 같다:
(<=) I'가 feasible schedule 갖는다 가정.
(Pf): 두 작업이 모두 reject or 모두 accept 되면 제약 조건 또는 목적값이 깨지므로 모순 발생 ∴ 정확히 하나만 선택
다음을 정의:
→ 만약 strict inequality(<)이면 목적값이 Z2보다 커지므로 모순. 따라서 = → 즉, N은 partition 문제의 solution이 됨.
이제 P2가 pseudo-polynomial time에 해결이 가능함 / FPTAS를 가짐을 보이면 된다. 이를 위해 restricted shortest path problem (RSPP)로 reduction한다.
RSPP 정의: 그래프 G = (V,E)에서 각 edge(길이 Iij, 지연 dij), source s, target t, delay 제한 D → 목표: delay≤D를 만족하면서 최단 경로 찾기
P2는 O(n^2) 시간에 RSPP로 reduction 가능함.
<Proof> 1. 노드를 다음과 같이 만듦;
- 시작점 s = (0,0) - 중간 노드 (j,h): 앞에서 j개 작업을 봤을 때, 그중 h개를 accept한 상태 - 마지막 도착점 t 즉, (j,h)는 state라고 보면 됨.
2. 간선의 의미 각 작업 j를 하나씩 보면서 두 선택지가 존재함. 1) 작업 j를 reject: (j-1,h) → (j,h) length = 0 delay = rj ∵ reject하면 목적함수 쪽에는 안 들어가고, 대신 rejection budget을 소모하니까. 2) 작업 j를 accept length = λjh delay = 0 ∵ accept하면 rejection cost는 안 쓰고, 대신 목적함수 쪽 값이 하나 추가되니까 3) 모든 (n,h)에서 t로 가는 간선을 붙임. length = & delay 0 3. 왜 정확히 스케줄 하나를 나타내냐면, 경로: (0,0)→(1,h1)→(2,h2)→⋯→(n,hn)→t 에 대하여 여기서 hj는 처음 j개 작업 중 accept된 개수를 의미함. 그러면 h_{j}=h_{j}-1이면 작업 j는 reject / h_{j}=h_{j-1} +1이면 작업 j는 accept 즉, 경로 하나가 각 작업마다 accept / reject 결정 accept된 작업들은 h=1,2,... 순서로 배치되므로 각 작업이 뒤에서 몇 번째 자리인지도 자동으로 결정 그래서 경로 : feasible schedule이 일대일대응이 됨.
4. 경로의 delay와 length가 왜 원문제와 맞냐면,
reject 간선만 rj를 가지니까 total delay는 정확히 총 rejection cost가 됨. 그래서 delay 제한을 D = R로 두면, 원래 문제의 제약 W3≤R와 완전히 동일
결국 P2는 delay가 R 이하인 s-t 경로 중에서 length가 최소인 경로 찾기 문제로 바뀌고(RSPP) 시간 복잡도는 다음과 같아짐: O(n^2)
3.3. Relation to positional-penalty scheduling with job rejection
Shabtay et al.[22]는 작업 거절이 있는 단일 기계 스케줄링에 대해 일반적인 이중 기준 프레임우크 연구
이때 스케줄의 품질은 다음 두 기준으로 평가됨:
수락된 작업의 고정 처리시간에 적용되는 위치 기반 패널티 기준 F1
총 거절 비용 F2
ξh(α)는 뒤에서부터 계산한 위치 h에 있는 작업에 대한 위치 의존 패널티(α값에는 의존하지만 작업에는 독립적인 값) / pˉj 는 작업 j의 고정 처리시간
이 프레임워크에서 중요한 subclass:
ξh(α)가 α와 무관하고,
h에 대해 단조 비감소(monotonically nondecreasing)인 경우
Lemma 1과 식 (4)-(5)에 의해, P1과 P2는 instances of this monotone positional-penalty subclass로 재정의
따라서 우리 문제에서 유도되는 위치 패널티는 α와 무관하며, h에 대해 단조 비감소 함수가 됨.
그 결과, 본 논문에서 도출한 복잡도 결과:
Problem P1은 다항시간에 해결 가능하고
Problem P2는 weakly NP-hard
이라는 사실은 [22]에서 보고된 결과와 일치
그러나 설명의 완결성과 self-contained 유지하기 위해, 본 연구의 자원 기반 모델에 맞추어 직접적인 reduction과 알고리즘적 논증을 통해 제시함.
또한 Shabtay et al.[22]는 이중 기준 (F1,F2)를 근사하기 위한 FPTAS 제안함.
이 근사 방법은 두 번째 기준 F2에 대해 (1+ ϵ)의 곱셈적 증가를 허용함.
→ F2≤R이라는 hard constraint를 정확히 만족해야 하기 때문에, P2에는 부적합
따라서, 이러한 제약 구졸르 위해 특별히 설계된 독립적인 FPTAS가 필요 + 본 논문에서 제안된 FPTAS는 독립적이고 필수적인 기여.
3.4 Problem P3 and P4
P3가 weakly NP-hard임을 보이고, P3와 P4가 모두 FPTAS를 가짐을 보임.
이 결과는 Shabtay and Kaspi[23]의 분석으로부터 직접적으로 도출되므로, 간결함을 위해 증명 생략
증명증명증
4. Concluding remarks and future research
볼록 자원 소비와 작업 거절을 포함하는 4가지 단일 기계 스케줄링 문제를 다룸. 성능 척도로는 수락된 작업들의 총 완료 시간을 사용.
P1: 총 완료시간, 총 자원 소비 비용, 총 거절 비용의 합 최소화하는 것을 목표로 + 다항 시간에 해결 가능함
P2 & P3: 각각 총 거절 비용에 대한 제약, 그리고 총 자원 소비 비용과 총 거절 비용 모두에 대한 제약을 가지며, 이 두 문제는 weakly NP-hard임을 보였고 동시에 FPTAS를 가짐을 확인
P4: 총 자원 소비에 대한 예산 제약 하에서 총 완료 시간과 총 거절 비용의 합을 최소화하는 문제 + 위치 기반 패널티 구조와의 연관성을 활용해 FPTAS를 가짐을 확인
그러나 P4의 정확한 계산 복잡도(polynomial time에 해결 가능한지 / NP-hard인지 여부)는 여전히 열린 문제로 남아 있음.
향후 연구에서는 총 자원 소비 비용과 총 거절 비용의 합에 대해 하나의 결합된 제약을 두고 총 완료 시간을 최소화하는 문제의 계산 복잡도를 분석하는 것과, Problem P4의 정확한 복잡도 분류를 규명하는 것이 흥미로운 연구 주제가 될 것
Problem P1~P4 새롭게 정의하고
복잡도 결과 제시하고
DP, reduction, FPTAS 제안
"새로운 이론 결과 만듦."
핵심 포인트? total completion time + resource + rejection 을 동시에 다룬 최초 연구
