A branch and price algorithm for the robust WSOS scheduling problem

LI Ruiyang, HE Ming, HE Hongyue, WANG Zhixue, and YANG Cheng

Institute of Command and Control Engineering, Army Engineering University of PLA, Nanjing 210007, China

Abstract: To analyze and optimize the weapon system of systems (WSOS) scheduling process, a new method based on robust capabilities for WSOS scheduling optimization is proposed.First, we present an activity network to represent the military mission. The member systems need to be reasonably assigned to perform different activities in the mission. Then we express the problem as a set partitioning formulation with novel columns(activity flows). A heuristic branch-and-price algorithm is designed based on the model of the WSOS scheduling problem(WSOSSP). The algorithm uses the shortest resource-constrained path planning to generate robust activity flows that meet the capability requirements. Finally, we discuss this method in several test cases. The results show that the solution can reduce the makespan of the mission remarkably.

Keywords: weapon system of systems (WSOS), robust optimization, scheduling decision, branch-and-price, column generation.

1. Introduction

Weapon system of systems (WSOS) is a higher-level military complex system. It is integrated by various weapon systems that are functionally interconnected and complement [1]. To meet diverse military requirements and maximize overall operational effectiveness, all countries in the world are vigorously developing WSOS under the guidance of national security and military strategy. At present,most of the research is focused on the construction of the WSOS, exploring the optimal construction program to meet the military requirements. However, the research on scheduling in the scheduling process of the WSOS is still scarce. Appropriate WSOS scheduling scheme not only makes rational use of human and material resources, but also preemptively takes the initiative on the battlefield.Thus, at the beginning of the military mission, using scientific models and methods to analyze and optimize the WSOS scheduling process is particularly important [2].

The WSOS scheduling problem (WSOSSP) is defined as: under the premise of meeting the capability requirements of various activities, the limited systems and resources provided by the WSOS are reasonably allocated,the execution strategy of various operational activities is determined, and then the WSOS scheduling scheme in the mission is obtained. This problem is an extension and application of the multi-mode resource-constrained project scheduling problem (MRCPSP) in the military field. The MRCPSP is a classical non-deterministic polynomial hard (NP-hard) problem [3].

Most of the researches on the MRCPSP use the heuristic algorithm or meta-heuristic algorithm. For example,Chen et al. [4] proposed a two-stage genetic algorithm,which considered the activity mode and scheduling scheme. Najid et al. [5] divided the resource constraints in the MRCPSP into renewable and non-renewable, and proposed a new tabu search algorithm. Wang et al. [6]solved the MRCPSP by the estimation of distribution algorithm (EDA). Ayodele et al. [7] combined the EDA with the genetic algorithm to synchronize the different search spaces presented by two subproblems of mode selection and scheduling optimization. According to the non-preemptive MRCPSP, Adamu et al. [8] presented a novel method based on machine learning to obtain the feasible activity priority list of the project’s tasks, and calculated the primary solutions by metaheuristic algorithms. Afshar et al. [9] introduced a new local search method into the genetic algorithm framework to solve the MRCPSP. Roson et al. [10] divided resource constraints into different levels according to their importance, and proposed a hybrid optimization algorithm to solve the problem. In addition to the above, Ratajczak [11], Zsolt[12], Vahdani [13], etc. also solved similar problems based on the heuristic or meta-heuristic algorithms. These methods can find the approximate optimal solution satisfying the constraint in the polynomial time, but the stability of these algorithms is relatively poor in general.

There are also some researches on solving the MRCPSP with exact algorithms. The branch and bound method proposed by Sprecher et al. [14] is a classical exact algorithm. The algorithm used depth-first search and dominance rules to improve the algorithm efficiency. Mixed integer linear programming proposed by Kyriakidis et al.[15] is also a common method. In addition, the deterministic Boolean satisfiability theory proposed by Jose et al.[16] and Schnell et al. [17], the satisfiability model theory proposed by Bofill et al. [18] and the hybrid method combining branch and bound with a single non-renewable resource constraint proposed by Altintas et al. [19]are all used exact algorithms to solve the MRCPSP.

However, all the methods mentioned above are deterministic optimization methods. Considering the complex and changing characteristics of military missions, uncertainty such as weather changes, enemy strikes, and electromagnetic interference may affect the capabilities of the weapon system, which in turn affects the WSOS scheduling process. It has been proved that the uncertainty may lead to poor or even infeasible solutions. Therefore, we must find an optimization method that can effectively deal with the uncertainty, and ensure that the obtained scheme can be applied reliably. Robust optimization is a suitable method [20]. When the relevant parameters are changed by uncertainty, the scheme can maintain high stability against these changes. Leus et al. [21] proposed that the activities in the project insert a fixed buffer time to reduce the impact of uncertainty, but the value of the buffer time is often based on experience, so it is very subjective. Kaveh et al. [22], Birjandi et al. [23] represented parameters in the scheduling model as fuzzy variables,and Angela [24] used entropy functions to represent uncertain variables in the model and analyze the robustness of the solution. Shan et al. [25] designed a robust counterpart model for solving uncertain variables in the location and path planning problems.

Based on the previous researches, we consider the scenario where the capabilities provided by the weapon system decline during the WSOS scheduling process.Firstly we design a novel robust optimization model based on dynamic transfer equation, in which each column (variable) represents an activity flow on a timeline, and a feasible solution of the WOSSP is composed of multiple such activity flows. Secondly, the model we propose has a tighter lower bound, and each column has a distinct physical meaning. Based on this, we propose a more efficient heuristic branch-and-price algorithm that can help to make a high-quality solution in a certain time.

For the remainder, Section 2 describes the WSOSSP.Section 3 provides a robust mathematical model for the uncertain WSOSSP. Section 4 introduces a heuristic branch-and-price algorithm to solve the model. Section 5 reports computational experiments. Section 6 summarizes the conclusion.

2. Problem description

As was already mentioned, the WSOSSP can be described as follows: when a military mission is determined,the WSOS begins to perform a series of operational activities. Each of these activities can be completed when it meets specified operational capability requirements, such as communication, reconnaissance, transportation, etc.The system in the WSOS can provide a subset of capabilities. Therefore, different strategies composed of different systems that meet capability requirements can be selected to perform operational activities. In addition, there is a priority relationship between operational activities, and an activity can only begin after all its immediate preceding activities have been completed. Under the capability requirements, resource and time priority constraints, each member system in the WSOS is reasonably scheduled, so that the mission is completed in the shortest time.

Fig. 1 shows an example of a feasible strategy for analyzing activities: there are four systems in the WSOS that can provide certain operational capabilities. For example,Sys1 has C1 capability of 2 and C2 capability of 2. The strategy of (Sys1, Sys3) is able to complete activity V1 because it provides C1 capability of 4, which exceeds V1’s minimum capability requirement of 3. Similarly, activity V2 has two feasible strategies (Sys1, Sys2) and (Sys2,Sys4), and activity V3 has two feasible strategies (Sys2,Sys3) and (Sys3, Sys4).

Fig. 1 Example to analyze the activity feasible strategy

Fig. 2 shows a simple example of the scheduling process of the WSOS. We use an activity-on-node (AON) to represent the military mission. The activities in the mission are represented by a set of nodes {0,1,2,···i,···,11},where nodes 0 and 11 represent the start and end activities of the mission respectively. The priority order of the activities is represented by the directed edges between the connected nodes. The commander rationally allocates the systems in the WSOS to meet the capability require-ments of different activities, and ultimately minimizes the makespan of the mission. In fact, each system can be only assigned to one activity at a time. Such as Sys5 in Fig. 2,which can be allocated to activity 7 when activity 4 is completed. In addition, the resources consumed to complete all activities cannot exceed the resource limits that the WSOS can provide.

Fig. 2 Illustrative example of the WSOS scheduling process

It assumes that all activities in the mission require only one capability. Fig. 3 shows a scheduling scheme for the WSOS. The data is shown in Table 1. In this scheme, the capability requirements and the timing priority for each activity can be satisfied, and a system does not perform two different activities at the same time. Regardless of the resource constraints, the scheme can be considered as a feasible scheduling scheme, and the total time for completing the mission is 14 h.

Fig. 3 Feasible scheduling scheme for the example

Table 1 Detailed data of the scheme

3. Mathematical model

3.1 Nominal model of the WSOSSP

We model the scheduling optimization process of the WSOS. In our model, the following assumptions are given:

(i) In the planning horizon, the capability requirements and duration of each operational activity are predetermined. The activities have different feasible strategies,but only one of them can be selected.

(ii) At any time, a system in the WSOS can only provide capabilities for at most one activity.

(iii) The process by which the systems perform an activity is continuous during the mission. In other words,once an activity begins, it cannot be interrupted.

(iv) Starting and ending avtivities are two dummy activities that do not need capabilities and resources, and their duration is 0.

In solving the WSOSSP, the commander should determine how to allocate a limited number of systems in the WSOS to the operational activities. The execution time of the activity is optimized. A mathematical model[P] for the WSOSSP is proposed as follows:

s.t.

3.2 Robust model of the WSOSSP

Each system in the WSOS participating in the operational activities will provide specific capabilities. There are many methods for evaluating the capabilities of a weapon system, such as expert scoring, fuzzy comprehensive evaluation, Lanchester equation, Monte Carlo [26]. When considering the influence of uncertain factors in the battlefield, the capability of the systems is often not fixed,and usually fluctuate within a range. According to the robust optimization, it is defined in an uncertain set to optimize the worst case in the set. In this paper, we use a symmetric and bounded random variableto represent the capability of the systems, wheredenotes the expected value of the capabilitylfor the systemn, andis the maximum deviation from the expected capability. In the model [P], only constraint (8) which contains uncertain variables needs to be reformulated.Therefore, constraint (8) can be represented as val ue accordingtoanunknownbutsymmetricdistribu-

In(10), we definearandomvariableηl,whichtakes tion[-1,1].Whenηl=-1, the variouscapabilitiesof the systems aretheminimum, which isequivalent to theminmax absolute robust criterion [27]. Although the obtained scheduling scheme can face any variation of the system capabilities, the scheme is too conservative and may cause the WSOS waste a lot of time. In practice, the commander will comprehensively adjust the degree of risk preference and the robustness of the scheme according to their personality characteristics and battlefield situation. We consider the slack robustness criterion [28]. A controlparameterΓlisintroducedto adjusttherobustnessofthe scheme.Thisparameterdenotesthe numberof the weapon systems that can provide the capabilitylwhich takes the minimum value. Γltakes value inThe larger the value, the higher the robustness. When Γlis determined, it means that up toof systems with capabilityltake a value ofone system takes a value ofand the remaining systems take the expected value ofThen, the constraint (10) can be formulated as

whereydenotes the set of the decision variablesyin, and λl(y,Γl)is a nonlinear function, according to the strong duality, it can be transformed into an equivalent linear constraint as follows:

whereSrepresents the set of systems with capabilityltakes a value ofJrepresents the set of all systems with uncertain capabilityl, andrrepresents the set of remaining systems with uncertain capabilityl.

4. Solution method

Although the formulation [P] could be solved by CPLEX directly, it is difficult to solve practical problems, even for a moderate size instance. A Dantzig-Wolfe decomposition method is used in this paper to obtain a master problem and a pricing subproblem. We propose a column generation approach because the cardinality of the variables is extremely large.

In this mathematical model, a columnr(i.e., an activity flow) represents a series of activities performed along a timeline. Hence, a feasible solution is a convex combination of multiple activity flows that satisfy the constraints, which is shown in Fig. 4. Two red arrows represent two different activity flows (0-1-5-8-10-11, 0-2-4-6-7-3-9-11).

Fig. 4 Illustrative example of the activity flow

4.1 Master problem

This paper transforms the compact formulation [P] into a set partitioning formulation [MP] (Nannicini et al. [29]),which is regarded as the MP. Using the Dantzig-Wolfe decomposition, a set of constraints ((2)-(9)) in [P] can be replaced by a convex hull.

The MP [MP] can be formulated as follows:

[MP]

s.t.

where the objective function (12) and constraint (13)minimize γ which represents the makespan of the longest lasting activity flow in a feasible solution, Ω is the set of feasible activity flows,Tris the makespan of theactivity flowr, and θrrepresents that theactivity flowrisselected.Constraint (14) denotes that all activities mustbe included in the selected activity flows, each activity must be completed only once, andrepresents that the activityiis selected in the activity flowr. Constraint (15) denotes that any system in the WSOS can be only assigned to one activity at a time, andrepresents the systemnis selected by the activity flowrat timet. Constraint (16)denotes that the priority relationship between activities, in other words, any activity can only start when all its preceding activities are completed, andr epresents the start time of the activityiin the activity flowr. Constraint(17) denotes that the amount of consumable resources used cannot exceed the resource limit provided by the WSOS,andIris the resource consumptionbytheactivityflowr.Constraints(18) and (19)clarifythedomains of variables.

Given that the activity flow set Ω is extremely large,this paper considers a subset Ω′of Ω. This subset only contains those variables (i.e., activity flows) generated by solving the pricing subproblem. The master problem only considering the subset Ω′is called the restricted master problem (RMP).

4.2 Pricing subproblem

s.t.

where the objective function (20) minimizes the reduced cost ϖr. Constraints (21)-(23) denote a flow equilibrium relationship. Constraint (24) denotes the relationship between variables χijandyin. Constraints (25)-(26) denote the time window constraints for each activity. Constraints (27)-(29) respectively denote the capability requirements, makespan of the whole mission constraints and the consumable resource constraints. Constraints(30)-(32) clarify the domains of variables. The binary variable χijis equal to 1 if and only if the activitiesiandjare completed continuously. The PP is also NP-hard[30], it will consume most of the computing time in the process of column generation. Therefore, this paper proposes a tailor dynamic programming to solve it.

It notes that the parameterin constraint (27) is a random variable, thus it needs to be linearized. We refer to the method of Munari et al. [31] to define new state variableswhich denote the maximum value of the capabilitylthat can be provided when systemnperforms activityi. Therefore, constraint (27) can be extended as follows：

Hence, for the robust labeling algorithm, an implementation of the dynamic programming-based algorithm is used [32], which is called exact dynamic programming(EDP). In the dynamic programming-based algorithm, the start node and end node (i.e., activities) are represented by the same node. We build the new activity flows from the start node toward a sink node, which are encoded by labels. A state associated with a feasible activity flow from the start node 0 to the nodeiis defined as a multidimensional labelwhereSiis the set indicating which nodes have already been visited by σi;is the minimum value of the capabilitylprovided by systemnperforming activityi, when up to ε≤Γlcapabilitylattains it worst case; τiis the start time at the nodeiin the activity flow σi; φiis the least reduced cost of the activity flow σi;iis the last reached node in σi.

At the start node 0, the setS0is initialized at φ, andare initialized at 0. Each node may have multiple labels and the optimal solution to the pricing subproblem can be achieved by identifying the labels with the smallest φ(r) at the nodee. Note that for the a ctivity flowr, and each possible schedule scheme can be performed only at a time. Once a certain time is chosen to perform the schedule scheme by a label, the successors will perform the schedule pattern on the same time. When a feasible labelis associated with the nodei, it can be extended to a nodej∈Valong an arc(i,j) , yielding a new label σi. The extension functions are

For each timet, the labeldominates the labelif the following conditions hold:tre atedand untreatedlabels atthenodei∈V,respec-

Inthis algorithm,TLiandULidenotethesetsof tively. First, we initialize the label in lines 1 to 5. Line 6 is the start of the main loop and all untreated nondominated labels will be extended next. In line 7, a labelLiis chosen inULifollowing a certain rule (the shortest time component first). Then, the labelLiis extended to its successorjto generate a new labelLjaccording to the expansion function in line 8 and line 9. If labelLjis feasible, we use the dominance rules to examine whether the labelLjis dominated by a label inULj∪TLjor whether the labelLjdominates a label inULj∪TLjin line 10 to line 13. Finally, we update the sets of treated and untreated labels in line 16 and get a labelLn+1which provides the feasible activity flow with the minimal reduced cost from the node 0 to noden+1 performed on the timet*.

The pseudo code of the proposed exact dynamic programming is given in Algorithm 1.

Algorithm 1The proposed exact dynamic programming

4.3 Branching strategy

Since the column generation algorithm solves the linear relaxation model of the master problem, it cannot guarantee that the obtained solution is an integer solution[33]. If the obtained optimal solution is not an integer solution, a branching strategy needs to be adopted to properly modify the non-integer solution. Branching the activity flows in the RMP is a traditional branching strategy. Its disadvantage is the imbalance of the branch tree and the difficulty in solving the pricing subproblem.According to the characteristics of the model in this paper, we use the sum of the flow variables on arcs between operational activities to branch. This branching strategy neither increases the difficulty of solving the node subproblems, nor does it cause imbalance between the left and right subtrees.

5. Computational study

5.1 Test bed

In this paper, we design several test instances to verify the effectiveness of the robust WSOSSP model and the performance of the proposed branch-and-price algorithm.Since the number of operational activities in the mission(i.e., |V|) , the types of capabilities (i.e., |L|) and the number of weapon systems in the WSOS (i.e., |N|) will all affect the complexity of the WSOSSP, therefore, we select a subset of the iMOPSE dataset, and generate 10 test instances of different scales [34]. The iMOPSE dataset is a standard test dataset which is jointly created after a large number of data analysis and processing by many experienced project managers in Volvo’s IT department. Compared to the well-known PSPLIB benchmark dataset [35],the iMOPSE dataset not only includes the execution time of the scheduling plan, but also the economic cost and capability types. What is more, iMOPSE dataset can completely reflect the robust WSOSSP model.

The selected test instances in this paper has been presented in the Table 2, which are divided into two groups. The first group contains 100 activities and another group contains 200 activities. Within each group, different instances are distinguished according to the number of weapon systems and the number of priority relationships between operational activities. For each case, 9 or 15 different capability types have been set up. Each of these activities can be completed when it meets specified operational capability requirements and different system combinations that meet the capability requirements can perform different activities, consuming some resources at the same time. Because of the difference in the number of weapon systems and preceding relations, the computational complexity for each instance is varied.

Table 2 iMOPSE dataset instances

5.2 Computational results

We use the CPLEX 12.6 solver and the branch-and-price algorithm to calculate the optimal solutions for these 10 test instances. The calculation results are shown in Table 3 and the contents of the indicators in each column are explained as follows.

In Table 3, the three columns belong to the solution indicators of the CPLEX: the average calculation time of the algorithm is represented by “ACT”, the model optimal solution is represented by “OPT” and the number of explored nodes when the calculation is terminated is represented by “Node”. The following columns are related to the branch-and-price algorithm. The number of columns generated in the MP is represented by “col. in MP”. The average calculation time in the MP and the algorithm total time are represented by “ACT in MP” and “ACT”.“LB” represents the lower bound of the objective function, its corresponding solution is a relaxed real number solution, “OPT” represents the objective function obtained by the branch pricing algorithm, and its corresponding solution must be a feasible integer solution. The column “Node” represents the number of nodes searched by the branch-and-price algorithm. The calculation process is automatically terminated when the calculation time reaches 1 h. The last column “GAP” reflects the relative difference between the objective function values of the two algorithms. The “GAP” formula is given as follows:

Table 3 Performance comparison of the brand-and-price algorithm and CPLEX

In terms of average calculation time and the optimal solution, the performance of the branch-and-price algorithm is better than CPLEX. Firstly, we compare the average calculation time, as shown in the column “ACT”, the CPLEX solver obtained the optimal solution for 6 of the 10 instances, and the branch-and-price algorithm obtained the optimal solution for 8 instances within 1 h. For the same instance, the branch-and-price algorithm solves faster than CPLEX. Although the average calculation time of two algorithms increases sharply with the increase of the problem scale, the branch-and-price algorithm increases relatively slowly. The main reason is that CPLEX directly solves the linear relaxation model of the original model, so the lower bound at the root node is poor, and it takes plenty of time to find the optimal integer solution in the branch and bound process.

Secondly, in 4 of the 10 test instances, the gap is less than 0. This is because a tight lower bound is provided by the set partition formula in the subproblem. A tight lower bound cannot only improve the branching effect, but also save a lot of time for the branch and bound process. In instances 200-40-133-15 and 200-40-45-9, CPLEX does not find the optimal solution, while the branch-and-price algorithm find it in a limited time. In instances 200-40-90-9 and 200-40-91-15, neither algorithm finds the optimal solution, but it is obvious that the branch-and-price algorithm can get a better upper bound than CPLEX.

In addition, we compare the number of nodes explored in the two algorithms. As shown in the column “Node”,in the same instance, the number of nodes explored by CPLEX is much larger than the branch pricing algorithm.The two main reasons are as follows. On the one hand,the branch-and-price algorithm proposes a compact set partition method, which defines the activity flow in the scheduling process as columns. Compared with the intensive variables in the original model, the new model definition form can provide a tighter lower bound for calculation. On the other hand, due to the constraints of priority relationships and capability requirements, only activity flows that meet the constraints will be generated.Therefore, the scale of the MP is small, and the lower bound of the set partition model always corresponds to a relaxed solution.

As the instance size increases, the space and time complexity of the branch-and-price algorithm will increase exponentially. By comparing the calculation time of different stages in the algorithm, we find that solving the subproblem model will consume most of the time. That is because with increase in the scale of instances, the length of an activity flow in the subproblem grows dramatically(in some cases, an activity flow contains 20 elements). In other words, the process of dynamic programming in the subproblem model will take up a lot of calculation time.We are actually exploring a subproblem where the size of the network is growing exponentially. At the same time,it can be seen that as the problem scale increases, the number of “col. in MP” also increases exponentially, and the branch-and-price algorithm still has difficulties in solving large-scale instances.

6. Conclusions

The WSOS scheduling decisions are important for efficiently completing military missions. In this paper, we design a robust model to optimize the WSOSSP. At the same time, a slack robustness criterion is used to describe the uncertainty of the capabilities of the weapon system. A branch-and-price algorithm is developed to solve the model. We propose a novel set partitioning formulation, in which an activity flow is defined as a column. Thus, the subproblem is to identify the activity execution order and the distribution of member systems.The performance of the proposed algorithm is tested by several instances based on the iMOPSE dataset.

The results show that after optimizing, the makespan of the WSOSSP is significantly reduced. From the perspective of computational efficiency, the solution of the branchand-price algorithm is extremely stable, and its performance is significantly better than CPLEX, which can solve medium-scale instances in a reasonable time.