https://www.sciencedirect.com/science/article/pii/S037722171500123X
Abstract
우리는 여러 개의 마일스톤과 완전히 순서가 정해진 작업들을 갖는 continuous time–cost tradeoff problem를 다룬다. 마일스톤이 기한을 넘기면 벌점 비용이 부과될 수 있다. 각 작업의 처리시간은 추가 자원이나 추가 활동을 투입해 단축할 수 있지만, 이 경우 단축 비용이 발생한다. 목적은 전체 지연 벌점 비용과 전체 단축 비용의 합을 최소화하는 것이다. 우리는 단축 비용 함수가 concave인 경우에도 이 문제가 NP-hard임을 보이고, 그 경우에 대한 의사다항시간 알고리즘을 제시한다. 또한 단축 비용 함수가 convex인 경우에는 이 문제가 다항시간에 해결 가능함을 보인다.
1. Introduction
- Time-Cost Tradeoff Problem(TCTP)는 각 작업의 처리시간이 장비, 노동, 자본과 같은 추가 자원을 사용함으로써 단축될 수 있다고 가정함.
- 일반적 목적: 단축 비용 예산 제약하에서 프로젝트 완료시간을 최소화 or 프로젝트 완료시간 제약 하에서 총 단축 비용 최소화
- Continuous TCTP(CTCTP)는 단축 비용이 연속함수로 표현되는 TCTP를 말함.
- Linear TCTP(LTCTP)는 선형계획 문제로 정식화 가능
기존의 TCTP 연구들은 프로젝트 전체에 대해 하나의 마일스톤, 즉 마지막 작업만을 가정해왔다. 그러나 실제로는 하나의 프로젝트 안에 여러 개의 마일스톤이 존재할 수 있다. 따라서 특정 시점까지 지정딘 작업이 완료되지 않으면 벌점이 부과될 수 있다.
ex) venture capital company는 처음에 프로젝트에 소규모 투자를 하고, 이후 마일스톤이 달성되었을 때 프로젝트의 진행 상황에 따라 중단할지 추가 투자를 할지 결정함.
하나 이상의 마일스톤을 갖는 TCTP를 다룬 연구는 Choi and Chung (2014)만 있음. 이들은 multiple milestones와 completely ordered jobs를 갖는 두 가지 LTCTP를 고려하였다.
- 첫 번째 문제의 목적은 총 단축 비용 제약 하에서 가중 지연 작업 수의 합을 최소화하는 것 (NP-hard임을 보임.)
- 두 번째 문제의 목적은 가중 지연 작업 수의 합과 총 단축 비용의 합을 최소화하는 것 (polynomial time에 풀 수 있음을 보임.)
본 논문은 Choi and Chung (2014)에서 다룬 두 번째 문제를 일반화한 버전을 고려하며, 여기서는 단축 비용 함수가 비선형일 수 있다. 시간-비용 관계는 여러 선행연구에서 다루어져 왔다. 비선형 단축비용 함수, 오목한 단축 비용 함수, 볼록한 단축 비용 함수 등이 각각 연구되었다.
문제
CTCTP는 방향성 activity-on-node 그래프 G = (V,A)로 표현되며,
여기서 V = {1,2,...,n}은 작업 집합이고 A는 선행관계의 집합이다.
관계 (i,j)∈A(i,j)는 작업 가 완료된 후에야 작업 j를 시작할 수 있음을 의미한다.
각 작업 j에는 정상 처리시간 pj∈Z+와 최대 단축 가능량 uj(≤pj)∈Z+가 주어진다 (j=1,2,…,n).
x=(x1,x2,…,xn)를 실수 벡터라 하고, xj를 작업 의 단축량이라 하자.
그러면 0≤xj≤uj (j=1,2,…,n)이다.
작업 를 xj만큼 단축하면 단축 비용은 fj(xj)가 되며, fj(xj)(≥0)는 xj의 비감소 연속함수이다.
본 논문에서 일반성을 잃지 않고 다음만 고려한다:
- 불필요한 유휴시간을 허용하지 않으며, 따라서 각 작업은 가능한 빨리 처리되는 스케줄
- 단축 비용 함수가 오목 또는 볼록인 경우
단축 비용 함수가 오목하다는 것 = 한계수익이 증가함 의미 (더 많은 자원을 투입할수록 추가 자원의 생산량이 더 높아진다.)
볼록 = 일반적인 체감 한계수익의 법칙을 반영하며, 새 작업자의 수가 증가할수록 추가 작업자 한 명의 한계생산성은 이전 작업자보다 작아짐.
각 스케줄 x에 대해 각 작업은 유일한 시작시점을 가지므로, x 자체를 스케줄이라 부른다.
를 마일스톤 집합이라고 할 때,
각 j∈D에 대해, wj∈Z+는 지연에 대한 벌점 비용, dj∈Z+는 마일스톤 j의 마감시점이다.
또한 Cj(x)를 스케줄 x 하에서 작업 의 완료시각이라 하자. 그러면 우리의 문제는 다음과 같이 정의된다.
목적함수는 지연된 마일스톤들의 벌점 비용 합 + 모든 작업의 단축 비용 합 (최소화)
제약식은 모든 선행관계 (i,j)∈A=에 대해 작업 i의 완료시각에 작업 j의 단축 후 처리시간을 더한 값이 작업 j의 완료시각보다 클 수 없도록 하며, 각 j=1,2,…,n에 대해 0≤xj≤uj를 만족해야 한다.
여기서 T(x)는 스케줄 x에서 기한을 넘긴 마일스톤들의 집합을 의미
인 문제는 D=V인 문제로 변환할 수 있다. 이를 위해 i∈V∖D에 대해 di=∑pj로 두면 된다. 그러면 i∈V∖D인 작업은 늦게 완료될 일이 없으므로, 두 문제의 최적 스케줄은 동일하다. 따라서 표기 단순화를 위해 D=V라고 가정
본 논문에서는 multiple milestones와 completely ordered jobs를 갖는 CTCTP에 초점을 맞춤.
completely ordered jobs는 A = {(1,2),(2,3), ...,(n-1,n)} 로 표현 가능 → 이 문제를 CTCTP-chain이라 부름.
이 경우 CTCTP-chain은 다음과 같이 정식화:
목적함수는 지연된 작업들의 벌점 비용 합 + 모든 작업의 단축 비용 합을 최소화하는 것
T(x)는 스케줄 x에서 지연된 마일스톤들의 집합
CTCTP-chain은, 정보가 연속된 단계들을 거치며 천천히 축적되는 순차적 제품개발 프로세스를 동기로 함.
각 단계는 바로 직전 단계가 종료되어 완전하고 최종적 정보를 제공한 뒤에야 시작 가능
2. Properties of some optimal schedules for the CTCTP-chain
CTCTP-cain의 최적 스케줄이 갖는 몇 가지 성질을 소개함.
작업 j가 스케줄 x에서 정확히 자신의 마감시점에 완료되면, 즉 dj = Cj(x)이면, 작업 j를 적시 완료 작업(just-in-time)이라고 부름.
Lemma1에 의해, 최적 스케줄은
- 모든 작업이 단축되지 않은 스케줄과
- 적어도 하나의 JIT 작업을 갖는 스케줄들 중 최소 비용 스케줄을 비교해 찾을 수 있음.
따라서 이후부터는 적어도 하나의 JIT 작업은 갖는 스케줄만 고려
이후부터는 Lemma 1과 Lemma 2를 만족하는 스케줄만 고려한다.
3. Concave-CTCTP-chain
In this section, we show that the concave-CTCTP-chain is NP-hard and introduce an approach to solve it in pseudo-polynomial time.
3.1. NP-hardness
concave-CTCTP-chain의 decision version이 partition problem으로부터의 환원을 통해 NP-complete임을 보임.
partition problem은 잘 알려진 NP-complete 문제
partition problem은 다음과 같다:
+ 증명
3.2. Pseudo-polynomial time approach for the concave-CTCTP-chain
+ 증명
4. Convex-CTCTP-chain
+ 증명
O: CON(k,l)의 최적해 집합이라고 하자.
만약 k와 l이 어떤 최적 스케줄 x*에서 연속하는 JIT 작업이라면, (x*_{k+1},...,x*_{l})는 CON(k,l)의 최적해이고, 동시에 O 안에서 지연 가중치가 최소인 해이다.
따라서 O 안에서 지연 가중치가 최소인 CON(k,l)의 최적해를 구하는 방법을 소개함.
CON(k,l)에서 압축 비용 함수가 선형인 경우를 LP(k,l)이라고 하자.
Choi and Chung (2014)는 LP(k,l)의 최적해 중 지연 가중치가 최소인 해를 다항시간에 찾는 다음 알고리즘을 제안
의 최적해 중 지연 가중치가 최소인 해를 구하는 문제를, LP(k,l)의 최적해 중 지연 가중치가 최소인 해를 구하는 문제로 환원
+ 증명
+ 증명
+ 증명
5. Concluding remarks and future works
- 오목한 압축 비용 함수를 갖는 concave-CTCTP-chain이 NP-hard임을 보였고, 이를 pseudo-polynomial time에 해결하는 방법을 제시
- 또한 볼록한 압축 비용 함수를 갖는 convex-CTCTP-chain은 SPP(shortest path problem)로 reduction함으로써 polynomially solvable함을 보였다.
- 향후 연구로는, 보다 일반적인 네트워크 구조에서의 CTCTP 계산 복잡도를 분석하는 것이 흥미로운 주제가 될 것