Resource leveling with subcontracting: algorithms and complexity

The recognition version of problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\) is unary NP-complete.

Given an arbitrary instance of Exact Cover by 3-Sets, we construct an instance of problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\). Let the makespan of the RLP be \(T = (|J| - u + 1)(3u + 2Ku + 1)\), where \(K > 4|J|/u\) and integer. Also, let the objective function threshold, which is the maximum resource level, be \(L = u\).

We construct four types of chains in pseudopolynomial time. To simplify their description, we index the tasks within each chain in precedence order.As a result, the number of tasks isBecause the Type 1 and Type 2 chains have length T, each is scheduled throughout the interval [0, T]. From the definition of L, the remaining resource capacity that is available for the Type 3 and Type 4 chains is 1, for periods \(1, \dots , 3u\), u for period \(3u+1\), 0 for periods \(3u+2\), ..., \(3u + Ku + 1\), u for periods \(3u + Ku +2, \dots , 3 + 2Ku + 1\), and 1 for the remaining periods \(3u + 2Ku + 2, \dots , T\). Observe that the total units of available resource once the Type 1 and Type 2 chains are assigned is \(3u +u +Ku^2 +[T -(3u + 2Ku + 1)] = (|J| - u)(3u + Ku - 3) + |J|(Ku + 4)\), which is exactly the total resource requirement of the Type 3 and Type 4 chains. Consequently, a feasible schedule must use all of the available resources and contain no idle time. Without loss of generality, we assume that when a task with \(r_j = 0\) has no unprocessed predecessors, it is processed as early as possible.

To complete the proof, we show that the constructed instance of problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\) has a feasible solution with a makespan of T and an objective value of \(R_{\max } \le L\) if and only if there exists an exact cover of X by 3-sets.

(\(\Rightarrow \)) Assume the existence of an exact cover by 3-sets. Let \(S_1, \dots , S_u\) denote the 3-element subsets of J that form an exact cover of X. Schedule all the Type 4 chains corresponding to subsets \(S_1, \dots , S_u\) to start processing at time 0 and complete at time \(3u +2Ku+1\). Observe that all the available resources are used in the interval \([0, 3u +2Ku +1]\). Now, schedule the remaining \((|J| - u)\) chains of Type 4 consecutively in any sequence without idle time, starting at time \(3u + 2Ku + 1\) and finishing at time \((3u + 2Ku + 1) + (|J| - u)(3u + 2Ku + 1) = T\). Observe that this does not require more than the remaining available capacity of 1 at any time in the interval \([3u + 2Ku + 1, T]\). However, one unit of idle time occurs at exactly \((|J| - u)(3u + Ku - 3)\) times within that interval. Now, schedule the first \((3u + 2Ku + 1)\) tasks of the Type 3 chain consecutively from time 0. The remaining tasks of the Type 3 chain become available one after another, and all have \(r_j = 1\). Therefore, one of the remaining \((|J| - u)(3u + Ku - 3)\) tasks in the Type 3 chain is scheduled whenever there is an idle time left by the Type 4 chains. Thus, there exists a feasible schedule for problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\) with makespan T and \(R_{\max } \le L\).

(\(\Leftarrow \)) Assume there exists a feasible schedule for problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\) with a makespan of T and an objective value \(R_{\max } \le L\). Because interval [0, 3u] has a total resource availability of 3u, and each Type 4 chain requires three units of resource in the first 3u periods, it is not possible that \((u+1)\) or more Type 4 chains complete their first 3u tasks by time 3u.

Suppose that \((u-1)\) or fewer Type 4 chains complete their first 3u tasks by time 3u. Observe that any Type 4 chain that does not complete its first 3u tasks by time 3u cannot complete its \((3u+1)\)st task until at least time \(3u + Ku + 2\). Therefore, that chain cannot schedule any later task with \(r_j = 1\) until at least time \(3u + 2Ku + 2\). As a result, the Ku tasks \(\{ 3u +Ku +2, \dots , 3u +2Ku + 1\}\) with \(r_j = 1\) in the Type 4 chains that complete their first 3u tasks by time 3u can use at most \(Ku(u-1)\) of the available \(Ku^2\) resources in the interval \([3u + Ku + 1, 3u + 2Ku + 1]\). The remaining Ku units of resource must be used by the first \(3u +1\) tasks of any Type 4 chains. For each of these chains, at most four of their tasks have \(r_j = 1\). Hence, the use of all available resources requires that \(4|J| \ge Ku\), which contradicts the definition of K.

Consequently, exactly u Type 4 chains must complete their first 3u tasks by time 3u. The total resource requirement of the first 3u tasks of these u chains is 3u, and each period of \(1, \dots , 3u\) has a resource availability of 1. Then, the construction of the \(r_j\) values in the Type 4 chains implies the existence of an exact cover of X by 3-sets. \(\square \)

The CRS problem \(P \, | \,\beta \, | \,C_{\max }\) is solvable in polynomial time if and only if \(PS \, | \,\beta , r_j =1 \, | \,R_{\max }\) problem is polynomially solvable.

(\(\Rightarrow \)) Suppose problem \(P \, | \,\beta \, | \,C_{\max }\) is polynomially solvable. Find the minimum number of machines, m, required to satisfy \(C_{\max } \le T\) in problem \(Pm \, | \,\beta \, | \,C_{\max }\). This value of m can be found using binary search by solving \(O(\log n)\) CRS problems. Since the CRS problem instance is polynomially solvable, m can be determined in polynomial time. Because \(r_j = 1\) for \(j \in N\), m is also the minimum value of the maximum resource requirement in \(PS \, | \,\beta , r_j =1 \, | \,R_{\max }\).

(\(\Leftarrow \)) Suppose problem \(PS \, | \,\beta , r_j =1 \, | \,R_{\max }\) is polynomially solvable. Set the number of machines in the CRS problem to the optimal value of the RLP. Using binary search on the value of T, find the smallest feasible value of T in the CRS problem. This can be accomplished by solving \(O(\log \sum p_i)\) CRS problems. Since the RLP is polynomially solvable, the value for T can be found in polynomial time. The value of T found is the minimum makespan for \(P \, | \,\beta \, | \,C_{\max }\). \(\square \)

If the recognition version of CRS problem \(P \, | \,\beta \, | \,C_{\max }\)is binary (respectively, unary) NP-complete, then the recognition version of \(PS \, | \,\beta , r_j =1 \, | \,R_{\max }\) is also binary (resp., unary) NP-complete.

Follows from the (\(\Leftarrow \)) part of Theorem 2. \(\square \)

The recognition version of an RLP where preemption is allowed and \(p_j\) is arbitrary is at least as hard as the corresponding RLP with no preemptions and \(p_j = 1\).

A special case of the preemptive problem is a problem where \(p_j = 1\) for \(j \in N\). Since all data is integer, there exists an optimal solution to the special case where no task is preempted. \(\square \)

If \(B = 0\) and \(c_j > 0\) for \(j \in N\), then Subcontracting Problem A reduces to the original RLP. Hence, all intractability results derived in Section 3 hold for the subcontracting problem.

The recognition version of problem \(PS \, | \,chains, p_j = 1, r_j = 1, c_j \in \{0, 1\} \, | \,R_{\max }\) is unary NP-complete.

By reduction from problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\), for which the recognition version is shown to be unary NP-complete in Theorem 1.

Given an arbitrary instance of problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\), we construct an instance of problem \(PS \, | \,chains, p_j = 1, r_j = 1, c_j \in \{0, 1\} \, | \,R_{\max }\) with the following data. The tasks, precedence graph, makespan, and threshold value of \(R_{\max }\) are unchanged. For any task j, set \(c_j = 0\) when \(r_j = 0\), and set \(c_j = 1\) when \(r_j = 1\). Further, let \(B = 0\).

Without loss of generality, all tasks where \(c_j = 0\) are subcontracted. However, the subcontracting of any task j where \(c_j = 1\) is not feasible. Hence, those tasks must be processed by the machines. Thus, the tasks that are not subcontracted are exactly those that have \(r_j = 1\) in the RLP. Therefore, only those tasks must be scheduled to meet the threshold for the number of tasks processed concurrently.

It follows that there exists a “yes” answer to the recognition question for the constructed instance of problem \(PS \, | \,chains, p_j = 1, r_j = 1, c_j \in \{0, 1\} \, | \,R_{\max }\) if and only if there exists a “yes” answer to the recognition question for problem \(PS \, | \,chains, p_j = 1, r_j \in \{0,1\} \, | \,R_{\max }\).  \(\square \)

(Hu 1961) For problem \(PS \, | \,intree, p_j = 1, r_j = 1, c_j = 1 \, | \,R_{\max }\), the number of available tasks is nonincreasing over time in every feasible schedule.

Given L machines, at least \(\max \{0, \sum _{t =1}^{\tau (L)} \rho _t - L \tau (L)\)} tasks require subcontracting in a feasible solution to problem \(PS \, | \,intree, p_j = 1, r_j = 1, c_j = 1 \, | \,R_{\max }\).

From Remark 3, no subcontracting is needed for the intree for periods \(\tau (L) +1, \dots , T\). To obtain a feasible solution, the total processing needed for periods \(1, \dots , \tau (L)\) is \(\sum _{t=1}^{\tau (L)} \rho _t\). A maximum of \(L \tau (L)\) tasks can be processed by L machines during this period. Hence, at least \(\sum _{t =1}^{\tau (L)} \rho _t -L \tau (L)\) tasks require subcontracting. \(\square \)

Consider two instances, \(I_1\) and \(I_2\) of problem \(PS \, | \,intree, p_j = 1, r_j = 1, c_j = 1 \, | \,R_{\max }\), where both instances have the same number of tasks and value of T. Suppose that \(\sum _{i=1}^j \rho _{I_1}(i) \le \sum _{i=1}^j \rho _{I_2}(i)\) for \(j = 1, \dots , T\). Then, an optimal solution to \(I_1\) does not require more resources than an optimal solution to \(I_2\).

Hu (1961) shows that given L machines,is a necessary and sufficient condition for the existence of a feasible solution without subcontracting. If \(\sum _{i=1}^j \rho _i(I_1) \le \sum _{i=1}^j \rho _i(I_2)\) for all j, then whenever (1) is satisfied for \(I_2\), (1) is also satisfied for \(I_1\). \(\square \)

The number of machines required to solve an instance of \(PS \, | \,intree, p_j = 1, r_j = 1, c_j = 1 \, | \,R_{\max }\), depends only on the number of tasks at each level and not on the precedence structure between tasks of adjacent levels.

Algorithm SubTreeC finds an optimal schedule for problem \(PS \, | \,intree, p_j = 1, r_j = 1, c_j = 1 \, | \,R_{\max }\) in O(n) time.

Lemma 1 specifies a lower bound on the total amount of subcontracting needed. This requirement is satisfied in Step 1 of Algorithm SubTreeC.

Each iteration of Algorithm SubTreeC increases t by 1. As a result, the algorithm stops after T iterations. Step 2 ensures that no subcontracting occurs until \(t = T -\bar{d} +1\). From this time forward, at least one task level is completed each period, using subcontracting when necessary. Consequently, after T iterations, all tasks at every level are processed. As a result, Algorithm SubTreeC finds a solution that satisfies the completion time constraint.

Once \(w \le L\), Step 2 of Algorithm SubTreeC creates no additional subcontracting in the current or any subsequent periods. From Remark 3 and the fact that Step 2 always processes the tasks with the largest d values first, the condition that \(w \le L\) occurs no later than time \(t = \tau (L) +1\). Hence, subcontracting can occur only in periods \(1, \dots , \tau (L)\).

The selection of tasks to be processed follows Lemma 2 and Remark 4, by always selecting those available tasks at the highest level. As a result, the selection of tasks maximizes the amount of processing by the machines.

From Step 2, if subcontracting occurs first at time \(t'\), then this is the first time that \(\bar{d} = T-t' +1\) and \(\rho _{t'} > L\). Remark 3 shows that L tasks are processed in each period \(1, \dots , t'\). Step 2 continues to process L tasks each period until the number of available tasks \(w < L\). Since this occurs at a period no later than \(\tau (L)\), Lemma 1 establishes the optimality of the schedule found by Algorithm SubTreeC.

Step 1 calculates and stores all \(\tau (l)\) and \(\sum _{t=1}^{\tau (l)} \rho _t\) values for \(l = 1, \dots , T\) in O(n) time. Using binary search, the value of L can be found in \(O(\log n)\) time. Steps 2 and 3 are repeated \(T = O(n)\) times. Scheduling or subcontracting each task and updating the list of available tasks require O(n) time. If \(T \ge n\), the problem is trivial because \(L = 0\) when \(B \ge n\) and 1 otherwise. If \(T < n\), then the overall computation time of Algorithm SubTreeC is O(n). \(\square \)

To determine a schedule for Problem \(PS \, | \,chains, p_j = 1, r_j = 1, a_t, s_t \, | \,R_{\max }\), it is sufficient to specify the chains that are assigned resources by period.

If resources are assigned as in Step 2 of Procedure LSubChainS, then \({\bar{q}}_0 \ge {\bar{q}}_1 \ge \cdots \ge {\bar{q}}_T\).

Given \({\bar{a}}_i\) for \(i \in \{1, \dots , T\}\), if at each stage a maximum number of tasks are assigned to the longest chains, then any order of assignments provides the same assignments to the chains.

Because Procedure LSubChainS has the chains arranged in nonincreasing order of number of tasks without assignments, \({\bar{n}}_1 \ge \cdots \ge {\bar{n}}_{{\bar{q}}}\) where \({\bar{q}}\) is the current set of chains that have unassigned tasks.

Consider the assignment of tasks to two periods \(i_1\) and \(i_2\), where the task assignments are made for \(i_2\) directly after \(i_1\). Then, \(i_1\) assigns resources to chains \(1, \dots , {\bar{u}}_1\), and \(i_2\) assigns resources to chains \(1, \dots , r\) and \({\bar{u}}_1 +1, {\bar{u}}_1 +2, \dots , v\), where \(r \le {\bar{u}}_2\) and \(v = {\bar{u}}_1 +{\bar{u}}_2 -r\). If \(r < {\bar{u}}_2\), then the \(i_2\) assignments skip chains \(r+1, \dots , {\bar{u}}_1\). After the \(i_1\) assignments, skipping occurs only when these chains have fewer unassigned tasks than chains \({\bar{u}}_1 +1, {\bar{u}}_1 +2, \dots , v\). This happens only when \({\bar{n}}_r > {\bar{n}}_{r +1} = \cdots = {\bar{n}}_v\). If \({\bar{n}}_{r+h} > {\bar{n}}_{r+h+1}\) for some \(h \in \{1, \dots , v-r-1 \}\), then chain \(r+1\) would have been assigned.

If \(i_2\) selects chains directly before \(i_1\), then \(i_2\) selects the chains \(1, \dots , {\bar{u}}_2\) and \(i_1\) selects the chains \(1, \dots , \min \{r, {\bar{u}}_1 \}\) and \({\bar{u}}_2 +1, {\bar{u}}_2 +2, \dots , v\). Thus, the same assignments are made as when period \(i_1\) selects first.

By repeating a series of pairwise interchanges, any order of assignments result in the same selection of chains.  \(\square \)

Selecting jobs from the longest chains maximizes the number of chains that remain available in subsequent periods.

A feasible solution to constraints (2) and (3) exists if and only if \(\sum _{k \in \mathcal{T}} {\bar{u}}_k = n\).

Procedure LSubChainS finds an optimal schedule for Problem \(PS \, | \,chains, p_j = 1, r_j = 1, a_t, s_t \, | \,R_{\max }\) with L resources, when one exists in \(O(\max \{qT, q \log q, T \log T\})\) time.

Given L resources, McNaughton’s “wrap-around” procedure finds a feasible assignment for any set of chains where \(LT \ge n\) and \(T \ge n_h\) for \(h \in Q\). Consequently, the amount of subcontracting required is \(\gamma = \max \{n -LT, 0\}\). Remark 5 shows that tasks can be scheduled by period. The periods are selected in nondecreasing subcontracting cost order. Lemma 3 shows that this order does not restrict the feasible set in any way. Since available resources are independent by period, Remark 6 shows that scheduling least cost subcontracting periods first is desirable because these periods have the most chains with tasks that require scheduling. Selecting periods in nonincreasing cost order and scheduling as much subcontracting as can be used, minimizes the total cost. This satisfies the budget constraint (4), when a feasible solution exists for L resources.

At a given iteration \(k \in T\), \(u =\min \{ L +a_{i_k}, \; L +\gamma , \; q \}\) tasks are assigned resources and subcontracting. There are \(L +a_{i_k}\) units of resource and contracting available. Also, exactly \(\gamma \) tasks require subcontracting. In accordance with Lemma 3, the u chains with the greatest number of unassigned tasks are selected for processing. Finally, at the current iteration k, at most q chains can be serviced. As a result, the value of u for period \(i_k\) is the value of \({\bar{u}}_k\) found in (5). Lemma 4 shows that this process finds a feasible solution to \((P_{SC})\), when one exists.

To determine the computational effort, Step 1 requires \(O(q \log q +T \log T)\) time. Step 2 is called O(T) times and each application requires O(q) computation. Step 3 requires O(qT) time and is called only once. Hence, the overall computational time requirement of Algorithm LSubChainS is \(O(\max \{qT, q \log q, T \log T\})\).

An optimal schedule for problem \(PS \, | \,chains, p_j = 1, r_j = 1, a_t, s_t \, | \,R_{\max }\) can be found in \(O(\max \{qT, q \log q, T \log T\} \log q)\) time.

Lemma 5 establishes that for a given L, the minimum cost schedule can be found in \(O(\max \{qT, q \log q, T \log T\})\) time. Since there are q chains, \(0 \le L \le q\). Solve Procedure LSubChainS using a binary search on \(L \in \{1, 2, \dots , q\}\) to find the smallest L that has a total subcontracting cost no larger than B. This finds the optimal solution in \(O(\max \{qT, q \log q, T \log T\} \log q)\) time. \(\square \)

The recognition version of problem \(PS \, | \,inforest, p_j = 1, r_j = 1, s_t \, | \,R_{\max }\) is unary NP-complete.

By reduction from 3-Partition (Garey and Johnson 1979) in pseudopolynomial time.

The proof uses some ideas from Garey et al. (1983). However, the lack of a machine profile for our problem requires different arguments. Let \(K = 5m^2\). Consider an instance of problem \(PS \, | \,inforest, p_j = 1, r_j = 1, s_t \, | \,R_{\max }\), where the planning horizon is

\(T = Kmb -(3m^2 - 5m)/2\).

One machine is available to process tasks in periods \(1, \dots , T\). Thus, the threshold value of the objective is \(R_{\max } = 1\). The budget is

\(B = \sum _{i=1}^m (m - i + 1)[(Kb -1) +3(i-1)]\).

Define periods

\(t_1 = 1\),

\(t_{i+1} = t_i +Kb -3(m -i) +1, \; i = 1, \dots ,m-1\).

LetThe precedence structure is an inforest consisting of 3m intrees, where intree \(N_i\), for \(i \in \{1, \dots , 3m\}\), contains \(Kc_i\) tasks of level \(K c_i\) denoted as “Type \(1_i\)” tasks, and one task of each level \(K c_i -1, K c_i -2, \dots , 0\), which are denoted as “Type \(2_i\)” tasks and form a chain. All of the Type \(1_i\) tasks precede the level \(K c_i -1\) Type \(2_i\) task. Thus, \(n = 2Kmb\). The structure for a typical intree \(N_i\) is shown in Fig. 1.

Bild vergrößern

Bild vergrößern

We show that there exists a feasible solution to the above instance of \(PS \, | \,inforest, p_j = 1, r_j = 1, s_t \, | \,R_{\max }\) with subcontracting cost \(\le B\) if and only if there exists a solution to 3-Partition.

(\(\Rightarrow \)) Assume that there exists a solution to 3-Partition. Let the subsets that form this solution contain the following elements: \(S_1 = \{1,2,3\}, S_2 = \{4,5,6\}, \ldots , S_m = \{3 m-2, 3 m-1, 3 m\}\). Consider a schedule \(\sigma ^0\) constructed as follows. Schedule the \(Kc_1 +Kc_2 +Kc_3 = Kb\) Type \(1_1\), \(1_2\) and \(1_3\) tasks in period \(t_1\). This incurs cost \(m(Kb -1)\), since one task is scheduled on the machine and the other \((Kb -1)\) tasks are subcontracted. Schedule \(K c_i -(m - 1)\) Type \(2_i\) tasks, for \(i = 1, 2, 3\), in the time periods \(t_1+1, \dots , t_2 - 1\), one in each time period on the machine in their precedence order. Schedule the remaining \(3(m-1)\) Type \(2_i\) tasks, one of each type i in periods \(t_2, \ldots , t_m\), for \(i = 1,2,3\) in their precedence order. Next, schedule each set of three Type \(1_i\) tasks in the intrees \(N_{3i -2}, N_{3i -1}, N_{3i}\), for \(i = 2, \dots , m\) in period \(t_i\). Also, for \(i = 2, \dots , m-1\), schedule the first \(K c_i - (m-i)\) Type \(2_i\) tasks in periods \(t_i+1, \dots , t_{i+1} -1\), and schedule the remaining Type \(2_{3i-2}, 2_{3i-1}, 2_{3i}\) tasks one in each period \(t_{i+1}, \dots , t_m\). Finally, schedule the Type \(2_{3m-2}, 2_{3m-1}, 2_{3m}\) tasks one in each period \(t_m +1, \dots , T\). This schedule is shown in Fig. 2, where we use the format “\(N_i\) Type 1” to represent all the Type 1 tasks of intree \(N_i\) being processed concurrently, and the format “z \(N_i\) Type 2” to represent a subset of cardinality z of the Type 2 tasks of intree \(N_i\) being processed sequentially in their precedence order. As mentioned above, between times \(t_i\) and \(t_{i+1}\), for \(1 \le i \le m-1\), only one task is scheduled in each period.

Because the precedence order of each task is satisfied, the schedule is feasible. Further, intervals \(t_i+1, \ldots , t_i +Kb -3(m - i)\), for \(i = 1, \dots , m\), have only one task scheduled. Hence, no subcontracting is required and no cost is incurred at those times. However, at times \(t_i\), for \(i = 1, \dots , m\), there are \(Kb + 3(i -1)\) tasks scheduled, and therefore \((Kb-1) +3(i - 1)\) tasks are subcontracted. As a result, schedule \(\sigma ^0\) incurs a subcontracting cost of(\(\Leftarrow \)) Assume that there exists a feasible schedule \(\sigma \) to the above instance of problem \(PS \, | \,intree, p_j = 1, r_j = 1, s_t \, | \,R_{\max }\) where \(y_t\) denotes the number of tasks subcontracted in period t, for \(t = 1,\ldots ,T\), and \(\sum _{t=1}^T s_ty_t \le B\). Because there is only one machine and \(s_t = B+1\) for \(t \in {{\bar{V}}}\), schedule \(\sigma \) processes at most one task in these periods. Consequently, all subcontracting must occur in periods \(t_1, \dots , t_m\).

Suppose that less than Kb Type 1 tasks are processed in period \(t_1\). The inforest structure of the precedence constraints implies that there are at least \(Kb(m-1) +K\) Type 2 tasks unprocessed by the start of period \(t_2\). Since not more than one Type 2 task of the same intree can be processed in the same period, no more than \(3m(m-1)\) of these tasks can be processed in the \((m - 1)\) periods \(t_2, \dots , t_m\). Further, there are only \(Kb(m-1) - 3(m-1)(m-2)/2\) periods of \({{\bar{V}}}\) after period \(t_2\) that can process at most one task in a feasible schedule. Sinceno feasible solution is possible. This implies that at least Kb Type 1 tasks must be processed in period \(t_1\).

By a similar analysis, it can be shown that at least Kbi tasks must be processed in periods \(t_1, \dots , t_i \in V\). Below we use the fact that, if exactly Kb Type 1 tasks are processed in \(t_i \in V\), their cost isWe now show that an optimal schedule processes no more than Kb Type 1 tasks in period \(t_1\). First, we consider only Type 1 tasks that are subcontracted. Since \(s_i = B + 1\) for \(t_i \in \bar{V}\), this subcontracting occurs only in periods \(t_i \in V\). Suppose that for some \(i \in \{1, \dots , 3m\}\), the subcontracted Type \(1_i\) tasks are scheduled in multiple periods of V. Since none of the Type \(2_i\) tasks can be processed until all of the Type \(1_i\) tasks are completed, all of the Type \(1_i\) tasks can be feasibly processed in the last of these multiple periods of V without any change to the remainder of the schedule. Moreover, the strictly decreasing subcontracting costs imply that subcontracting all of Type \(1_i\) tasks in the last of these multiple periods reduces subcontracting costs. As a result, we assume that for \(i \in \{1, \dots , 3m\}\), the subcontracting set of Type \(1_i\) tasks occurs in one period.

Let \(J \subseteq \{1, \dots , 3m\}\) denote the set of indices of intrees where some Type 1 tasks are processed in \(t_1\). If more than Kb Type 1 tasks are processed in this period in an optimal schedule, then \(\sum _{i \in J} Kc_i \ge Kb +K\). If all of these Type 1 tasks are processed in period \(t_1\), then the cost of subcontracting grows by at least \((s_1 - \max _{ i \ge 2} \{s_i\})K = (s_1-s_2)K = K\). From (6), without using the periods of \(\bar{V}\), the subcontracting cost for the Type 1 tasks alone is \(m(m+1)(Kb-1)/2 +K > B\). Hence, schedule \(\sigma \) is infeasible. However, it may be possible to process some of the Type 1 tasks of \(\cup _{i \in J} N_i\) in the periods of \(\bar{V}\) to reduce the subcontracting cost. We now show that the cost reduction from using the intervals of \(\bar{V}\) is insufficient to satisfy the budget constraint.

Since there are 3m Type 2 chains and \(|V {\setminus } \{t_1\}| = m - 1\), it is not possible to subcontract more than \(3 m(m - 1)\) Type 2 tasks in the periods of \(V \setminus \{t_1\}\). Since \(|{\bar{V}}| = T -|V| = [Kmb -(3 m^2 - 5 m)/2] - m = Kmb -3(m^2 -m)/2\) and there are Kmb Type 2 tasks, the number of available periods of \({\bar{V}}\) to process Type 1 tasks is no larger than \(Kmb -3(m^2 -m)/2 - (Kmb - 3 m(m - 1)) = 3(m^2 - m)/2\). Consequently, at least \(Kb +K - 3(m^2 - 5 m)/2\) of the Type 1 tasks of \(\cup _{i \in J} N_i\) tasks must be processed in period \(t_1\), with a cost of \(m[Kb +K -3(m^2 - m)/2].\) The reduction in subcontracting cost is not more thanwhere the last term compares the cost of subcontracting in periods \(t_2\) and \(t_m\). As a result, the additional cost to process more than Kb tasks in period \(t_1\) is at leastHence, it is not optimal to process more than Kb tasks in this period.

A similar analysis can be presented to show that periods \(t_2, \dots , t_m\) cannot process more than Kb Type 1 tasks.

Finally, consider the intrees that provide exactly Kb Type 1 tasks at period \(t_i\), for \(i = 1, \dots , m\). It is shown above that these are the full sets of Type 1 tasks for a subset of the 3m given intrees. Then, since by assumption \(b/4< c_i < b/2, \; i = 1,\ldots ,3 m\), these represent all of the Type 1 tasks of exactly three intrees. It follows that the indices of these intrees form a solution to 3-Partition. \(\square \)