# Task Scheduling for Multiunit Parallel Test Using Mixed-Integer Linear Programming

Authors: Zhao Yang; Han-Shan Xiao; Rui Guan; Yang Yang; Hong-Liang Ji
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Parallel test is an efficient approach for improving test efficiency in the aerospace field. To meet the challenges of implementing multiunit parallel test in practical projects, this paper presented a mixed-integer linear programming (MILP) model for solving the task scheduling problem. A novel sequence-based iterative (SBI) method is proposed to solve the model in reasonable time. The SBI method is composed of an implied sequence finding procedure (ISF) and a sequence-based iterative optimization (SBIO) procedure. The first procedure can reduce the search space by fixing free sequence variables according to the original test flowcharts, and the second procedure can solve the model iteratively in a reasonable amount of time. In addition, two indexes, namely, speed rate and average resource utilization rate, are introduced to evaluate the proposed methods comprehensively. Computational results indicate that the proposed method performs well in real-world test examples, especially for larger examples that cannot be solved by the full-space method. Furthermore, it is proved that the essence of the parallel test is trading space for time.


---

## Body

## 1. Introduction

In the aerospace field, test is an essential procedure in the manufacturing of aircraft, missiles, and satellites to guarantee the functional integrity. Every piece of equipment is a system of multiple relatively independent subsystems. When testing a system, every subsystem must pass some specific test items. In the test field, the relatively independent subsystem to be tested is called the unit under test (UUT), and the corresponding test items are called test tasks. Traditionally, the UUTs of an aerospace equipment will be tested sequentially [1, 2] using an automatic test system (ATS), which provides the necessary resources for test tasks. Sequential test methods are time-consuming [3] because of the unit-by-unit and task-by-task strategy. With the increase of test workload, sequential test severely restricts the efficiency of equipment support. Therefore, implementing parallel test is becoming highly desirable in the aerospace field [1, 4]. Parallel test means that multiple UUTs can be tested at the same time and that multiple test tasks can be performed at the same time, which can improve test efficiency without increasing the cost [4, 5].However, implementing parallel test in projects is challenging due to several practical difficulties [1]. First, resource competition can occur because test resources in an ATS are limited under the volume and budget constraints. Commonly, there are few spare resources in an ATS, and the test tasks must be scheduled elaborately with a minimum test resource set. Second, most instrument resources can be controlled by only one software thread at a time, which leads to a task’s exclusive occupation of relevant resources and threads. In the parallel test, tasks are assigned to multiple parallel software threads, with each thread performing some of the test tasks. Therefore, thread competition will occur among tasks that are assigned to the same thread. Third, the UUTs must be tested according to test flowcharts, which are strictly determined by the technical sequences and working principles. These difficulties lead to a complex NP-hard tasks scheduling problem [6, 7] that involves up to hundreds of decision variables.Although task scheduling for multiunit parallel test is important in the aerospace test field, limited solutions have been proposed due to the difficulties that are mentioned above. Xin et al. [3] established a relation model of test tasks based on graph theory and proposed two algorithms based on graph coloring, whose correctness and feasibility were proved by both theory and simulation. Xiao and Wang [8] proposed a vertex partitioning algorithm, which was derived from graph theory to coordinate system resource conflicts and time precedence. Xia et al. [9] combined the genetic algorithm and the simulated annealing algorithm to find the multi-UUT test task array. Li [10] built a mathematical model for the parallel test system with multi-UUTs and resource constraints and solved the model using genetic algorithm. Grey and Elizalde [11] proposed a method for performing multiple tests on one or more units by dynamically searching next executable test task. Lu et al. proposed two multiobjective evolutionary algorithms based on decomposition [12, 13] for test task scheduling problem, both of which considered two minimization objectives that were the test makespan and the mean resource workload. Zhang et al. [14] improved the basic ant colony algorithm to solve the parallel test task scheduling problem and to obtain the task execution sequence with shortest test time. In reference [15], a hybrid algorithm which combined the advantages of genetic algorithm and greedy algorithm was proposed for the parallel test task scheduling problem, and the chromosome coding and crossover in genetic algorithm were improved. Dorronsoro and Pinel [16] proposed a new accurate and fast memetic parallel optimization algorithm for the independent tasks scheduling problem, which combined the virtual savant optimization framework with a parallel genetic algorithm. Zhang et al. [17] developed an optimization model that jointly considered the preventive maintenance policy and the operating unit number for the multiunit parallel production system. Kim and Kim [18] constructed an intelligent task scheduler to improve the performance and energy efficiency in a heterogeneous multicore environment.However, the abovementioned works are not very practical when dealing with real-world test projects. Xin et al.’s [3] algorithm cannot be applied to large-scale problems because it is an enumeration method by nature. Xiao and Wang [8] do not consider dynamic test task addition and deletion; therefore, their approach is not flexible in real-world applications. In test tasks scheduling problem, test flowcharts mean predefined constraints for candidate solutions. In the works of references [9, 10, 14, 15], only simple time precedence of tasks is allowed, and it is difficult to generate legal chromosomes for the genetic algorithm, or legal candidate ant for the ant colony algorithm when considering test flowcharts. Autoscheduling method of Grey and Elizalde [11] allows the parallel execution of multiple tests by a given order without resource confliction, which means that it cannot optimize the test sequence from a global perspective. The two multiobjective evolutionary algorithms by Lu et al. [12, 13] perform well in experiment examples, but both of them supposed that the test start time and the test completion time for every test task were fixed, which means the test execution sequence cannot be optimized. The optimization algorithm for the independent tasks in reference [16] can get an accurate solution in a short computation time; however, it did not take the test flowchart into consideration. Models and methods in references [17, 18] did not take the diversity of tasks and the task-resource matching problem into consideration.Task scheduling in multiunit parallel test is similar to scheduling problems in other domains [19–21]. For example, a farmer must optimize the use of land by selecting the best mix of crops to cultivate [22] and consider several factors simultaneously including market price variability, specific resource requests for each crop, machine availability restrictions, and timing of cultivation. Another example [23] is the creation of master theatre timetables in hospitals, which takes account of the goal of reducing the maximum number of beds that are required, surgeons’ availability and preferences, variations in types of theatre, and so on. Although these problems differ in the details, the related models and approaches are inspiring to task scheduling of multiunit parallel test. To overcome the challenges mentioned above, this paper studies the task scheduling problem in multiunit parallel test and makes the following contributions:(1)
An MILP model that describes the resource competition and thread competition mathematically in multiunit parallel test is constructed. The resource competition and thread competition are described by introducing sequence variables.(2)
A novel SBI method is proposed for solving the MILP model. The SBI method includes two procedures: ISF and SBIO. The ISF procedure can reduce the search space by fixing free sequence variables according to the original test flowcharts, and the SBIO can solve the model in a reasonable amount of time.(3)
The proposed SBI method allows tasks to be added conveniently according to practical requirements. When the test flowchart changes, the project manager can simply “insert” the tasks to obtain a new optimal schedule without reoptimizing the whole problem, which minimizes the effort required to modify the test software.The proposed test task scheduling method can be applied to develop a new ATS or improve the performance of an existing ATS without adding new test resources. In addition, the difficulty of multithread programming will be reduced because the thread competition is solved by the proposed method. These advantages make the proposed method more practical and valuable in real-world test projects.This paper is organized as follows. In Section2, a motivating example is presented to illustrate the concept of parallel test. In Section 3, an MILP model is built to optimize the test time of tasks for multiple UUTs. In Section 4, the SBI method for solving the proposed model is developed. Section 5 studies 7 real-world test examples to evaluate the efficiency of the proposed SBI method. Finally, conclusions and suggestions for future research are provided in Section 6.


## 2. Motivating Example

To illustrate the idea of multiunit parallel test, an example of 2 UUTs with 6 test tasks, which involve 4 types of resources, is demonstrated. The required resources and expected test times (test durations) of the 6 test tasks are given in Table1. The prerequisite test sequences, which are determined by the working principle of the corresponding UUT, are shown in Figure 1.Table 1
Required resources and expected test times of the 2 UUTs.
UUTTest taskRequired resourcesTest time (seconds)r1r2r3r4UUT1t1110030t2001020t3000120UUT2t4001130t5100020t6010020Figure 1
Test flowcharts of UUT1 and UUT2.As shown in Table1, some tasks use the same test resource, such as t1 and t5, as well as t2 and t4. Currently, due to the uniqueness of the resource state, two tests that use the same resource cannot be performed simultaneously. Figure 1 shows the test flowcharts of UUT1 and UUT2, which specify the prerequisite technological sequences. Tasks t1 and t2 must finish before t3 begins, and t4 must finish before t5 and t6 begins.Figure2(a) illustrates the concept of sequential test. In the sequential test method, all the test tasks are executed one by one using only one software thread. Resource competition does not occur and the test sequence is not violated. However, the total test time is long (140 s) and equals the sum of the test times of all tasks. Figure 2(b) illustrates the concept of multi-UUT  parallel test, which can reduce the test time by 50% (70 s) with 3 threads. Using multithread technology, different tasks can be performed simultaneously. However, there are two main challenges, resource competition and technological sequence restriction. Any resource conflict in the practical test will lead to task failure and uncertainty of the test resource. If any test sequence restriction is violated, the related UUTs will suffer security risks, especially for the high-tech equipment in the aerospace field.Figure 2
Alternative schedules for the motivating example. (a) Sequential test. (b) Multi-UUT parallel test.
(a)(b)This example shows that the test efficiency can be improved remarkably by multi-UUT parallel test technology. The problem becomes more challenging when more tasks and resource types with complex test flowcharts are taken into consideration. Therefore, an optimization model that accounts for all of the aspects mentioned above is needed to minimize the test time of the multiunit parallel test.


## 3. Mathematical Formulation

This paper discusses the task scheduling problem for multiunit parallel test under the following assumptions [9, 10]:(1)
Only minimum test resource sets are provided(2)
A resource can be occupied by only one test task at the same time(3)
The time for which a resource is occupied by a test task is equal to the duration of the task(4)
No test task can be interrupted and then completed later(5)
Different test tasks of the same UUT can be performed simultaneously by different threads without violating the task sequence constraintsAll the assumptions are reasonable in real-world test projects. In assumption (1), the “minimum test resource sets” means sets with the minimum number of test resources (often one resource) that satisfy the test tasks. Assumption (1) is practical because the volume and budget of an ATS are often limited and because few spare resources are installed in the test system. Assumption (2) is based on the restriction that each resource can only be in one status. Therefore, only one task can be executed by a resource at a time. Assumption (3) means that a resource is occupied once the corresponding task starts and released once the task ends. Assumption (4) is because if a test task is interrupted, the UUT will work abnormally in subsequent tasks. Assumption (5) is the technological foundation of the parallel test.The following symbols (see Table2) are used in modelling the problem [24, 25].Table 2
Parameters and variables used to formulate the optimal task scheduling problem.
SymbolsDescriptionRR=r1,r2,…,ri,…rI is a set of various test resources, where I is the number of test resourcesNN is the total number of UUTs to be testedTT=T1∪T2⋯∪Tn⋯∪TN=t1,t2,…,tk,…,tK; K is the number of test tasks for all UUTs, and tk represents the kth test task in all tasksTnTn=t1n,t2n,…,tkn,…,tKn is the set of test tasks for UUTn, Kn is the number of test tasks for UUTn, and tkn represents the kth test task for UUTnKK=∑n=1NKn is the total number of test tasks for all UUTsτTest time vectorτ=τ1,τ2,…,τk,…,τK, and τk represents the time needed for test kAK × I task-resource dependency matrix; the (k ×i)th element aki=1 if test k needs resource I, otherwise aki=0sTask start time vectors=s1,s2,…,sk,…,sK, and sk is a continuous variable that represents the start time of test kyK × K task sequence matrix; the (k1 × k2)th element yk1k2=1 if there is a technological sequence between tk1 and tk2, which means tk1 finishes before test tk1 begins, otherwise yk1k2=0. y0 is the prerequisite technological task sequence, which is defined by the test flowchartxK × J matrix; the (k × j)th elementxkj=1 if the kth test task is assigned to thread j, otherwise xkj=0. J is the total number of test threadsThe problem of task scheduling for multiunit parallel test can be stated as follows: given test tasks setT, test resources set R, test time set τ, and task-resource dependency matrix A, the objective is to find an optimal task schedule (x, s) that minimizes the overall test time without violating the prerequisite technological task sequence y0.This problem can be formulated as the following optimization modelM [26, 27]:(1)minimizeZ=maxksk+τk,k=1,2,…,K,under the constraints(2)∑j=1Jxkj=1,j=1,2,…,J,∀k=1,2,…,K,(3)ak1i+ak2i−yk1k2−yk2k1≤1,∀i=1,2,…,I,∀k1≠k2,k1,k2=1,2,…,K,(4)xk1j+xk2j−yk1k2−yk2k1≤1,∀j=1,2,…,J,∀k1≠k2,k1,k2=1,2,…,K,(5)sk1+τk1≤sk2+U×1−yk1k2,∀k1,k2=1,2,…,K,(6)sk≥0,∀k=1,2,…,K,(7)yk1k2=0,∀k1=k2,k1,k2=1,2,...,K,(8)yk1k2+yk2k1≤1,∀k1,k2=1,2,…,K,(9)yk1k2≥yk1k20,∀k1,k2=1,2,…,K,(10)yk1k2∈0,1,∀k1≠k2,k1,k2=1,2,…,K,(11)xkj∈0,1,∀k=1,2,…,K,∀j=1,2,…,J.The objective function (1) minimizes the time of the latest completed test task. Constraint (2) ensures that every task is performed by exactly one software thread. Constraint (3) enforces an execution sequence between different tasks that need the same resource [28]. By determining an execution sequence, the resource competition problem will be solved. Constraint (4) enforces an execution sequence of different tasks that are assigned to the same thread. Constraint (5) enforces the time sequence when a sequence (either a prerequisite technological sequence or execution sequence) exists between two tasks, and U is a big-M parameter. Constraint (6) ensures that the starting time of every test task is bigger than zero. Constraint (7) ensures that no sequence is required for the task itself. Constraint (8) ensures that the sequences of tasks k1 and k2 will not conflict with each other. Constraint (9) requires the sequence matrix y to conform with prerequisite technological task sequence y0. Constraints (10) and (11) define x and y as binary variables.The modelM is an MILP model, in which s is a continuous variable and x and y are binary variables. The difficulty in solving this problem is due to the combination of sequencing and task assignment binaries (y and x). In small-scale problems, this model can be solved in a reasonable amount of time. However, for real-world test projects, the computation time increases exponentially with the number of tasks [26]. Therefore, it is necessary to explore reasonable methods for obtaining the optimal (or suboptimal) solution.


## 4. SBI Method

In real-world applications, the number of test tasks is large and the task-resource dependency is complex. Therefore, the problem is intractable with a full-space method [29]. In this section, the SBI method is proposed for solving the model M. The proposed SBI method is accomplished by the ISF SBIO procedure, and its scheme is shown in Figure 3.Figure 3
Scheme of the SBI method.


### 4.1. ISF Procedure

By test flowcharts, the prerequisite technological sequences can be fixed intuitively. For instance,y12=1,y23=1,y52=1,y14=1,y43=1,y36=1 can be set directly according to the test flowcharts shown in Figure 4(a). Although there is no prerequisite technological sequence for t1 and t3, t1 must finish before t3 begins because t1 finishes before t2 begins and t2 finishes before t3 begins. The sequences of t1 and t3 are called implied sequences [30]. It is difficult to find them one by one intuitively in large problems with many test tasks.Figure 4
Application of the ISF procedure: (a) Original test flowchart. (b) Technological sequences after the ISF procedure.
(a)(b)To derive all implied sequences, the ISF following procedure is proposed:For all test tasks of UUTn to be scheduled k1 = 1: KnFor all test tasks of UUTn to be scheduled k2 = 1: KnFor all test tasks of UUTn to be scheduled k3 = 1: KnIfyk1k2=1 AND yk2k3=1, then yk1k3=1For the test flowchart shown in Figure4(a), the implied sequences identified by the ISF procedure are shown by dashed lines in Figure 4(b). This ISF procedure is inspired in [28], in which the test tasks must be labelled elaborately according to their technological sequences. If the technological sequences are changed or new tasks are added to the flowcharts, the label numbers must be upgraded with the technological sequences, which brings great inconvenience to practical test project management [31]. In the ISF procedure proposed by this paper, the test tasks can be labelled freely. The ISF procedure can substantially reduce the computation time, as shown in Section 5.


### 4.2. SBIO Procedure

In modelM, the sequence matrix y is a key variable, which includes a K × K sequence binary elements. These binary elements can be classified into three types depending on their sources:(1)
Prerequisite technological sequence (PTS): PTS can be fixed intuitively according to the original test flowcharts. The function of PTS is to ensure all the prerequisite technological sequences are followed.(2)
Implied sequence (IS): IS is the sequence identified by the ISF procedure. The function of IS is to reduce the number of binary variables to be optimized, thereby shortening the computation time.(3)
Free sequence (FS): FS is the indeterminate element to be optimized in matrixy after the ISF procedure. FS is used to obtain a minimum objective function Z when the tasks use the same resource or are assigned to the same thread. The combination of FS is a leading contributor to the high computational burden.By the ISF procedure, the PTS and IS of every UUT can be determined. Thus, the sequence matrix for every UUT is dense (y (1), y (2), …, y (N) in Figure 5). However, for the integrated matrix of multiple UUTs, there are many FSs to be optimized (gray region in Figure 5). It is time-consuming to solve the model M. Of the three types of sequence elements, PTS and IS are determined by test flowcharts. This makes fixing FS before optimization the only way to reduce the computation time. Based on the above analysis, model M is reformulated and the SBIO procedure is proposed.Figure 5
Structure of sequence matrixy.A reformulated modelM (k) is proposed:(12)minimizeZ=maxk1sk1+τk1,k1=1,2,…,k,under the constraints(13)∑j=1Jxk1j=1,j=1,2,…,J,∀k1=1,2,…,k,(14)ak1i+ak2i−yk1k2−yk2k1≤1,∀i=1,2,…,I,∀k1≠k2,k1,k2=1,2,…,k,(15)xk1j+xk2j−yk1k2−yk2k1≤1,∀j=1,2,…,J,∀k1≠k2,k1,k2=1,2,…,k,(16)sk1+τk1≤sk2+U×1−yk1k2,∀k1,k2=1,2,…,k,(17)sk1≥0,∀k1=1,2,…,k,(18)yk1k2=0,∀k1=k2,k1,k2=1,2,…,k,(19)yk1k2+yk2k1≤1,∀k1,k2=1,2,…,k,(20)yk1k2≥yk1k20+∑l=1k−1yk1k2l,∀k1,k2=1,2,…,k,(21)yk1k2∈0,1,∀k1≠k2,k1,k2=1,2,…,k,(22)xk1j∈0,1,∀j=1,2,…,J,∀k1=1,2,…,k.Compared to modelM, model M (k) restricts the tasks to be scheduled to a partial test set {t1, t2, …, tk}. Constraint (9) in M is reformulated as constraint (20) in M (k). yk1k2l is the optimization result of model M (l).The SBIO procedure for solving modelM (k) is shown in Figure 6. The initial sequence matrix y1 is set to 0 because of its 1 × 1 dimension and lack of prerequisite test sequence for itself. For every iteration k, the SBIO procedure will solve the model M (k) to obtain yk. After adding PTS of tk+1 to yk, the ISF procedure will be performed to reduce the number of FSs. Then, the sequence matrix yk obtained by solving M (k) will be used to rebuild M (k + 1). The reservation mechanism of the last step’s optimization result will reduce the computation time of the current step. Finally, model M (K) (i.e., model M) will be solved and the corresponding optimization result will be output as the solution.Figure 6
SBIO procedure.


## 4.1. ISF Procedure

By test flowcharts, the prerequisite technological sequences can be fixed intuitively. For instance,y12=1,y23=1,y52=1,y14=1,y43=1,y36=1 can be set directly according to the test flowcharts shown in Figure 4(a). Although there is no prerequisite technological sequence for t1 and t3, t1 must finish before t3 begins because t1 finishes before t2 begins and t2 finishes before t3 begins. The sequences of t1 and t3 are called implied sequences [30]. It is difficult to find them one by one intuitively in large problems with many test tasks.Figure 4
Application of the ISF procedure: (a) Original test flowchart. (b) Technological sequences after the ISF procedure.
(a)(b)To derive all implied sequences, the ISF following procedure is proposed:For all test tasks of UUTn to be scheduled k1 = 1: KnFor all test tasks of UUTn to be scheduled k2 = 1: KnFor all test tasks of UUTn to be scheduled k3 = 1: KnIfyk1k2=1 AND yk2k3=1, then yk1k3=1For the test flowchart shown in Figure4(a), the implied sequences identified by the ISF procedure are shown by dashed lines in Figure 4(b). This ISF procedure is inspired in [28], in which the test tasks must be labelled elaborately according to their technological sequences. If the technological sequences are changed or new tasks are added to the flowcharts, the label numbers must be upgraded with the technological sequences, which brings great inconvenience to practical test project management [31]. In the ISF procedure proposed by this paper, the test tasks can be labelled freely. The ISF procedure can substantially reduce the computation time, as shown in Section 5.


## 4.2. SBIO Procedure

In modelM, the sequence matrix y is a key variable, which includes a K × K sequence binary elements. These binary elements can be classified into three types depending on their sources:(1)
Prerequisite technological sequence (PTS): PTS can be fixed intuitively according to the original test flowcharts. The function of PTS is to ensure all the prerequisite technological sequences are followed.(2)
Implied sequence (IS): IS is the sequence identified by the ISF procedure. The function of IS is to reduce the number of binary variables to be optimized, thereby shortening the computation time.(3)
Free sequence (FS): FS is the indeterminate element to be optimized in matrixy after the ISF procedure. FS is used to obtain a minimum objective function Z when the tasks use the same resource or are assigned to the same thread. The combination of FS is a leading contributor to the high computational burden.By the ISF procedure, the PTS and IS of every UUT can be determined. Thus, the sequence matrix for every UUT is dense (y (1), y (2), …, y (N) in Figure 5). However, for the integrated matrix of multiple UUTs, there are many FSs to be optimized (gray region in Figure 5). It is time-consuming to solve the model M. Of the three types of sequence elements, PTS and IS are determined by test flowcharts. This makes fixing FS before optimization the only way to reduce the computation time. Based on the above analysis, model M is reformulated and the SBIO procedure is proposed.Figure 5
Structure of sequence matrixy.A reformulated modelM (k) is proposed:(12)minimizeZ=maxk1sk1+τk1,k1=1,2,…,k,under the constraints(13)∑j=1Jxk1j=1,j=1,2,…,J,∀k1=1,2,…,k,(14)ak1i+ak2i−yk1k2−yk2k1≤1,∀i=1,2,…,I,∀k1≠k2,k1,k2=1,2,…,k,(15)xk1j+xk2j−yk1k2−yk2k1≤1,∀j=1,2,…,J,∀k1≠k2,k1,k2=1,2,…,k,(16)sk1+τk1≤sk2+U×1−yk1k2,∀k1,k2=1,2,…,k,(17)sk1≥0,∀k1=1,2,…,k,(18)yk1k2=0,∀k1=k2,k1,k2=1,2,…,k,(19)yk1k2+yk2k1≤1,∀k1,k2=1,2,…,k,(20)yk1k2≥yk1k20+∑l=1k−1yk1k2l,∀k1,k2=1,2,…,k,(21)yk1k2∈0,1,∀k1≠k2,k1,k2=1,2,…,k,(22)xk1j∈0,1,∀j=1,2,…,J,∀k1=1,2,…,k.Compared to modelM, model M (k) restricts the tasks to be scheduled to a partial test set {t1, t2, …, tk}. Constraint (9) in M is reformulated as constraint (20) in M (k). yk1k2l is the optimization result of model M (l).The SBIO procedure for solving modelM (k) is shown in Figure 6. The initial sequence matrix y1 is set to 0 because of its 1 × 1 dimension and lack of prerequisite test sequence for itself. For every iteration k, the SBIO procedure will solve the model M (k) to obtain yk. After adding PTS of tk+1 to yk, the ISF procedure will be performed to reduce the number of FSs. Then, the sequence matrix yk obtained by solving M (k) will be used to rebuild M (k + 1). The reservation mechanism of the last step’s optimization result will reduce the computation time of the current step. Finally, model M (K) (i.e., model M) will be solved and the corresponding optimization result will be output as the solution.Figure 6
SBIO procedure.


## 5. Experiments and Results

### 5.1. Experiment Design

In this section, 7 real-world examples which involve including 3 UUTs, 31 test tasks, and 10 resources were studied to evaluate the SBI method. All the examples were solved on a PC with an Intel Core i5-4590 3.3 GHz CPU using CPLEX 12.6. The relative optimality tolerance was set to 0.1%. The other CPLEX options have been set as the default for all models. In all models, the big-M parameter was set as the sum of all test tasks times, multiplied by a safety factor 2, so no feasible solutions would be cut off [28].(23)U=2×∑k1=1kτk1,∀k1=1,2,…,k.The task-resource dependency matrix and corresponding test time are shown in Table3. The configurations of the 7 examples are given in Table 4. The test flowcharts of 3 UUTs are presented in Figure 7. The small examples (1, 2, and 3) each involve only one UUT. The medium examples (4, 5, and 6) involve two UUTs, respectively. The large example involves all 3 UUTs. For every example, three scenarios (using 2, 3, and 4 threads) and three methods (full-space method without ISF, full-space method with ISF, and SBI method) for parallel test are studied to find the optimal solution.Table 3
Problem data: task-resource dependency matrix and test times of 3 UUTs.
UUTTest taskRequired resources setRTest timeτ (s)r1r2r3r4r5r6r7r8r9r10UUT1T1t1101000000018t2110000000020t3100010000042t40000010010120t5100001000026t6010000100025t7011000000040t8101000000026t9010100000060t10000100000015t11100100000016t12001010000020UUT2T2t13000001000030t14001000001075t15000011000060t160000100100145t17100001000054t180001000000120t190000100000135t20000001000010t21000000100032t22110010000025UUT3T3t23100000010115t24001101000032t25000001010040t26000000010155t27100101000055t28100100000024t29010000100075t30001000001081t31000000011030Table 4
Configuration of 7 examples.
Example1234567UUTs1231&21&32&31&2&3Total tasks (K)1210922211931Figure 7
Test flowcharts of UUT1, UUT2, and UUT3.Two indexes, speed rate (SR) and average resource utilization rate (ARUR), are used to evaluate the efficiency of the proposed method comprehensively.The SR is defined as the ratio of the sequential test time and the parallel test time for the same task set.(24)SR=∑k=1Kτkmaxksk+τk,k=1,2,...,K.The ARUR is defined as the integral average of the instantaneous resource utilization rate over the whole test.(25)ARUR=∫0tnτ/Ndτt×100%.In (25), t is the completion time of the whole test, nτ is the number of utilized resources at time τ, and N is the total number of utilized resources during the whole test. The SR can evaluate the extent of the speedup of the parallel test compared to the sequential test. The ARUR can indicate the overall level of resource utilization.


### 5.2. Model Statistics and Experiment Results

The model statistics and solution details for all examples are given in Table5. Examples are labelled in the format “E-T,” where “E” stands for the example number and “T” represents the number of threads that are used. For example, label “7-3” means that example 7 is solved using 3 threads. The recorded model statistics are the numbers of constraints and binary and continuous variables in model M. The solution details of both the full-space method and the SBI method are recorded for comparison. The search time is limited to 2000 seconds for all examples. The computation times of the full-space method are recorded in the two cases. The FIS procedure is adopted in the first case but not the second. The computation time of the SBI method includes the total time needed for the ISF and SBIO procedures.Table 5
Model statistics and solution details of 7 examples.
ExampleModel detailsFull-space methodSBI methodBinary variablesContinuous variablesConstraintsOptimal solution (s)Computation time without ISF (s)Computation time with ISF (s)Best solution (s)Computation time (s)SRARUR1-21561260532116.21.73219.41.3326.12-21101040746111.11.44616.61.4926.73-29093342538.11.32535.61.6136.04-2506222065728485.766.472835.31.5328.55-2462211898577366.653.257732.11.4530.46-2380191532732206.232.873224.81.4929.37-2992314150999a20001066.3999a86.51.5229.91-31681286932125.12.132110.51.3326.12-31201058745616.51.74567.11.527.03-399947825312.11.52535.91.6136.14-3528222989658758.589.665844.41.6931.55-3483212738533593.668.9533401.5732.96-3399192216619321.643.161930.71.7734.77-31023316010None20002000815113.51.8736.71-418012113332131.92.532111.51.3326.12-41301076745622.11.94567.61.527.03-4108962225316.11.72536.31.6136.04-45502239135771077.510857753.41.9337.15-4504213578553844.683.253347.91.5732.96-4418192900619461.854.461936.31.7734.77-41054317870None20002000815141.21.8736.7aSolution of examples 7-2 is found by the full-space method with ISF.The advantage of the proposed MILP model lies in its unlimited descriptive ability, which means that it can describe test task scheduling problem with any number of tasks, resources, and threads. What is more, every practical constraint for test resources, threads, and sequences can be described clearly by the corresponding equation or inequality in modelM (k). However, the number of binary variables and total constraints will increase sharply with the number of tasks, resources, and threads getting larger (see “Model details” in Table 5), which is caused by the combination of the three. This will lead to more memory to be consumed when solving the model. Considering that the memory of the modern computer is large enough to deal with it and the computation time will be reduced by the proposed SBI method, this disadvantage can be overcome.As shown in Table5, the optimal solution cannot be found in 2000 s by the full-space method without the ISF procedure in examples 7-2, 7-3, and 7-4. Nor can it be found by the full-space method with the ISF procedure in 2000 s in examples 7-3 and 7-4. However, the optimal (or suboptimal) solutions can be found by the proposed SBI method in all examples.


### 5.3. Discussion

#### 5.3.1. Computation Time

The computation time of all examples is shown in Figure8 on the natural logarithmic scale. In all examples, the full-space method without the ISF procedure takes the most computation time. The full-space method with the ISF procedure takes the least computation time in small problems that involve one UUT (examples 1, 2, and 3). However, for medium and large problems with 2 or 3 UUTs (examples 4-7), the SBI method takes the least computation time. Therefore, the time efficiency of the SBI method is better than that of the full-space method for large problems, such as in practical multiple UUTs parallel test applications.Figure 8
Computation time of all the examples.


#### 5.3.2. Resource Competition and Thread Competition

The best solutions (i.e., those with the minimum tasks completion time) with different number of threads are shown in Figure9. For small problems (examples 1, 2, and 3), using different numbers of threads has no remarkable effect on the value of the solution. The best solution of example 2 using 2 threads is associated with longer computation time (461 s) than the solutions that are obtained using 3 and 4 threads (456 s) because some tasks must “wait” to be performed when the number of threads is limited. However, for medium and large problems (examples 4-7), using more threads to schedule test tasks can reduce the completion time of the whole test. Nevertheless, it does not promise an affirmatory optimal solution reduction (see examples 4-6 in Figure 9) because the completion time is restricted by test resources other than the number of threads. In practical test projects, using too many threads will lead to higher complexity of resource control. For this reason, applying fewer threads is preferable when the solutions are equal. For the biggest problem (example 7), the same solution can be found using either 3 or 4 threads.Figure 9
Best solutions with different threads.The Gantt chart of the best solution for all the examples are shown in Figure10, in which the resource competition and thread competition are efficiently solved, and this will facilitate the software programming and resource control in practice.Figure 10
Gantt chart of the best solution. (a) Example 1, (b) example 2, (c) example 3, (d) example 4, (e) example 5, (f) example 6, and (g) example 7.
(a)(b)(c)(d)(e)(f)(g)


#### 5.3.3. Effect of Adding Tasks

To evaluate the effect of adding tasks in the proposed model, three tasks (t32, t33, and t34) were randomly generated and inserted into the test flowchart in example 7. The three tasks were generated by following rules: (1) the required resources, with a maximum number of 3, were randomly selected from the given resource set; (2) test time for each task was a randomly generated real number within the bounds minτk,maxτk,k=1,2,…,31; and (3) each task was inserted into one of the test flowchart, which means t32∈T1,t33∈T2,t34∈T3. The test sequences were also randomly generated. Table 6 and Figure 11 report the details of three randomly generated tasks. Example 7 with tasks t32, t33, and t34 was denoted as example 7∗. Example 7∗ was solved based on model M (31) of example 7 using 3 threads, and the model statics and solution details are recorded in Table 7.Table 6
Problem data: task-resource dependency matrix and test time oft32, t33, and t34.
UUTTest taskRequired resources setRTest timeτ (s)r1r2r3r4r5r6r7r8r9r10UUT1T1t32000010000023.1UUT2T2t33010001000095.4UUT3T3t340101000100133.3Figure 11
Test flowcharts of UUT1, UUT2, and UUT3 witht32, t33, and t34.Table 7
Model statistics and solution details of example 7∗ using 3 threads.
ModelBinary variablesContinuous variablesConstraintsBest solution (s)Additional computation time (s)SRARUR (%)M (32)10883263958155.21.9338.0M (33)1155336415833.46.41.9738.1M (34)1224347247853.49.12.0747.1The additional computation time for adding a task to the proposed model is less than 10 seconds (see Table7). When adding a new task to test projects, the developer simply needs to describe the resource requirements and redefines the test flowchart. In comparison, the procedure proposed by Maravelias and Grossmann [28] has to label the test tasks elaborately according to their technological sequences, which means the whole model must be reoptimized. Therefore, the SBI method will bring great convenience to practical application when adding new test tasks.


#### 5.3.4. SR and ARUR

The SR and ARUR for examples 4-7 are shown in Figure12. The SR of parallel test for all examples ranges from 1.33 (example 1) to 1.97 (example 4 using 4 threads), which means that the parallel test consumes 50.7% (1/1.97) to 75% (1/1.33) of the time compared to the sequential test. From the computational results shown in Figure 12, it is concluded that the SR will increase with the ARUR for the same tasks set, which proves that the multi-UUT parallel test trades space for time.Figure 12
SR and ARUR of examples 4-7.


## 5.1. Experiment Design

In this section, 7 real-world examples which involve including 3 UUTs, 31 test tasks, and 10 resources were studied to evaluate the SBI method. All the examples were solved on a PC with an Intel Core i5-4590 3.3 GHz CPU using CPLEX 12.6. The relative optimality tolerance was set to 0.1%. The other CPLEX options have been set as the default for all models. In all models, the big-M parameter was set as the sum of all test tasks times, multiplied by a safety factor 2, so no feasible solutions would be cut off [28].(23)U=2×∑k1=1kτk1,∀k1=1,2,…,k.The task-resource dependency matrix and corresponding test time are shown in Table3. The configurations of the 7 examples are given in Table 4. The test flowcharts of 3 UUTs are presented in Figure 7. The small examples (1, 2, and 3) each involve only one UUT. The medium examples (4, 5, and 6) involve two UUTs, respectively. The large example involves all 3 UUTs. For every example, three scenarios (using 2, 3, and 4 threads) and three methods (full-space method without ISF, full-space method with ISF, and SBI method) for parallel test are studied to find the optimal solution.Table 3
Problem data: task-resource dependency matrix and test times of 3 UUTs.
UUTTest taskRequired resources setRTest timeτ (s)r1r2r3r4r5r6r7r8r9r10UUT1T1t1101000000018t2110000000020t3100010000042t40000010010120t5100001000026t6010000100025t7011000000040t8101000000026t9010100000060t10000100000015t11100100000016t12001010000020UUT2T2t13000001000030t14001000001075t15000011000060t160000100100145t17100001000054t180001000000120t190000100000135t20000001000010t21000000100032t22110010000025UUT3T3t23100000010115t24001101000032t25000001010040t26000000010155t27100101000055t28100100000024t29010000100075t30001000001081t31000000011030Table 4
Configuration of 7 examples.
Example1234567UUTs1231&21&32&31&2&3Total tasks (K)1210922211931Figure 7
Test flowcharts of UUT1, UUT2, and UUT3.Two indexes, speed rate (SR) and average resource utilization rate (ARUR), are used to evaluate the efficiency of the proposed method comprehensively.The SR is defined as the ratio of the sequential test time and the parallel test time for the same task set.(24)SR=∑k=1Kτkmaxksk+τk,k=1,2,...,K.The ARUR is defined as the integral average of the instantaneous resource utilization rate over the whole test.(25)ARUR=∫0tnτ/Ndτt×100%.In (25), t is the completion time of the whole test, nτ is the number of utilized resources at time τ, and N is the total number of utilized resources during the whole test. The SR can evaluate the extent of the speedup of the parallel test compared to the sequential test. The ARUR can indicate the overall level of resource utilization.


## 5.2. Model Statistics and Experiment Results

The model statistics and solution details for all examples are given in Table5. Examples are labelled in the format “E-T,” where “E” stands for the example number and “T” represents the number of threads that are used. For example, label “7-3” means that example 7 is solved using 3 threads. The recorded model statistics are the numbers of constraints and binary and continuous variables in model M. The solution details of both the full-space method and the SBI method are recorded for comparison. The search time is limited to 2000 seconds for all examples. The computation times of the full-space method are recorded in the two cases. The FIS procedure is adopted in the first case but not the second. The computation time of the SBI method includes the total time needed for the ISF and SBIO procedures.Table 5
Model statistics and solution details of 7 examples.
ExampleModel detailsFull-space methodSBI methodBinary variablesContinuous variablesConstraintsOptimal solution (s)Computation time without ISF (s)Computation time with ISF (s)Best solution (s)Computation time (s)SRARUR1-21561260532116.21.73219.41.3326.12-21101040746111.11.44616.61.4926.73-29093342538.11.32535.61.6136.04-2506222065728485.766.472835.31.5328.55-2462211898577366.653.257732.11.4530.46-2380191532732206.232.873224.81.4929.37-2992314150999a20001066.3999a86.51.5229.91-31681286932125.12.132110.51.3326.12-31201058745616.51.74567.11.527.03-399947825312.11.52535.91.6136.14-3528222989658758.589.665844.41.6931.55-3483212738533593.668.9533401.5732.96-3399192216619321.643.161930.71.7734.77-31023316010None20002000815113.51.8736.71-418012113332131.92.532111.51.3326.12-41301076745622.11.94567.61.527.03-4108962225316.11.72536.31.6136.04-45502239135771077.510857753.41.9337.15-4504213578553844.683.253347.91.5732.96-4418192900619461.854.461936.31.7734.77-41054317870None20002000815141.21.8736.7aSolution of examples 7-2 is found by the full-space method with ISF.The advantage of the proposed MILP model lies in its unlimited descriptive ability, which means that it can describe test task scheduling problem with any number of tasks, resources, and threads. What is more, every practical constraint for test resources, threads, and sequences can be described clearly by the corresponding equation or inequality in modelM (k). However, the number of binary variables and total constraints will increase sharply with the number of tasks, resources, and threads getting larger (see “Model details” in Table 5), which is caused by the combination of the three. This will lead to more memory to be consumed when solving the model. Considering that the memory of the modern computer is large enough to deal with it and the computation time will be reduced by the proposed SBI method, this disadvantage can be overcome.As shown in Table5, the optimal solution cannot be found in 2000 s by the full-space method without the ISF procedure in examples 7-2, 7-3, and 7-4. Nor can it be found by the full-space method with the ISF procedure in 2000 s in examples 7-3 and 7-4. However, the optimal (or suboptimal) solutions can be found by the proposed SBI method in all examples.


## 5.3. Discussion

### 5.3.1. Computation Time

The computation time of all examples is shown in Figure8 on the natural logarithmic scale. In all examples, the full-space method without the ISF procedure takes the most computation time. The full-space method with the ISF procedure takes the least computation time in small problems that involve one UUT (examples 1, 2, and 3). However, for medium and large problems with 2 or 3 UUTs (examples 4-7), the SBI method takes the least computation time. Therefore, the time efficiency of the SBI method is better than that of the full-space method for large problems, such as in practical multiple UUTs parallel test applications.Figure 8
Computation time of all the examples.


### 5.3.2. Resource Competition and Thread Competition

The best solutions (i.e., those with the minimum tasks completion time) with different number of threads are shown in Figure9. For small problems (examples 1, 2, and 3), using different numbers of threads has no remarkable effect on the value of the solution. The best solution of example 2 using 2 threads is associated with longer computation time (461 s) than the solutions that are obtained using 3 and 4 threads (456 s) because some tasks must “wait” to be performed when the number of threads is limited. However, for medium and large problems (examples 4-7), using more threads to schedule test tasks can reduce the completion time of the whole test. Nevertheless, it does not promise an affirmatory optimal solution reduction (see examples 4-6 in Figure 9) because the completion time is restricted by test resources other than the number of threads. In practical test projects, using too many threads will lead to higher complexity of resource control. For this reason, applying fewer threads is preferable when the solutions are equal. For the biggest problem (example 7), the same solution can be found using either 3 or 4 threads.Figure 9
Best solutions with different threads.The Gantt chart of the best solution for all the examples are shown in Figure10, in which the resource competition and thread competition are efficiently solved, and this will facilitate the software programming and resource control in practice.Figure 10
Gantt chart of the best solution. (a) Example 1, (b) example 2, (c) example 3, (d) example 4, (e) example 5, (f) example 6, and (g) example 7.
(a)(b)(c)(d)(e)(f)(g)


### 5.3.3. Effect of Adding Tasks

To evaluate the effect of adding tasks in the proposed model, three tasks (t32, t33, and t34) were randomly generated and inserted into the test flowchart in example 7. The three tasks were generated by following rules: (1) the required resources, with a maximum number of 3, were randomly selected from the given resource set; (2) test time for each task was a randomly generated real number within the bounds minτk,maxτk,k=1,2,…,31; and (3) each task was inserted into one of the test flowchart, which means t32∈T1,t33∈T2,t34∈T3. The test sequences were also randomly generated. Table 6 and Figure 11 report the details of three randomly generated tasks. Example 7 with tasks t32, t33, and t34 was denoted as example 7∗. Example 7∗ was solved based on model M (31) of example 7 using 3 threads, and the model statics and solution details are recorded in Table 7.Table 6
Problem data: task-resource dependency matrix and test time oft32, t33, and t34.
UUTTest taskRequired resources setRTest timeτ (s)r1r2r3r4r5r6r7r8r9r10UUT1T1t32000010000023.1UUT2T2t33010001000095.4UUT3T3t340101000100133.3Figure 11
Test flowcharts of UUT1, UUT2, and UUT3 witht32, t33, and t34.Table 7
Model statistics and solution details of example 7∗ using 3 threads.
ModelBinary variablesContinuous variablesConstraintsBest solution (s)Additional computation time (s)SRARUR (%)M (32)10883263958155.21.9338.0M (33)1155336415833.46.41.9738.1M (34)1224347247853.49.12.0747.1The additional computation time for adding a task to the proposed model is less than 10 seconds (see Table7). When adding a new task to test projects, the developer simply needs to describe the resource requirements and redefines the test flowchart. In comparison, the procedure proposed by Maravelias and Grossmann [28] has to label the test tasks elaborately according to their technological sequences, which means the whole model must be reoptimized. Therefore, the SBI method will bring great convenience to practical application when adding new test tasks.


### 5.3.4. SR and ARUR

The SR and ARUR for examples 4-7 are shown in Figure12. The SR of parallel test for all examples ranges from 1.33 (example 1) to 1.97 (example 4 using 4 threads), which means that the parallel test consumes 50.7% (1/1.97) to 75% (1/1.33) of the time compared to the sequential test. From the computational results shown in Figure 12, it is concluded that the SR will increase with the ARUR for the same tasks set, which proves that the multi-UUT parallel test trades space for time.Figure 12
SR and ARUR of examples 4-7.


## 5.3.1. Computation Time

The computation time of all examples is shown in Figure8 on the natural logarithmic scale. In all examples, the full-space method without the ISF procedure takes the most computation time. The full-space method with the ISF procedure takes the least computation time in small problems that involve one UUT (examples 1, 2, and 3). However, for medium and large problems with 2 or 3 UUTs (examples 4-7), the SBI method takes the least computation time. Therefore, the time efficiency of the SBI method is better than that of the full-space method for large problems, such as in practical multiple UUTs parallel test applications.Figure 8
Computation time of all the examples.


## 5.3.2. Resource Competition and Thread Competition

The best solutions (i.e., those with the minimum tasks completion time) with different number of threads are shown in Figure9. For small problems (examples 1, 2, and 3), using different numbers of threads has no remarkable effect on the value of the solution. The best solution of example 2 using 2 threads is associated with longer computation time (461 s) than the solutions that are obtained using 3 and 4 threads (456 s) because some tasks must “wait” to be performed when the number of threads is limited. However, for medium and large problems (examples 4-7), using more threads to schedule test tasks can reduce the completion time of the whole test. Nevertheless, it does not promise an affirmatory optimal solution reduction (see examples 4-6 in Figure 9) because the completion time is restricted by test resources other than the number of threads. In practical test projects, using too many threads will lead to higher complexity of resource control. For this reason, applying fewer threads is preferable when the solutions are equal. For the biggest problem (example 7), the same solution can be found using either 3 or 4 threads.Figure 9
Best solutions with different threads.The Gantt chart of the best solution for all the examples are shown in Figure10, in which the resource competition and thread competition are efficiently solved, and this will facilitate the software programming and resource control in practice.Figure 10
Gantt chart of the best solution. (a) Example 1, (b) example 2, (c) example 3, (d) example 4, (e) example 5, (f) example 6, and (g) example 7.
(a)(b)(c)(d)(e)(f)(g)


## 5.3.3. Effect of Adding Tasks

To evaluate the effect of adding tasks in the proposed model, three tasks (t32, t33, and t34) were randomly generated and inserted into the test flowchart in example 7. The three tasks were generated by following rules: (1) the required resources, with a maximum number of 3, were randomly selected from the given resource set; (2) test time for each task was a randomly generated real number within the bounds minτk,maxτk,k=1,2,…,31; and (3) each task was inserted into one of the test flowchart, which means t32∈T1,t33∈T2,t34∈T3. The test sequences were also randomly generated. Table 6 and Figure 11 report the details of three randomly generated tasks. Example 7 with tasks t32, t33, and t34 was denoted as example 7∗. Example 7∗ was solved based on model M (31) of example 7 using 3 threads, and the model statics and solution details are recorded in Table 7.Table 6
Problem data: task-resource dependency matrix and test time oft32, t33, and t34.
UUTTest taskRequired resources setRTest timeτ (s)r1r2r3r4r5r6r7r8r9r10UUT1T1t32000010000023.1UUT2T2t33010001000095.4UUT3T3t340101000100133.3Figure 11
Test flowcharts of UUT1, UUT2, and UUT3 witht32, t33, and t34.Table 7
Model statistics and solution details of example 7∗ using 3 threads.
ModelBinary variablesContinuous variablesConstraintsBest solution (s)Additional computation time (s)SRARUR (%)M (32)10883263958155.21.9338.0M (33)1155336415833.46.41.9738.1M (34)1224347247853.49.12.0747.1The additional computation time for adding a task to the proposed model is less than 10 seconds (see Table7). When adding a new task to test projects, the developer simply needs to describe the resource requirements and redefines the test flowchart. In comparison, the procedure proposed by Maravelias and Grossmann [28] has to label the test tasks elaborately according to their technological sequences, which means the whole model must be reoptimized. Therefore, the SBI method will bring great convenience to practical application when adding new test tasks.


## 5.3.4. SR and ARUR

The SR and ARUR for examples 4-7 are shown in Figure12. The SR of parallel test for all examples ranges from 1.33 (example 1) to 1.97 (example 4 using 4 threads), which means that the parallel test consumes 50.7% (1/1.97) to 75% (1/1.33) of the time compared to the sequential test. From the computational results shown in Figure 12, it is concluded that the SR will increase with the ARUR for the same tasks set, which proves that the multi-UUT parallel test trades space for time.Figure 12
SR and ARUR of examples 4-7.


## 6. Conclusions

In this paper, an MILP optimization model for the scheduling of multiunit parallel test is presented. This model uses the sequence variables to describe the resource competition and the thread competition, which takes the original test flowcharts into consideration. To solve the model in a reasonable amount of time, the proposed model is reformulated and a novel SBI method is proposed. The SBI method is accomplished by the ISF and SBIO procedures. The ISF procedure reduces the search space by fixing FS variables according to the original test flowcharts, and the SBIO procedure can solve the reformulated model in a reasonable amount of time. Moreover, the SBI method is evaluated comprehensively in terms of test duration, SR, and ARUR using different numbers of threads. The computational results prove that the SBI method performs well in real-world test examples, especially for larger examples that cannot be solved by the full-space method. The method presented in this paper can be applied to many task scheduling problems that involve resource competition, such as software test, and agrochemical and pharmaceutical products development. Future research will concentrate on developing a method for task scheduling problems that have high resource requirements for every resource type.



---

*Source: 3785452-2021-01-29.xml*