2 Mathematical formulation

Let I be the index set of n agents, J be the index set of n jobs and $J_1~(\subset J)$ be the index set of the Stage-1 jobs. Also, $\bar {J}_1=J \setminus J_1$ is the complement of $J_1$ and represents the index set of the Stage-2 jobs. The BiTSAP can be mathematically stated as

(2.1) $$ \begin{align} \min_{X=(Y,Z),~Y\in S, ~Z\in S(Y)} \quad (T(X),C(X)), \end{align} $$

where $C(X)$ is a nonlinear cost function, defined in terms of a feasible solution $X=\{x_{ij} \}$ of a TSAP. Here, the total completion time of a TSAP is

$$ \begin{align*}T(X)=T_1(Y)+T_2(Z),\end{align*} $$

where

$$ \begin{align*}T_1(Y)=\displaystyle \max_{I\times J_1} (t_{ij}:y_{ij}>0) \quad \text{and} \quad T_2(Z)=\displaystyle \max_{\bar{I}_1(Y)\times \bar{J}_1} (t_{ij}:z_{ij}>0).\end{align*} $$

Note that $t_{ij}$ is the time taken by the ith agent to complete the jth job and ${Y= \{y_{ij}\}_{i\in I, ~j\in J_1} \in S}$ , $Z= \{z_{ij}\}_{i\in I, ~j\in \bar {J}_1} \in S(Y)$ such that

$$ \begin{align*} S&=\left\{\begin{array}{@{}cc} Y=\{y_{ij}\} \in \mathbb{R}^{n\times n_1} \left | \begin{array}{l} \displaystyle\sum_{j \in J_1} y_{ij} \leq 1\quad \text{for all } i \in I\\[.2cm] \displaystyle\sum_{i \in I} y_{ij} = 1\quad \text{for all } j \in J_1\\ y_{ij}=0 ~{\textrm{or}}~ 1\quad \text{for all } (i,j) \in I \times J_1 \end{array} \right. \end{array} \!\!\!\!\!\!\right\} ,\\[6pt]S(Y)&= \left\{\begin{array}{@{}cc} Z=\{z_{ij}\} \in \mathbb{R}^{n\times (n-n_1)} \left | \begin{array}{l} \displaystyle\sum_{j \in \bar{J}_1} z_{ij} = 1\quad \text{for all } i \in \bar{I}_{1}(Y)\\[.2cm] \displaystyle\sum_{i \in \bar{I}_1(Y)} z_{ij} = 1\quad \text{for all } j \in \bar{J}_1\\ z_{ij}=0 ~{\textrm{or}}~ 1\quad \text{for all } (i,j) \in \bar{I}_1(Y) \times \bar{J}_1 \\ \end{array} \right. \end{array} \!\!\!\!\!\!\right\}, \end{align*} $$

where $I_1(Y)$ denotes the set of agents allocated to the jobs in $J_1$ corresponding to the feasible solution $Y\in S$ and $ \bar {I}_1(Y)=I \setminus I_1 (Y)$ . The decision variables $y_{ij}$ , $z_{ij}$ for $(i,j)\in I \times J$ take the value 1 if the ith agent performs the jth job and $0$ otherwise.

3 Preliminaries – finding the optimal total completion time of the TSTMAP

This section consists of a brief sketch of Algorithm 1, namely “Algorithm-Imp” developed by Jain et al. [Reference Jain, Dahiya, Sharma and Verma15] for finding an optimal total completion time of a TSTMAP. Throughout the paper, this has been used for solving a TSAP with respect to the total completion time wherever required in Algorithms 2 and 3 stated in Section 5.

Let $t_1^1<t_1^2< \cdots <t_1^{\kern1.1pt p}$ be the distinct time entries corresponding to Stage-1 jobs and $t_2^1<t_2^2< \cdots <t_2^q$ be the distinct time entries corresponding to Stage-2 jobs.

An optimal solution of the Stage-1 problem is obtained by solving the TMAP, $(TP)^1_0$ :

(3.1) $$ \begin{align} \begin{aligned} \displaystyle \min_{X\in S^*} \max_{I\times J} \quad &(t_{ij}':x_{ij}>0), \\ \text{where}\quad &t_{ij}'= \begin{cases} t_{ij}&\text{for all } (i,j)\in I\times J_1, \\[.1cm] 0&\text{for all } (i,j)\in I\times \bar{J_1}, \end{cases} \end{aligned} \end{align} $$

and $S^*$ is the feasible region of a standard assignment problem. Let the optimal value of the problem $(TP)^1_0$ (3.1) be $T_1=t^{m_1}_1,~1\leq m_1 \leq p$ . Then, $t^{m_1}_1$ is the minimum time of Stage-1.

Similarly, an optimal time of Stage-2 is obtained by solving the TMAP, $(TP)^2_0$ :

(3.2) $$ \begin{align} \begin{aligned} ~\displaystyle \min_{X\in S^*}\max_{I\times J}\quad & (t_{ij}':x_{ij}>0), \\ \text{where}\quad &t_{ij}'= \begin{cases} 0&\text{for all } (i,j)\in I\times J_1 , \\[.1cm] t_{ij}&\text{for all } (i,j)\in I\times \bar{J_1}. \end{cases} \end{aligned} \end{align} $$

Let the optimal value of the problem $(TP)^2_0$ (3.2) be $T_2=t^{m_2}_2,~1\leq m_2 \leq q$ . Then, $t^{m_2}_2$ is the minimum time of Stage-2.

Let $X^o$ be an optimal solution of $(TP)^2_0$ (3.2) yielding optimal value of $T_2$ as $T_2^o=t^{m_2}_2$ . Let $T_1^o$ be the corresponding time of Stage-1.

Thus, $(T^o_1, T_2^o)$ is the pair of Stage-1 and Stage-2 times obtained from the optimal solution $X^o$ of problem $(TP)^2_0$ (3.2), such that $T^o_2$ is the minimum time of Stage-2 corresponding to the Stage-1 time $T_1^o$ . The pair $(T^o_1, T_2^o)$ yields the total completion time of Stage-1 and Stage-2 jobs as $T_1^o+T_2^o$ .

The main steps of the algorithm for finding the optimal solution of the TSTMAP are provided in the following sections.

4 Notation and definitions

In this section, various notation and definitions are introduced to comprehend the solution technique for the problem BiTSAP (2.1).

4.2 Definitions

Definition 4.2 (Nodes arising from an assignment).

For an assignment $\alpha =((b_1,c_1)$ , $(b_2,c_2)$ ,…, $(b_n,c_n))$ of a TSAP, define the nodes $N_1,N_2,\ldots ,N_{n-1}$ arising from assignment “ $\alpha $ ” as nonempty mutually exclusive subsets of A as

$$ \begin{align*} N_1 &=\{ \overline{(b_1,c_1)}\} , \quad N_2 =\{ (b_1,c_1),\overline{(b_2,c_2)} \} , \end{align*} $$

$$ \begin{align*} \cdots &\qquad \qquad \cdots \qquad \qquad \cdots \qquad \cdots \qquad \cdots \\ N_{n-1} &=\{ (b_1,c_1),(b_2,c_2),\ldots,(b_{n-2},c_{n-2}),\overline{(b_{n-1},c_{n-1})}\}, \end{align*} $$

where $N_r$ is the set of assignments in all of which $(b_1,c_1),(b_2,c_2), \ldots ,(b_{r-1},c_{r-1})$ are allocated and $(b_r,c_r)$ is nonallocated. In other words, for any ${r=1,2,\ldots , n-1}$ , $(b_k,c_k)\in N_r$ means that $x_{{b_k}{c_k}}=1$ and $\overline {(b_k,c_k)}\in N_r$ means that $x_{{b_k}{c_k}}=0$ for all assignments in $N_r$ . Clearly, $A=\{\alpha \} \cup (\bigcup _{r=1}^{n-1} N_r )$ . Note that any pair of job-person that is not listed in a node can be chosen freely, provided the resulting assignment satisfies the feasibility conditions pertaining to the TSAP.

Definition 4.3 (Partitioning of a node by its optimal assignment).

Let N be a node and $\alpha _N$ be its optimal time assignment defined as

$$ \begin{align*}N= \{ (b_1,c_1),(b_2,c_2),\ldots ,(b_s,c_s),\overline{(p_1,q_1)},\overline{(p_2,q_2)},\ldots ,\overline{(p_t,q_t)} \},\end{align*} $$

$$ \begin{align*}\alpha_N= ((b_1,c_1),(b_2,c_2),\ldots ,(b_s,c_s),(u_1,v_1),(u_2,v_2),\ldots ,(u_{n-s},v_{n-s}) ).\end{align*} $$

Define partitioning of N by its optimal assignment $\alpha _N$ into nodes $N_1, N_2,\ldots , N_{n-s-1}$ :

$$ \begin{align*} N_1 &=\{ (b_1,c_1),(b_2,c_2),\ldots ,(b_s,c_s),\overline{(p_1,q_1)},\overline{(p_2,q_2)},\ldots ,\overline{(p_t,q_t)}, \overline{(u_1,v_1)} \}, \\ N_2 &=\{ (b_1,c_1),(b_2,c_2),\ldots ,(b_s,c_s),\overline{(p_1,q_1)},\overline{(p_2,q_2)},\ldots ,\overline{(p_t,q_t)}, (u_1,v_1), \overline{(u_2,v_2)} \} , \\ \cdots &\qquad \qquad \cdots \qquad \qquad \cdots \qquad \cdots \qquad \cdots\\ N_{{n-s-1}} &=\{ (b_1,c_1),\ldots ,(b_s,c_s),\overline{(p_1,q_1)},\ldots ,\overline{(p_t,q_t)}, (u_1,v_1), (u_2,v_2),\ldots , \overline{(u_{n-s-1},v_{n-s-1})} \}. \end{align*} $$

Clearly, $N=\{\alpha _N\} \cup ( \bigcup _{r=1}^{n-s-1} N_r )$ .

Definition 4.4 (Efficient solution).

A solution $X^*=(Y^*,Z^*)$ , $Y^*\in S$ , $Z^*\in S(Y)$ is said to be an efficient solution of BiTSAP (2.1) if and only if there does not exist another solution $\hat {X}=(\hat {Y},\hat {Z})$ , $\hat {Y}\in S$ , $\hat {Z}\in S(Y)$ , such that (i) $T(\hat {X}) \leq T(X^*)$ , (ii) $C(\hat {X}) \leq C(X^*)$ , with strict inequality holding for at least one of the relations (i) and (ii).

Definition 4.5 (Efficient pair or nondominated pair).

A time-cost pair $[T(X^*),C(X^*)]$ corresponding to an efficient solution $X^*$ of BiTSAP (2.1) is said to be an efficient pair or nondominated pair of a BiTSAP.

Definition 4.6 (Dominated pair).

A pair $[T(X),C(X)]$ that is not an efficient pair is termed as a dominated pair. In other words, a pair $[T(X),C(X)]$ is dominated by another pair $[T(X^*),C(X^*)]$ if $T(X^*)\leq T(X)$ and $C(X^*)\leq C(X)$ with strict inequality holding for at least one of the relations.

5 Algorithms

This section consists of two algorithms that jointly solves the BiTSAP (2.1). First, Algorithm 2 (namely, “Algorithm-R&S”) is proposed that ranks and scans all feasible assignments of a TSAP in order of increasing total completion time. Next, Algorithm 3 (named as “Algorithm-Eff”) is presented that is used for finding efficient time-cost pairs of BiTSAP (2.1).

6 Theoretical justification

In this section, various results are proved which provide theoretical validation of the algorithms proposed in Section 5.

Lemma 6.1. In the sequence of generated efficient pairs $[T^e(h),C^e(h)]$ , $h=1,2,\ldots ,h_l$ , the following hold true

$$ \begin{align*} C^e(1)>C^e(2)>\cdots>C^e(h_l), \\ T^e(1)<T^e(2)<\cdots<T^e(h_l). \end{align*} $$

Proof. Let, if possible, $[\hat {T}^e, \hat {C}^e]$ be an efficient pair obtained from a feasible solution $\hat {X}$ of BiTSAP (2.1) which has not been recorded by the algorithm

$$ \begin{align*}\Rightarrow [\hat{T}^e, \hat{C}^e] \neq [T^e(h), C^e(h)]\quad{\textrm{for ~any~}} h=1,2,\ldots,h_l.\end{align*} $$

Then, by construction of efficient pairs, it is clear that

(6.1) $$ \begin{align} [\hat{T}^e, \hat{C}^e] \neq [T(k), C(k)]\quad{\textrm{for ~any~}} k=1,2,\ldots,k_l. \end{align} $$

Since Algorithm 2 scans the complete set of feasible assignments of a TSAP,

$$ \begin{align*} &\hat{T}^e= T(\hat{k})~{\textrm{for~some~}} \hat{k}\in \{1,2,\ldots,k_l \} \\ &\Rightarrow \hat{X} \in A(\hat{k}), {\textrm{and~}} \hat{C}^e \neq C(\hat{k}) ~({\textrm{using~(6.1)}}).\\ &{\textrm{Also,~}} C(\hat{k}) = \min \{ C(\alpha)\mid \alpha \in A(\hat{k}) \} \\ &\Rightarrow C(\hat{k}) < \hat{C}^e. \end{align*} $$

This implies that $[\hat {T}^e,\hat {C}^e]$ is dominated by $[T(\hat {k}),C(\hat {k})]$ , which is a contradiction to the assumption that $[\hat {T}^e,\hat {C}^e]$ is an efficient pair. This completes the proof.

7 Numerical illustration

Consider a BiTSAP dealing with an allocation of five contractors, represented by $B_i,~i=1,2,\ldots ,5$ to five jobs, represented by $W_j, j=1,2,\ldots ,5$ out of which $W_1$ and $W_2$ are Stage-1 jobs (corresponding time entries are shown in bold and underlined), whereas $W_3$ , $W_4$ and $W_5$ are Stage-2 jobs. Table 1 provides the time “ $t_{ij}$ ” (in days) that the ith contractor takes to complete the jth job for all $i,j=1,2,\ldots ,5$ . The BiTSAP aims at minimizing the following nonlinear cost function $C(X)$ (in terms of thousands of dollars) and total completion time $T(X)=\min \max \{t_{ij}\mid ~i\in I,~ j\in J\}$ , where

$$ \begin{align*} C(X)&=\begin{cases} 17x_{11}+60x_{12}+27x_{13}+38x_{14}+26x_{15}+27x_{21}+30 x_{22}+31x_{23}+\\ 44x_{24}+35x_{25}+11x_{31}+20x_{32}+16x_{33}+14x_{34} +26x_{35}+30x_{41}+\\ 32x_{42}+ 25x_{43}+19x_{44}+14x_{45}+ 20x_{51}+30x_{52}+31x_{53} +29x_{54}+\\ 28x_{55} +12x_{14}x_{21}+09x_{14}x_{31}+ 05x_{32}x_{45}+ 04x_{41}x_{52}- (03x_{12}x_{21}+\\04x_{13}x_{31}+05x_{14}x_{41}+06x_{15}x_{51}+05x_{23}x_{32}+07x_{34}x_{43}+08x_{35}x_{53}+ \\ 09x_{45}x_{54})- 07x_{23}x_{11}x_{52} - 08 x_{22}x_{33}x_{44}. \end{cases} \end{align*} $$

Table 1

Time entries $t_{ij}$ .

The fixed cost charges (in thousands of dollars) of performance of a job by each contractor are presented by the coefficients of the linear terms in the expression of cost function $C(X)$ . In addition, other circumstances and constraints imposed by various contractors give rise to nonlinear terms in the expression for the cost function, like the additional cost of 12 (thousand dollars) charged by the contractor $B_1$ for performing the $W_4$ job if $B_2$ is performing the $W_1$ job that gives rise to the term “ $12 x_{14} x_{21}$ ” in the cost function $C(X)$ . Similarly, $B_1$ charging a cost of 09 (thousand dollars) for the $W_4$ job if $B_3$ performs the $W_1$ job, adds the term “ $09 x_{14} x_{31}$ ” in $C(X)$ . Likewise, the term $-07 x_{23} x_{11} x_{52}$ is attributed to the concession in cost of performance of job $W_3$ by 07 (thousand dollars) provided by contractor $B_2$ if the jobs $W_1$ and $W_2$ are performed by the contractors $B_1$ and $B_5$ , respectively. Other nonlinear terms in $C(X)$ are attributed in a similar manner. The aim is to find all efficient time-cost pairs for the given BiTSAP.

Solution. First of all, let us rank and scan the complete set of feasible assignments of a TSAP in order of increasing total completion time using Algorithm 2. For this, find the minimum total completion time $T(1)$ and corresponding optimal assignment $\alpha _1$ for the TSAP using the technique provided by Jain et al. [Reference Jain, Dahiya, Sharma and Verma15].

The minimum total completion time of the given two-stage problem is ${T(1)=(T_{S1}(1)=05,T_{S2}(1)=03)=08}$ , and the corresponding optimal assignment is

$$ \begin{align*}\alpha_1=\{(1,1),(2,3),(3,5),(4,4),(5,2)\}.\end{align*} $$

The partial set of assignments giving the total completion time as $T(1)$ is

$$ \begin{align*}\mathscr{P}A(1)=\{\alpha_1\}.\end{align*} $$

We construct mutually exclusive nonempty subsets from $\alpha _1$ , and find the optimal assignment and minimum total completion time for the corresponding two-stage assignment problem:

$$ \begin{align*} N_1&=\{\overline{(1,1)}\}, \; \;T_{N_1}=15, \;\;\alpha_{N_1}=\{(1,3),(2,2),(3,4),(4,1),(5,5)\} ,\\ N_2&=\{(1,1),\overline{(2,3)}\}, \;\;T_{N_2}=12,\,\, \alpha_{N_2}=\{(1,1),(2,2),(3,3),(4,4),(5,5)\} ,\\ N_3&=\{(1,1),(2,3),\overline{(3,5)}\},\;\; T_{N_3}=12, \;\;\alpha_{N_3}=\{(1,1),(2,3),(3,2),(4,4),(5,5)\}, \\ N_4&=\{(1,1),(2,3),(3,5),\overline{(4,4)}\},\;\; T_{N_4}=41,\;\; \alpha_{N_4}=\{(1,1),(2,3),(3,5),(4,2),(5,4)\}. \end{align*} $$

Here,

$$ \begin{align*}\mathscr{N}=\{N_1,N_2,N_3,N_4\}, \; \; \xi=\{N_1,N_2,N_3,N_4\}\quad\text{and}\quad \displaystyle \min_{N\in \xi} T_N=12>T(1).\end{align*} $$

This implies that all feasible assignments of the TSAP having a corresponding total completion time as $T(1)$ have been found and are given by $A(1)=\{\alpha _1\}$ . Next, to determine $A(2)$ , we find $\displaystyle \min _{N\in \mathscr {N}} \{T_N\mid T_N> T(1) \}=12=T(2)$ . With

$$ \begin{align*}\mathscr{N}(2)=\{N_2,N_3\}\quad\text{and}\quad \mathscr{P} A(2)=\{\alpha_{N_2},\alpha_{N_3}\},\end{align*} $$

we set $\xi (2)=\mathscr {N}(2)$ and partition each node of $\xi (2)$ by its optimal assignment. Partitioning $N_2$ by $\alpha _{N_2}$ , we have

$N_{21}=\{(1,1), \overline {(2,3)}, \overline {(2,2)}\}$ , $\alpha _{N_{21}}=\{(1,1),(2,5),(3,2),(4,4),(5,3)\}$ and $T_{N_{21}}=20$ ,

$N_{22}\kern-1pt =\kern-1pt \{(1,1), \overline {(2,3)},(2,2), \overline {(3,3)}\}$ , $\alpha _{N_{22}}\kern-1pt =\kern-1pt \{(1,1),(2,2),(3,5),(4,4),(5,3)\}$ and $T_{N_{22}}\kern-1pt =\kern-1pt 15$ ,

$N_{23}=\{(1,1), \overline {(2,3)},(2,2),(3,3),\overline {(4,4)}\}$ , $\alpha _{N_{23}}=\{(1,1),(2,2),(3,3),(4,5),(5,4)\}$ and $T_{N_{23}}=26$ .

Next, we partition $N_3$ by $\alpha _{N_3}$ :

$N_{31}\kern-1pt =\kern-1pt \{(1,1), (2,3), \overline {(3,5)}, \overline {(3,2)}\}$ , $\alpha _{N_{31}}\kern-1pt =\kern-1pt \{(1,1),(2,3),(3,4),(4,5),(5,2)\}$ and $T_{N_{31}}\kern-1pt =\kern-1pt 15$ ;

$N_{32}=\{(1,1), (2,3), \overline {(3,5)},(3,2), \overline {(4,4)}\}$ , $\alpha _{N_{32}}=\{(1,1),(2,3),(3,2),(4,5),(5,4)\}$ and $T_{N_{32}}=26$ .

Here, $\xi =\{N_{21},N_{22},N_{23},N_{31},N_{32}\}$ , then $\displaystyle \min _{N\in \xi } T_N=15>T(2)$ .

Therefore, all feasible assignments having a total completion time as $T(2)$ have been found and are given by $A(2)=\{\alpha _{N_2},\alpha _{N_3}\}$ . Similarly, find all ranked total completion times of the TSAP and obtain the corresponding nodes and feasible assignments.

Table 2 provides the list of all completion times of the TSAP in increasing order of time value, the corresponding set $\mathscr {N}_A(k)$ of all nodes possible with total completion time $T(k)$ and the corresponding value of cost function $C(k)$ , which is the minimum of the cost values for optimal assignments of all nodes with total completion time $T(k)$ .

Table 2

Ranking and scanning of the given TSAP.

Note that $T(19)=50$ is the last completion time when ranking of the feasible assignment with respect to the total completion is done in increasing order. It follows that $T(19)=50$ is actually the maximum possible total completion time of the TSAP.

Next, we find efficient time-cost pairs of a BiTSAP using Algorithm 3.

Find $C(1)=\min \{C(\alpha _1)\}=\min \{116\}=116$ .

Therefore, $[T(1),C(1)]=[08,116]=[T^e(1),C^e(1)]$ is the first efficient pair and the corresponding assignment $\{(1,1),(2,3),(3,5),(4,4),(5,2)\}$ is an efficient solution to the given BiTSAP.

Next, $C(2)=\min \{C(\alpha _{N_2}), C(\alpha _{N_3})\}=\min \{102,110\}=102$ .

Since $C(2)<C(1)$ , $[T(2),C(2)]$ is the next efficient pair.

Thus, the second efficient pair is $[T^e(2),C^e(2)]=[T(2),C(2)]=[12,102]$ .

The corresponding second efficient assignment is $a_{N_2}=\{(1,1),(2,2),(3,3),(4,4), (5,5)\}$ .

Next, $C(3)=\min \{C(\alpha ):\alpha \in A(3)\}=99<C(2)$ and it corresponds to the assignment

$\{(1,1),(2,3),(3,4),(4,5),(5,4)\}$ .

Therefore, we get the third efficient assignment and $[T^e(3),C^e(3)]=[T(3),C(3)]=[15,99]$ .

Further, $C(4)=121>C(3)$ , thus $(T(4),C(4))$ is dominated by $[T(3),C(3)]$ and is not an efficient time-cost pair.

Proceeding in a similar manner, the next efficient pair obtained is

$$ \begin{align*} [T^e(4),C^e(4)]=[T(9),C(9)]=[26,97] \end{align*} $$

and the corresponding assignment is $\{(1,1),(2,2),(3,3),(4,5),(5,4)\}$ . After this, no efficient pair is obtained. Thus, all efficient time-cost pairs for the BiTSAP are

$$ \begin{align*}[08,116], [12,102], [15,99], [26,97].\end{align*} $$

8 Complexity of Algorithm-R&S

Algorithm 2 explores ranking and scanning of feasible assignments for the TSTMAP by branching of nodes corresponding to a specified total completion time of the problem and solving the TSTMAP corresponding to each constructed node. Sizes of these problems (TSTMAPs) solved at each node vary from 2 to n depending upon the level of the node. The level of a node $N_{\gamma }$ (say) refers to the number of times a Level- $0$ node is partitioned to obtain $N_{\gamma }$ . That is, a node is termed as a Level-L node if it is obtained by partitioning a Level- $0$ node “L” number of times. Note that the node corresponding to an optimal solution of the TSTMAP is marked as a Level-0 node. For example, in the numerical example stated in Section 7, the node corresponding to an optimal solution ( $\alpha _1$ ) can be marked as a Level-0 node and its partitioning leads to $(n-1)$ nodes (nodes $N_1,\ldots , N_4$ ) having sizes 2 to n. All these nodes are referred to as Level-1 nodes and these are stored in a set ( $\mathcal {N}$ ). For further scanning of the feasible solutions, one or more nodes from Level-1 are picked for partitioning (depending on the minimum value of $T(X)$ for the TSTMAP corresponding to that particular node and the existence of alternate solutions), which results in the formation of Level-2 nodes. In the numerical example, partitioning of Level-1 node $N_2$ yields three nodes $N_{21}, N_{22}$ and $N_{23}$ , and these are Level-2 nodes. The set $\mathscr {N}$ is then updated to contain all Level-1 and Level-2 nodes, and partitioning is continued.

For further partitioning, one or more nodes corresponding to the minimum value of $T(X)$ are selected out of the nodes of $\mathcal {N}$ and the partitioning process is executed. Note that either the size of the TSTMAP or the number of feasible links $(i,j)$ reduces as the level of the partitioning node increases. Therefore, the total number of nodes that can be formed is finite and the termination of partitioning is certain. At each node, the corresponding TSTMAP is solved by the iterative algorithm proposed by Jain et al. [Reference Jain, Dahiya, Sharma and Verma15] having polynomially bound complexity of the order of $O( \lfloor {n/2} \rfloor n^3 \sqrt {n \log n})$ , where $ \lfloor {n/2} \rfloor $ denotes the greatest integer less than or equal to $n/2$ . An optimal assignment is noted on the basis of which further partitioning is executed. It can be observed that for finding the Kth ranked assignments of the TSTMAP, the number of problems (TSTMAPs) solved is equal to the total number of nodes constructed till the step where it is declared that all possible assignments that could yield total completion time $T(K)$ have been obtained. The number of nodes is associated with the number of times branching is done. It can be observed from the Algorithm-R&S that the branching process depends on the given data of the problem in terms of the time entries “ $t_{ij}$ ” and therefore varies with the change in time entries of the problem.

In general, in a standard assignment problem, there are $n!$ assignments in total, which is a very big number [Reference Dantzig10] and increases rapidly as n increases. Ranking and scanning of feasible assignments of the TSTMAP of size “n” precisely means enumerating the $n!$ assignments in increasing order of total completion time and scrutinizing all possible alternate assignments as well. However, while scanning the feasible set for finding the Kth optimal assignments, Algorithm 2 discards a large number of nodes and consequently a large number of assignments, all of which are sure to possess a total completion time greater than $T(K)$ . Hence, the branching technique explored in Algorithm 2 is computationally efficacious for determining ranked assignments of a TSTMAP. It should be noted that the computational load increases as the value of K increases where scanning of the $1$ st optimal assignments require the least computational efforts.

The proposed algorithm has been coded in MATLAB on a 64-bit operating system, 4-GB RAM, i3 processor and tested with the help of a variety of randomly generated problems. The algorithm runs successfully for test problems with sizes varying from 4 to 10 and $t_{ij}$ varying from 1 to 30. The number of problems solved for obtaining the Kth optimal assignments ( $K=1,2,3$ ) is noted in each case. Results show that in most of the cases, the number of problems solved to obtain the Kth optimal solution increases with the increase in the size of the problem, and hence the computational time increases with the increase in the size of the problem. It should be noted that each problem solved yields a unique feasible assignment of the TSAP (because of the mutual exclusiveness of the nodes). Therefore, we can say that the number of problems solved is equal to the number of feasible assignments explored. Table 3 provides the results obtained as an outcome of the numerical experiments in terms of the percentage of feasible assignments explored for obtaining the Kth optimal solution for different values of n. If $\eta $ represents the percentage of feasible assignments (out of the total number of $n!$ assignments) explored, then from Table 3, we see that for each instance of n, $\eta $ increases as K increases. In addition, in each instance of n, $\eta $ is small and it decreases rapidly as n increases. Likewise, for obtaining all possible $3$ rd optimal assignments, $\eta $ drops from 37 % for $n=4$ to 0.001 % for $n=10$ . This is because as n increases, the total number of assignments (which is $n!$ ) increases quite rapidly. All these results show that the proposed algorithm is quite efficient in terms of computational performance.

Table 3

Results of numerical experiments.

9 BiTSAP with a minimization and a maximization objective

This section describes a modification in Algorithm 3 that can efficiently tackle a bi-objective TSAP dealing with one minimization objective and the other a maximization objective. Consider a BiTSAP in which the objective is to minimize the total completion time ( $T(X)$ ) and maximize the cost objective function ( $C(X)$ ). Practically, maximization of the cost objective function can be visualized as maximization of profit, dividend, efficiency etc.

In this case, the BiTSAP takes the form $\mathrm{BiTSAP}^c$ :

(9.1) $$ \begin{align} \begin{split} \min_{X=(Y,Z),~Y\in S,~Z\in S(Y)} (T(X)), \\ \max_{X=(Y,Z),~Y\in S,~Z\in S(Y)} (C(X)), \end{split} \end{align} $$

where S and $S(Y)$ are same as defined in Section 2. Since $C(X)$ is now required to be maximized, the definition of an efficient solution for BiTSAP $^c$ (9.1) takes the following form.

The corresponding time-cost pair $[T(X^*),C(X^*)]$ is termed as an efficient pair of BiTSAP $^c$ (9.1).

In this case, $C(k)$ is defined as $C(k)=\max \{C(\alpha )\mid \alpha \in A(k)\}$ for $k=1,2,\ldots $ .

Efficient pairs for BiTSAP $^c$ (9.1) can be obtained using Algorithm 3 with a modification to Step G(ii).

Modified G(ii) (for BiTSAP $^c$ ). Set $k=\hat {k}$ . Find $T(k+1)$ and $A(k+1)$ using Algorithm-R&S. Next, find $C(k+1)=\max \{C(\alpha )\mid \alpha \in A(k+1)\}$ . If $C(k+1) \leq C(\hat {k})$ , then $[T(k+1),C(k+1)]$ is dominated by $[T(\hat {k}),C(\hat {k})]$ . Repeat Step G(ii) by updating $k=k+1$ .

However, if $C(k+1)> C(\hat {k})$ , then $[T(k+1),C(k+1)]$ is the next efficient pair $[T^e(h+1),C^e(h+1)]$ .

10 Concluding remarks

• • The paper addresses a BiTSAP that aims at minimizing two objective functions simultaneously. One objective function is a nonlinear cost function, defined explicitly in terms of assignment variables, and the other is the total completion time of all jobs in a two-stage assignment process.

• • An algorithm (Algorithm 3) for finding all efficient time-cost pairs of the BiTSAP has been proposed. The proposed algorithm is based on ranking and scanning all feasible assignments in order of increasing total completion time and then obtaining the value of the cost objective function corresponding to ranked feasible assignments.

• • For ranking and scanning the feasible assignments in order of total completion time, a systematic branch and bound technique (Algorithm 2) has been developed in the paper.

• • A large number of nodes are formed while branching for ranking of assignments in order of increasing total completion time. We would like to develop a more efficient technique for solving such a bi-objective two-stage assignment problem.

• • Bi-objective multistage assignment problems and multi-objective two-stage assignment problems emerge as interesting open problems from the current study.