# Algorithms for Investment Project Distribution on Regions

Authors: Mafawez Alharbi; Mahdi Jemmali
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

This paper proposes an optimization system for solving an NP-hard problem by using several new algorithms and application programs. This study aims to identify a suitable distribution of investment projects across several developed industrial regions. It is assumed that all industrial regions involved have the same economic and strategic characteristics. The problem involves a set of projects that are to be assigned across regions. Each project creates an estimated number of new jobs, and the distribution of projects can be guided by minimizing the maximum total number of newly created jobs. The problem is NP-hard one, and it is difficult to determine the most appropriate distribution. We apply scheduling algorithms in order to solve the analyzed problem. Severalheuristics are developedto obtain the appropriate distribution of newly created jobs across all regions. A branch-and-bound method is employed in order to obtain the exact solution. The performance of the algorithm is demonstrated by the experimental results for a total number of 1850 instances.


---

## Body

## 1. Introduction

It is important to distribute investments throughout a given country. A “good” distribution of investment resources is very important both from an economic and a social perspective since this may have a direct effect on the behavior of cities in terms of business and economic cycles. The context of this paper is the regional allocation of industrial projects. The problem is as follows: when there are several projects to be assigned across different industrial regions, how should these projects be allocated?The solution to this problem may be based either on the principle of equity distribution or on a distribution process which is meant to minimize the maximum total number of projects to be assigned. We start with a set of projects to be undertaken in several regions, each of which represents an amount of newly created jobs and will be entirely undertaken in the chosen region. For the sake of equity, certain heuristics are applied to guide the allocation of industrial projects to different regions in order to increase the minimum total number of new jobs created [1]. To answer the research question, it is necessary to choose between minimizing the maximum total number of new jobs created and maximizing the minimum total number of new jobs created. In this study, we assume that the industrial regions involved are identical and that they share the same characteristics that affect both investment allocation and investment opportunities. For example, if the investment project consists in the creation of a marine port, then it should be allocated to a coastal region since this is an investment with specific economic characteristics. All types of investments with such specific characteristics will be excluded from this work. Heuristics and exact solutions will be used to ensure a good distribution of all investment projects to industrial regions.The solutions to the aforementioned problem affect individuals and their everyday activities and have significant impacts on the public and private sectors and on society at large. A wide variety of resource allocation methods with different mathematical approaches to medialization have previously been used in various application areas to compute optimal solutions to the problem of the distribution of projects to several regions. The present work aims to determine the distribution of investment projects across regions by using a new objective function and newly proposed mathematical model. New solutions were developed based on the utilization of the heuristics and the optimal solutions forPCmax (minimizing the maximum total completion time for parallel machines) and PCmin (maximizing the minimum total completion time for parallel machines). For the first problem, which is PCmax, we use the heuristics and optimal solution cited by Haouari and Jemmali [2]. The respective derived bounds cited in latter work were embedded in an exact procedure which yielded an exact and effective algorithm based on a symmetry-breaking branching strategy. For the second problem, PCmin, a branch-and-bound (B & B) algorithm was developed by Haouari and Jemmali [1] based on enhanced lower and upper bounds. The PCmin problem is also referred to as “machine covering.” A study of Walter et al. [3] also proposed an exact B & Bmethod.The rest of this paper is structured as follows. Section2 discusses previous work related to the aforementioned problem, while Section 3 sets forth the analyzed problem. Section 4 develops the lower bound for the analyzed problem, and Section 5 introduces and describes several heuristics. Section 6 presents the proposed solution, and Section 7 describes the experimental tests applied and their results. Section 8 concludes this paper.


## 2. Related Work

The theory of optimal control is used to tackle the unequal distribution of income between regions associated with high rates of aggregate growth for the regional allocation of investments [4]. Other applications for optimizing the allocation of investments include linear dynamic programming problems. The objective of a study by Ohtsuki [5] was to search for the optimum solution to the regional allocation problem. Bagchi et al. [6] provided a formulation for the problem of investment allocation across cities in the framework of a planning model, and a case study examining the impact of investment on the economies of Japan was carried out [7]. The study by Castells and Solé-Ollé [8] was undertaken in order to help managers make decisions, and in order to address the need for a system that provided data and information, two metaheuristic algorithms were compared, the first of which was based on a genetic algorithm and the second on the mean variance technique. The work of Salo et al. [9] focused on improved methods of resource allocation compared to the previous work that would facilitate decision analytics by helping public organizations and firms allocate resources for “lumpy” investment opportunities. Resource allocation problems are ubiquitous in governmental organizations and business. In addition to the aforementioned cited works, Luss [10] specifically addressed equitable resource allocation problems with applications in manufacturing, networks, communication, and other areas.Ranjbar et al. [11] investigated the problem of investment project scheduling with the purpose of reducing the related costs and the amount of necessary resources and of avoiding any delay in the implementation of those projects. The project in this case consisted in a set of interrelated activities, and the authors suggested two methods for resolving the project scheduling problem, which are a genetic algorithm and relinking, whereby a schedule is created with a list of priorities. Shadrokh and Kianfar [12] suggested a genetic algorithm to solve the resource investment problem. The performance of this algorithm has been noticed to be satisfactory when compared with that of other algorithms.Castells and Solé-Ollé [8] analyzed the main determinants of investment distribution across different regions. The expected objectives of the investment were set based on a general description of the objectives of the respective country, which focused on effective and fair trade and on the rules arising from political factors. This study employed a dynamic equation that allowed for gradual adjustment and readjustment, and the results indicated that criteria of effective trade played an important part in the geographical distribution of investment within the government infrastructure. Hartmann and Briskorn [13] provided an overview of the aforementioned extensions, which were designed based on the structure of the resource-constrained project scheduling problem (RCPSP). This paper gave a general summary related to the concepts of activity, precedence relationships, and resource constraints and also gave a summary of many lesser-known concepts. Singh [14] developed an algorithm that incorporated the priority of a project with the development of a programmed schedule, with the objective of reducing the project makespan and the penalty cost when some projects have higher priority. The proposed algorithm was shown to be an improvement of the current priority rules.Rodrigues and Yamashita [15] developed a new precise algorithm that solved the cost of the resource availability (RACP) problem in scheduling projects. This new algorithm relied on a hybrid method in which an initial feasible solution was determined heuristically. The branching scheme resolved an RCPSP at each node, where the resources of the RACP were fixed. The new algorithm can be employed for reducing the cost of making resources available.Sanaei et al. [16] studied the firefly algorithm, which was originally developed by Yang to optimize numerical tasks. This method was employed for solving an RCPSP. The difficulty in solving this type of problem arises from a lack of resources and priority of constraints. The algorithm begins by configuring a set of random scheduling solutions, and the primitive scheduling is then repeatedly improved using the firefly algorithm. Qi et al. [17] developed a model for multimode resources that reduced the cost of making resources available for all activities, with the aim of completing all activities of a project on schedule. When the deadline for a project is confirmed, the contractor will attempt to reduce the project cost, and this study proposes an optimization method and a useful heuristic algorithm for identifying the optimal solution. Rahmani et al. [18] proposed a new method for solving an RCPSP based on a differential search. Their approach could provide a set of preliminary schedules. Rabbani et al. [19] suggested a new approach to the multiobjective time-cost constrained RACP.Several other problems related to scheduling problem applications can be cited in [20–23] and [24].More recently, several works have proposed solutions for the fair distribution problem. For example, Jemmali [25] gave different approximate solutions for the project revenue assignment problem. Another study [26] focused on budget-balancing algorithms for solving the aforementioned problem and gave several algorithms. An application of load balancing of the files on different storage supports was treated in [27].


## 3. Description of the Problem

The problem analyzed in this paper can be described as follows. Given a set ofnp industrial investment projects P1 to be undertaken in nr different industrial regions Re, each project j can be assigned to only one industrial region i with i=1,…,nr. Each project j with j=1,…,np can be evaluated by applying three indicators. The number of newly created jobs is denoted by NJj. The objective of this study is to ensure a suitable distribution of projects, and it is essential to define a variable that can be evaluated in order to measure the performance of the project allocation process. In the first approach, the number of new jobs created was set as the objective variable, and the overall objective was to maximize the minimum total number of new jobs created. The question then arises as to whether minimizing the maximum total number of new jobs created yields the same result.When assigning a projectj to an industrial region i, the total cumulative number of new jobs created is denoted by tj. The total number of new jobs created in each region i after the project allocation is completed is denoted by Ci. Example 1 illustrates the analyzed problem. The maximum number of new jobs created for all regions is denoted by Cmax, and the minimum number of new jobs created for all regions is denoted by Cmin. For each schedule, the values of Ci are indexed as follows: C1≤C1≤⋯≤Cnr.Example 1.
We assume that, in the case of industrial investment projects, there are five new projects, i.e.,np=5. In addition, there are two regions, i.e., nr=2. Table 1 displays the number of new jobs created for each project.
Now, let us suppose that the assignment of projects to regions will be as follows. Projects 1, 4, and 5 are allocated to region 1, while projects 2 and 3 are allocated to region 2. Figure1 illustrates this allocation.
From Figure1, it can be noticed that there is a large gap between regions 1 and 2, which is equal to C2−C1=17. This means that more new jobs were created in region 2 than in region 1. The objective is to decrease this gap in order to ensure a better distribution between the regions involved. There is also another arrangement that can be used in order to ameliorate the manner of project assignment with the purpose of achieving a good project distribution. Figure 2 illustrates the new arrangement.
It can be seen from Figure2 that the gap between regions is lower compared with the one in the first arrangement shown in Figure 1. After rearrangement, the gap is reduced to three.Table 1
New jobs created in instance 1.
j12345NJj16262498Figure 1
Assignment in instance 1.Figure 2
Rearrangement for instance 1.Remark 1.
The gap for each regioni is given by Cmax−Ci.Proof.
The maximum number of new jobs created isCmax. Thus, for each region, Cmax−Ci gives the difference between the number of new jobs created in region i and that in the region with the maximum number of new jobs.
The indicator that can be measured to minimize the gap between regions is represented by the following formula:(1)Minimize∑i=1nrCmax−Ci,Proposition 1.
The objective described in equation (1) can be expressed as(2)MinimizenrCmax−∑i=1nrCi,Proof.
From equation (1), we have(3)∑i=1nrCmax−Ci=∑i=1nrCmax−∑i=1nrCi=nrCmax−∑i=1nrCi.
By applying the minimum function to the latter result, we obtain equation (2).
Hereafter, the gap between regions that was obtained by using a given heuristic is denoted bygmaxNJ=nrCmax−∑i=1nrCi. The objective of this study is to minimize gmaxNJ. It is worth mentioning that the constraint applied in this work consists in the fact that the project cannot be divided (i.e., the number of new jobs created by a project cannot be divided across two or more industrial regions). The optimal solution is denoted by gmaxNJ∗, and LBmax denotes the lower bound and UBmax the heuristic value for the PCmax problem.


## 4. Lower Bounds

Two lower bounds are proposed for the analyzed problem. The first is obtained from the optimal solution toPCmax and the optimal solution to PCmin. Hence, the balance between PCmax and PCmin will be considered. The second lower bound is obtained from the lower bound on PCmax. Cmax∗ denotes the optimal solution for PCmax, and Cmin∗ denotes the optimal solution for PCmin.


### 4.1. Min-Max-Based Lower Bound (MML)

This lower bound is determined based on the following proposition:Proposition 2.
MML=Cmax∗−Cmin∗. The obtained value (MML) is a valid lower bound.Proof.
In any scheduleσ, the value nrCmax−∑i=1nrCi is calculated after Cmax is evaluated. This value is the difference between Cmax and Ci for each region. This also indicates that the difference between Cmax and Ci for all the remaining regions (excluding the region that has Ci=Cmax) will be zero in this case.
In addition,σmax is the schedule obtained by applying the optimal solution to PCmax. In this schedule, it is obvious that no Ci is greater than Cmax, and hence, this schedule is the optimal one, with Cmax being minimized. Let us suppose that the aforementioned problem may be re-envisaged as follows. Let us assume that, in the ideal case, when the two regions with Cmax and Cmin are excluded, the remaining regions have the same number of new jobs, which is equal to Cmax. In this case, the comparison is only between Cmax and Cmin. Now, if this relaxation is applied while applying the schedule σmax, the minimum value can be obtained when the value of Cmin is maximized. Thus, the difference will be Cmax∗−Cmin∗. Accordingly, σmax is then selected, which is the schedule obtained by applying the optimal solution to PCmin and the relaxation; the ideal case has a difference of Cmax∗−Cmin∗. The proposition can also be written mathematically. For any schedule, Cmin≤Cmin∗ can be written as(4)−Cmin≥−Cmin∗.
Furthermore, in any schedule, we have(5)Cmax≥Cmax∗.
Combining equations (5) and (4) yields(6)Cmax−Cmin≥Cmax∗−Cmin∗.
From equation (6), it can be deduced that Cmax∗−Cmin∗ is a valid lower bound.


### 4.2. Cmax-Based Lower Bound (CML)

This lower bound is based on thePCmax one.The Cmax-based lower bound, denoted by CML, is based on the following proposition:Proposition 3.
For a given lower bound on thePCmax problem, LBmax, let CML=nrLBmax−∑j=1npNJj. The obtained value for CML is a valid lower bound.Proof.
From the objective function described in equation (2), we have ∑i=1nrCmax−Ci=∑i=1nrnr−∑i=1nrCi=nrCmax−∑i=1nrCi.
Furthermore, for any schedule, we have∑i=1nrCi=∑i=1npNJj. Therefore,(7)nrCmax−∑i=1nrCi=nrCmax=−∑j=1npNJj.
When considering the lower bound on thePCmax problem, we have(8)LBmax≤Cmax.
From equation (8), after multiplication by a positive integer, we obtain(9)nrLBmax≤nrCmax.
Then,∑j=1npNJj is subtracted from equation (9) to give(10)nrLBmax−∑j=1npNJj≤nrCmax−∑j=1npNJj.
From equations (7) and (10), it can be deduced that nrLBmax−∑j=1npNJj is the lower bound for the problem.
In this study, two lower bounds from the literature for thePCmax problem are used for developing two versions of CML. Denoted by LBFSCML and LBTVCML, these two lower bounds are based on L˜FS and L˜TV, respectively, as described by Haouari and Jemmali [2].


## 4.1. Min-Max-Based Lower Bound (MML)

This lower bound is determined based on the following proposition:Proposition 2.
MML=Cmax∗−Cmin∗. The obtained value (MML) is a valid lower bound.Proof.
In any scheduleσ, the value nrCmax−∑i=1nrCi is calculated after Cmax is evaluated. This value is the difference between Cmax and Ci for each region. This also indicates that the difference between Cmax and Ci for all the remaining regions (excluding the region that has Ci=Cmax) will be zero in this case.
In addition,σmax is the schedule obtained by applying the optimal solution to PCmax. In this schedule, it is obvious that no Ci is greater than Cmax, and hence, this schedule is the optimal one, with Cmax being minimized. Let us suppose that the aforementioned problem may be re-envisaged as follows. Let us assume that, in the ideal case, when the two regions with Cmax and Cmin are excluded, the remaining regions have the same number of new jobs, which is equal to Cmax. In this case, the comparison is only between Cmax and Cmin. Now, if this relaxation is applied while applying the schedule σmax, the minimum value can be obtained when the value of Cmin is maximized. Thus, the difference will be Cmax∗−Cmin∗. Accordingly, σmax is then selected, which is the schedule obtained by applying the optimal solution to PCmin and the relaxation; the ideal case has a difference of Cmax∗−Cmin∗. The proposition can also be written mathematically. For any schedule, Cmin≤Cmin∗ can be written as(4)−Cmin≥−Cmin∗.
Furthermore, in any schedule, we have(5)Cmax≥Cmax∗.
Combining equations (5) and (4) yields(6)Cmax−Cmin≥Cmax∗−Cmin∗.
From equation (6), it can be deduced that Cmax∗−Cmin∗ is a valid lower bound.


## 4.2. Cmax-Based Lower Bound (CML)

This lower bound is based on thePCmax one.The Cmax-based lower bound, denoted by CML, is based on the following proposition:Proposition 3.
For a given lower bound on thePCmax problem, LBmax, let CML=nrLBmax−∑j=1npNJj. The obtained value for CML is a valid lower bound.Proof.
From the objective function described in equation (2), we have ∑i=1nrCmax−Ci=∑i=1nrnr−∑i=1nrCi=nrCmax−∑i=1nrCi.
Furthermore, for any schedule, we have∑i=1nrCi=∑i=1npNJj. Therefore,(7)nrCmax−∑i=1nrCi=nrCmax=−∑j=1npNJj.
When considering the lower bound on thePCmax problem, we have(8)LBmax≤Cmax.
From equation (8), after multiplication by a positive integer, we obtain(9)nrLBmax≤nrCmax.
Then,∑j=1npNJj is subtracted from equation (9) to give(10)nrLBmax−∑j=1npNJj≤nrCmax−∑j=1npNJj.
From equations (7) and (10), it can be deduced that nrLBmax−∑j=1npNJj is the lower bound for the problem.
In this study, two lower bounds from the literature for thePCmax problem are used for developing two versions of CML. Denoted by LBFSCML and LBTVCML, these two lower bounds are based on L˜FS and L˜TV, respectively, as described by Haouari and Jemmali [2].


## 5. Approximate Solutions

In this section, certain heuristics developed for the problem under study are presented, and these are compared to demonstrate their performance. The first heuristic is based on the nonincreasing dispatching rule, while the second is based on the nondecreasing dispatching rule. The multifit method is employed for deriving the third heuristic. In the fourth approach, we apply several times the resolution of the subset-sum problem in order to calculate the value of the heuristic. In a similar way, the fifth heuristic will solve a well-known problem iteratively; difference lies in choosing the knapsack problem which is used rather than the subset-sum problem. The last heuristic is based on rescheduling of the most charged and least charged regions to find a better result.


### 5.1. Heuristic 1: Nonincreasing Number of New Jobs Created (NIJ)

For this schedule, the total number of new jobs created for all projects is placed in a nonincreasing order. HighestNJj is then allocated to the first region on the list, i.e., the one with the lowest number of new jobs created.Example 2.
In this example, the same instance cited in Example1 is considered. Figure 3 shows the schedule after applying NIJ.Figure 3
Schedule after applyingNIJ in instance 1.(11)gmaxNJ=2×43−43+40=86−83=3.


### 5.2. Heuristic 2: Nondecreasing Number of New Jobs Created (NDJ)

In this schedule, the total number of new jobs created for all projects is placed in a nondecreasing order. LowestNJj is then allocated to the first region on the list, i.e., the one with the lowest number of new jobs created. The schedule obtained after applying NDJ is as follows: region 1: 5,1,2 and region 2: 4,3. Thus, gmaxNJ=50−33=17.


### 5.3. Heuristic 3: Multifit Heuristic Based on the Number of New Jobs Created (MFJ)

This approximate solution is inspired by the machine job scheme presented by LEE and David Massey [28]. This method uses the bin-packing method for determining the minimum capacity that will allow all n new jobs created to fit into the m regions. For each bin capacity, the first-fit decreasing (FFD) method is employed for fitting the number of newly created jobs to the bin. Let us assume that the number of new jobs was ordered such that NJ1≥⋯≥NJnp. The FFD method successively assigns the project to the lowest indexed region with the necessary capacity for that respective number of new jobs. Hence, LBmax=maxNJ1,NJnr+NJnr+1,∑j=1npNJj/nr, and UBmax is the value achieved by applying the LPT heuristic for PCmax. Here, bin denotes the number of bins used after applying FFD, and iter is a predetermined, fixed number of iterations for FFD. In this study, iter=35.TheMFJ algorithm is illustrated in Algorithm 1.Algorithm 1:MFJ algorithm.
Step0. Set I=0, Cu=UBmax, and Cl=LBmax.Step1. Set C=Cu+Cl/2. Set I=I+1.Step2. Apply FFD with capacity C.Step3. If all projects np can be assigned to nr regions, then set Cu=C and go to Step 4; else, Cl=C and go to Step 4.Step4. If I=iter then STOP; otherwise, go to Step 1.End. If bin>nr or bin<nr, then the result given by LPT is accepted; otherwise, the result given by FFD is accepted.Example 3.
Assume that, in case of industrial investment projects, the number of projects is equal to10, i.e., np=10. In addition, there are two regions, i.e., nr=2. Table 2 presents the number of new jobs created for each project.
For the instance given in Table2, UBmax=363 and LBmax=354. C=363+354/2=358. Now, FFD function should be applied for a capacity equal to C and the 10 items represented by instance 2 after arranging them in the nonincreasing order The first bin contains items with weights 79,88,90,99, while the second contains items with weights 21,45,55,62,83,85. The first bin has a total load of 356, and the second has a total load of 351, giving gmaxNJ=356−351=5. Comparing this value with the results obtained using NIJ, we see that the associated gmaxNJ is equal to 19. This example shows that the results obtained using MFJ are better than those obtained using NIJ. However, the difference in the number of new jobs created in regions 1 and 2 after applying MFJ is only 5.Table 2
New jobs created in instance 2.
j12345678910Njj62885521904599798385


### 5.4. Heuristic 4: Subset-Sum Problem-BasedCSS Approach

This heuristic is based on a greedy algorithm. It is denoted byPkk=1,…,nr−1 as follows:(12)Pk:minimize∑Jj∈SkNJjyjsubject to∑Jj∈SkNJjyj≥LSk,nr−k+1yj∈0,1∀Jj∈Sk.(i)
S1=PI and Sk=1=Sk/PIk, where PIk is an optimal subset sum for Pkk=1,…,nr−1.(ii)
LS,K denotes a valid lower bound for PCmax on the makespan of a reduced instance, defined by k≤nr regions and a subset of the number of new jobs created S⊆PI. Hence, the first region will be the number of new jobs created until L on P1 is reached. The remaining number of new jobs created in the remaining regions will constitute the second problem P2, which will consist in solving the new SSP until L is reached, and so on [29]. The subset-sum problem will be solved by using the dynamic programming algorithm developed by Pisinger [30] to solve the subset-sum problem.


### 5.5. Heuristic 5: Knapsack Problem-BasedCKS Approach

This heuristic is based on the division of the main problem intom smaller problems, each of which involves scheduling of the projects to regions. In the first region, a knapsack problem is used to assign a project to region 1, and the remaining projects are assigned to the remaining regions using a further knapsack problem, and so on. For each region, a knapsack problem must be solved as follows:(13)kNk:minimize∑j∈Fkwjxjsubject to∑j∈FkNJjxj≤∑j∈FkNJjkxj∈0,1∀j∈Fk.(i)
F1=PI and Fk=1=Fk/PIk, where PIk is an optimal knapsack for kNkk=1,…,nr−1.(ii)
wj=Fk/k×NJj−1, where Fk is the number of remaining projects, and k is the number of remaining regions. Hence, for the first region, the new jobs created are assigned until ∑j∈F1NJj/nr on KN1 is reached. The remaining number of new jobs created and the remaining regions form the second problem KN2 to be solved via a new knapsack problem until ∑j∈F2NJj/nr−1 is reached, and so on.


### 5.6. Heuristic 6: Min-Max Iteration Heuristic (MMI)

This heuristic is based on the reformulation ofP2Cmax as a subset-sum problem [29]. In each iteration, the most loaded region rmax and the least loaded region rmin were fixed, and a subset-sum problem was solved with the projects assigned to rmax and rmin. This procedure was repeated several times, and the best solution was identified. The number of iterations was set to 100 based on an experimental study.


## 5.1. Heuristic 1: Nonincreasing Number of New Jobs Created (NIJ)

For this schedule, the total number of new jobs created for all projects is placed in a nonincreasing order. HighestNJj is then allocated to the first region on the list, i.e., the one with the lowest number of new jobs created.Example 2.
In this example, the same instance cited in Example1 is considered. Figure 3 shows the schedule after applying NIJ.Figure 3
Schedule after applyingNIJ in instance 1.(11)gmaxNJ=2×43−43+40=86−83=3.


## 5.2. Heuristic 2: Nondecreasing Number of New Jobs Created (NDJ)

In this schedule, the total number of new jobs created for all projects is placed in a nondecreasing order. LowestNJj is then allocated to the first region on the list, i.e., the one with the lowest number of new jobs created. The schedule obtained after applying NDJ is as follows: region 1: 5,1,2 and region 2: 4,3. Thus, gmaxNJ=50−33=17.


## 5.3. Heuristic 3: Multifit Heuristic Based on the Number of New Jobs Created (MFJ)

This approximate solution is inspired by the machine job scheme presented by LEE and David Massey [28]. This method uses the bin-packing method for determining the minimum capacity that will allow all n new jobs created to fit into the m regions. For each bin capacity, the first-fit decreasing (FFD) method is employed for fitting the number of newly created jobs to the bin. Let us assume that the number of new jobs was ordered such that NJ1≥⋯≥NJnp. The FFD method successively assigns the project to the lowest indexed region with the necessary capacity for that respective number of new jobs. Hence, LBmax=maxNJ1,NJnr+NJnr+1,∑j=1npNJj/nr, and UBmax is the value achieved by applying the LPT heuristic for PCmax. Here, bin denotes the number of bins used after applying FFD, and iter is a predetermined, fixed number of iterations for FFD. In this study, iter=35.TheMFJ algorithm is illustrated in Algorithm 1.Algorithm 1:MFJ algorithm.
Step0. Set I=0, Cu=UBmax, and Cl=LBmax.Step1. Set C=Cu+Cl/2. Set I=I+1.Step2. Apply FFD with capacity C.Step3. If all projects np can be assigned to nr regions, then set Cu=C and go to Step 4; else, Cl=C and go to Step 4.Step4. If I=iter then STOP; otherwise, go to Step 1.End. If bin>nr or bin<nr, then the result given by LPT is accepted; otherwise, the result given by FFD is accepted.Example 3.
Assume that, in case of industrial investment projects, the number of projects is equal to10, i.e., np=10. In addition, there are two regions, i.e., nr=2. Table 2 presents the number of new jobs created for each project.
For the instance given in Table2, UBmax=363 and LBmax=354. C=363+354/2=358. Now, FFD function should be applied for a capacity equal to C and the 10 items represented by instance 2 after arranging them in the nonincreasing order The first bin contains items with weights 79,88,90,99, while the second contains items with weights 21,45,55,62,83,85. The first bin has a total load of 356, and the second has a total load of 351, giving gmaxNJ=356−351=5. Comparing this value with the results obtained using NIJ, we see that the associated gmaxNJ is equal to 19. This example shows that the results obtained using MFJ are better than those obtained using NIJ. However, the difference in the number of new jobs created in regions 1 and 2 after applying MFJ is only 5.Table 2
New jobs created in instance 2.
j12345678910Njj62885521904599798385


## 5.4. Heuristic 4: Subset-Sum Problem-BasedCSS Approach

This heuristic is based on a greedy algorithm. It is denoted byPkk=1,…,nr−1 as follows:(12)Pk:minimize∑Jj∈SkNJjyjsubject to∑Jj∈SkNJjyj≥LSk,nr−k+1yj∈0,1∀Jj∈Sk.(i)
S1=PI and Sk=1=Sk/PIk, where PIk is an optimal subset sum for Pkk=1,…,nr−1.(ii)
LS,K denotes a valid lower bound for PCmax on the makespan of a reduced instance, defined by k≤nr regions and a subset of the number of new jobs created S⊆PI. Hence, the first region will be the number of new jobs created until L on P1 is reached. The remaining number of new jobs created in the remaining regions will constitute the second problem P2, which will consist in solving the new SSP until L is reached, and so on [29]. The subset-sum problem will be solved by using the dynamic programming algorithm developed by Pisinger [30] to solve the subset-sum problem.


## 5.5. Heuristic 5: Knapsack Problem-BasedCKS Approach

This heuristic is based on the division of the main problem intom smaller problems, each of which involves scheduling of the projects to regions. In the first region, a knapsack problem is used to assign a project to region 1, and the remaining projects are assigned to the remaining regions using a further knapsack problem, and so on. For each region, a knapsack problem must be solved as follows:(13)kNk:minimize∑j∈Fkwjxjsubject to∑j∈FkNJjxj≤∑j∈FkNJjkxj∈0,1∀j∈Fk.(i)
F1=PI and Fk=1=Fk/PIk, where PIk is an optimal knapsack for kNkk=1,…,nr−1.(ii)
wj=Fk/k×NJj−1, where Fk is the number of remaining projects, and k is the number of remaining regions. Hence, for the first region, the new jobs created are assigned until ∑j∈F1NJj/nr on KN1 is reached. The remaining number of new jobs created and the remaining regions form the second problem KN2 to be solved via a new knapsack problem until ∑j∈F2NJj/nr−1 is reached, and so on.


## 5.6. Heuristic 6: Min-Max Iteration Heuristic (MMI)

This heuristic is based on the reformulation ofP2Cmax as a subset-sum problem [29]. In each iteration, the most loaded region rmax and the least loaded region rmin were fixed, and a subset-sum problem was solved with the projects assigned to rmax and rmin. This procedure was repeated several times, and the best solution was identified. The number of iterations was set to 100 based on an experimental study.


## 6. Exact Solution

The exact solution was developed using theB & B method.Corollary 1.
MinimizenrCmax−∑i=1nrCi is equivalent to MinimizeCmax.Proof.
Proof. For each schedule,∑i=1nrCi=∑j=1npNJj, and the objective of the studied problem can therefore be written as follows: MinimizenrCmax−∑j=1npNJj. The total number of regions involved m and the summation of all new jobs created ∑j=1npNJj are determined in advance and are fixed. This indicates that MinimizenrCmax−∑j=1npNJj is equivalent to MinimizenrCmax−∑j=1npNJj, which is equivalent to MinimizeCmax.Lemma 1.
The optimal solution to the approached problem is(14)nrCmax∗−∑j=1npNJj.Proof.
Based on the Corollary1 above, MinimizenrCmax−∑i=1nrCi is equivalent to MinimizeCmax.
Based on the definition ofPCmax, the problem is Cmax∗=MinimizeCmax. Hence, MinimizenrCmax−∑i=1nrCi is equal to nrCmax∗−∑j=1npNJj.


## 7. Experimental Results

In this section, we present the results given after the implementation of all algorithms coded in C++ using an Intel(R) Xeon(R) CPU E5-2687W v4 @ 3.00 GHz and 64 GB RAM. Several instances and statistical analyses are presented in order to illustrate the results obtained by applying the algorithms described in the previous sections. Different instances were generated which were inspired by Dell’Amico and Martello [31]. The overall instances were based on the choice of n, m, and the type of new jobs created, which is denoted by Class. The selection of the pair np,nr was as follows: np=10,15,50,100,200,300 and nr=2,3,5,10,20,25,50. Table 3 shows the fixed distribution of np,nr.Table 3
Choice ofnp,nr.
npnr102,3,5152,3,5,10502,3,5,10,20,25100,200,3002,3,5,10,20,25,50The number of new jobs created was calculated according to the 5 distributions in the following, whereU denotes the discrete uniform distribution and N the normal distribution.Class1: U20−100; Class2: U20−500; Class3: U100−500; Class4: N50,100; and Class5: N20,100. For each fixed (np,nr,Class), 10 instances were generated, giving 1850 instances in total. The following notations were used:(i)
U indicates the best (minimum) value obtained after execution of all heuristics.(ii)
UB represents the analyzed heuristic.(iii)
Min is the number of instances for which the analyzed upper bound is equal to U.(iv)
GAPu=UB−U/U represents the gap between the value obtained by applying the analyzed heuristic and the one obtained by executing the single best heuristic.(v)
AGAPu is the average GAPu for all heuristics.(vi)
L is the best (maximum) value obtained after execution of all lower bounds.(vii)
LB is the lower bound for the problem.(viii)
Max is the number of instances for which the analyzed lower bound is equal to L.(ix)
GAPl=L−LB/LB represents the gap between the value obtained by applying the analyzed lower bound and the one obtained by executing the single best lower bound.(x)
AGAPu is the average GAPu for all lower bounds.(xi)
Time represents the time required to execute the heuristic or lower bound or exact solution for a corresponding instance. It is measured in seconds and is denoted by “−” if it is less than 0.001s.(xii)
Timet is the average time for all lower bounds (or heuristics). It is measured in seconds and is denoted by “−” if it is less than 0.001s.(xiii)
NN is the average number of nodes created in the B & B method.(xiv)
NS is the total number of instances that is unsolved by the B & B algorithm.In this study, the aforementioned analyses are based on several criteria. The main criterion lies in analyzing the results obtained based on the variations in the gap and time according to the variation innp, nr, and Class. A comparison between the lower bounds provides information on the time spent and the related gap.The results of comparing the best lower bound and the best heuristic are significant. The average total gap betweenMin and Max in all 1850 instances is 0.18, with an average time of 19.99s. This result was obtained based on the performance of the heuristic and lower bounds. Another notable result is the number of times that the lower bound was equal to the upper bound: 1684 from a total of 1850 instances (representing 91.03% of the total number of instances). This indicates that the optimal solution is reached when the lower and upper bounds are calculated. An exact solution is required for only 8.97% of the overall instances. It is worth mentioning that, for the lower bound MML which is based on the solution provided by the B & B method, if the instance is not solved by the B & B method, then the value of Cmax∗ is not determined. In this case, the best lower bound for PCmax is chosen. The same procedure is followed for PCmin.In Table4, it is obvious that the gap increases when m increases for MML. This phenomenon is not applicable for LBTVCML and LBFSCML. For LBTVCML, when nr=2, GAPl=0.06, and when nr=5, GAPl=1.71, but when nr=10, the value of the gap decreases to 0.02. The values of Time, as illustrated by Table 4, do not vary along with other values. The maximum time was 467.640 s and was reached when nr=50 for the MML bound. This is because this last lower bound is a consequence of solving two different problems in an exact way. The shortest time was achieved for LBTVCML and was less than 0.001s. The total minimum gap was 0.04 and was obtained for nr=2.Table 4
Behavior ofGAPl and Time according to nr.
nrMMLLBTVCMLLBFSCMLTotalGAPlTimeGAPlTimeGAPlTimeAGAPlTimet20.000.2680.060.0010.060.0020.040.09030.281.1041.24—1.230.0010.920.36951.051.4641.710.0380.480.0461.080.516103.777.3400.020.0440.000.0601.272.481207.72419.4150.120.0840.100.1402.65139.8802511.16316.2030.770.0970.000.1833.98105.4955023.03467.6402.550.2010.000.4718.53156.104Other analyses are illustrated in Table5, which shows the variation in the gap and time according to the number of new jobs created.Table 5
Behavior ofGAPl and Time according to np.
npMMLLBTVCMLLBFSCMLTotalGAPlTimeGAPlTimeGAPlTimeAGAPlTimet100.530.8143.94—1.370.0011.950.272151.123.3261.06—0.820.0011.001.109503.12595.6140.740.0010.090.0191.31198.5451007.70294.1131.700.0060.000.0633.1398.0602007.6827.4500.000.0310.000.0922.569.1913008.436.1230.000.0880.000.1652.812.1255008.298.7630.030.2490.010.3602.783.124Time increases whennp increases for LBTVCML and LBFSCML. The smallest gap of zero is obtained for LBFSCML when np=100,np=200, and np=300. The maximum gap value, which is 8.413, was obtained for MML when np=300. The total maximum time was 198.545s for nr=50. This explains the nonresolved exact solution provided by employing the B & B method for calculation of MML.Table6 presents the variation in gap and time according to Class. Table 6 shows that all classes are approximately characterized by the same magnitude of difficulty.Table 6
Variation ofGAPl and Time according to Class.
ClassMMLLBTVCMLLBFSCMLTotalGAPlTimeGAPlTimeGAPlTimeAGAPlTimet15.97149.8720.240.0520.050.0962.0950.00725.72157.5691.100.0520.330.1092.3852.57735.86177.2341.850.0650.520.1182.7459.13945.99144.3490.290.0490.130.1032.1448.16755.83128.8310.690.0860.040.1422.1943.019In Table7, Perc indicates that the percentage of the analyzed lower bound is equal to the best value of all lower bounds for all total number of instances.Table 7
Comparison between lower bounds.
MMLLBTVCMLLBFSCMLMax70316761774Perc38.00%90.59%95.89%GAPl5.870.840.22Time151.5710.0610.114In Table7, it can be noticed that the best lower bound, which reaches a maximum percentage of 95.89%, is LBFSCML, with an average gap of 0.22 and an average execution time of 0.114s. The minimum percentage of approximately 38.00% is obtained by MML, with a gap of 5.87 and an execution time of 151.571s.Further information on the results obtained is included in Table8.Table 8
Lower bound details.
npnrMMLLBTVCMLLBFSCMLGAPlTimeGAPlTimeGAPlTime1020.000.3830.44—0.44—30.140.9613.67—3.660.00151.451.0977.72—0.000.0021520.000.3970.00—0.00—30.381.1880.04—0.040.00150.052.6954.17—3.260.002104.069.0250.03—0.000.0035020.000.2720.00—0.000.00130.321.1650.000.0010.000.00151.221.7780.000.0010.000.003103.823.9350.000.0010.000.008202.952070.0170.610.0020.510.0272510.391496.5193.850.0010.000.07610020.000.2390.00—0.000.00150.901.7190.000.0020.000.007103.583.4470.000.0040.000.016208.527.8160.000.0070.000.0382512.7960.1800.000.0080.000.0545020.391691.27510.220.0130.000.26020020.000.2430.00—0.000.00251.301.1770.000.0140.000.018104.023.0650.000.0230.000.043208.046.7140.000.0360.000.0892510.468.6380.000.0410.000.1155022.27144.8660.000.0730.000.28730020.000.1760.00—0.000.00251.401.1340.000.0390.000.045103.062.8360.000.0650.000.0882010.986.6010.000.1040.000.1782511.008.0460.000.1220.000.2195024.1417.9420.000.1980.000.45850020.000.1630.000.0060.000.00951.030.6480.080.2060.080.245104.1021.7310.100.1720.000.204208.105.9270.000.2730.000.3682511.147.6310.000.3150.000.4535025.3416.480.000.5230.000.881To show how the analyzed heuristics perform, several tables of results are presented and discussed. The analyses are based on the variations inGAPu and Time with np, nr, and Class. Table 9 presents the variations in gap and time based on the number of regions.Table 9
Behavior ofGAPu and Time according to nr.
nrNDJNIJMFJCSSCKSMMIGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTime268.61—5.45—2.720.0020.00—0.00—0.000.0123116.23—19.83—12.15—0.54—0.43—0.000.0085166.34—5.40—4.060.0030.56—0.760.0010.000.01310302.96—18.41—12.360.0040.400.0010.130.0010.000.01420335.60—21.92—14.520.0052.730.0013.170.0030.000.01425371.27—24.46—15.660.0058.180.0011.320.0030.000.01450491.61—37.99—24.190.0068.110.0032.340.0070.000.018It is obvious in Table9 that the MMI heuristic has a constant gap of zero for all values of nr. The heuristics NDJ and NIJ are much faster than the others, and the necessary execution time for these heuristics is lower than 0.001s. The maximum gap of 491.61 is achieved for NDJ when nr=50. Furthermore, the highest time consumption of 0.018s is seen for MMI for nr=50. The results show that, in almost all cases, MMI provides better results than other heuristics, but there is no dominance amongst the heuristics. Table 10 compares GAP and Time based on np.Table 10
Behavior ofGAPu and Time according to np.
npNDJNIJMFJCSSCKSMMIGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTime1040.59—8.39—3.790.0000.55—0.85—0.0000.0051564.68—10.92—6.980.0011.01—1.18—0.0000.00850128.78—14.88—9.430.0012.480.0013.690.0010.0000.010100252.70—23.27—15.320.0027.510.0011.410.0020.0000.007200320.66—19.21—12.870.0044.410.0010.190.0030.0000.016300383.54—22.02—14.390.0060.350.0010.000.0030.0000.024500402.88—14.10—9.060.0100.120.0020.020.0040.0000.017As it can be noticed in Table10, the gap does not vary along with the variation of np values. The time increases according to np for CSS. The results of all executed heuristics are shown in Figure 4, where an increasing curve can be noticed.Figure 4
Variation ofAGAPu according to np.From Table11, it is vivid that there is a difference between the classes in terms of difficulty.Table 11
Behavior ofGAPu and Time according to np.
npNDJNIJMFJCSSCKSMMIGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTime1101.69—6.09—4.400.0050.820.0010.890.0020.0010.3782432.12—24.80—12.790.0024.680.0011.360.0020.0010.5853360.65—21.86—17.160.0064.960.0011.240.0020.0010.5664263.52—19.53—9.310.0010.910.0010.890.0020.0010.5105100.38—12.82—11.160.0061.460.0010.910.0020.0010.473For theCSS heuristic, the greatest values for the gap can be noticed for Classes2 and 3, meaning that these classes are more difficult to solve than the others for CSS. The same behavior was noticed for the CKS, MFJ, NDJ, and NIJ heuristics. It can be concluded that this problem is more difficult to solve for Classes2 and 3. Furthermore, this heuristic is more time-consuming, reaching 0.585s for Class2.In Table12, it is vivid that the best heuristic is MMI, with the highest percentage of 98.2%, an average gap of zero, and an average execution time of 0.502s. The lowest percentage that is 14.5% was obtained by NDJ, with a gap of 251.67 and a time of less than 0.001s. Further information on the results obtained is included in Table 13.Table 12
Comparison between the heuristics overall in 1850 instances.
NDJNIJMFJCSSCKSMMIMin268605680150715581817perct14.5%32.7%36.8%81.5%84.2%98.2%GAPu251.6717.0210.972.571.060.00Time——0.0040.0010.0020.502Table 13
Detailed heuristics for all 1850 instances.
npnrNDJNIJMFJCSSCKSMMIGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTimeGAPuTime10276.10—13.86—5.040.0010.00—0.00—0.000.004341.90—11.19—6.32—0.88—0.94—0.000.00553.77—0.11—0.00—0.76—1.62—0.000.00615269.34—15.40—8.78—0.000.0010.00—0.000.0073162.32—23.55—16.230.0010.74—0.36—0.000.008524.83—4.73—2.930.0013.17—3.67—0.000.008102.22—0.00—0.000.0010.14—0.670.0010.000.00950254.24—2.40—1.040.0010.000.0010.00—0.000.0093144.48—24.75—13.92—0.00—0.00—0.000.0105176.76—12.13—10.350.0020.00—0.000.0010.000.01110355.62—41.15—27.370.0011.500.0010.000.0010.000.0112035.12—8.75—3.91—10.510.00115.860.0020.000.010256.48—0.11—0.000.0022.840.0016.300.0010.000.008100259.04—2.16—1.360.0030.00—0.00—0.000.0065259.63—9.71—7.490.0030.000.0010.000.0010.000.00510436.92—37.01—24.130.0020.000.0000.000.0010.000.00420413.24—48.26—32.550.0023.120.0010.000.0020.000.00625339.63—42.27—26.380.00238.060.0010.280.0030.000.009507.77—0.24—0.000.0033.870.0038.200.0050.000.012200284.48—2.36—1.640.0030.000.0010.00—0.000.0135218.62—4.66—3.240.0040.00—0.000.0010.000.01510240.44—8.97—6.200.0040.000.0010.000.0010.000.01620381.60—25.17—17.860.0040.000.0010.000.0030.000.01725541.64—35.05—22.270.0040.000.0010.000.0030.000.01850457.16—39.03—25.990.00326.450.0031.170.0070.000.019300280.72—1.00—0.400.0040.00—0.00—0.000.0215204.78—3.94—3.020.0060.000.0010.000.0010.000.02310431.95—12.70—8.710.0060.000.0010.000.0020.000.02320269.86—11.30—8.030.0060.000.0010.000.0030.000.02325458.49—26.13—16.550.0060.000.0010.000.0040.000.02450855.45—77.06—49.650.0072.130.0030.000.0070.000.028500256.32—0.96—0.760.0050.000.0010.00—0.000.0235275.98—2.53—1.380.0080.000.0010.000.0010.000.02110350.62—10.65—7.790.0100.740.0010.100.0020.000.01820578.18—16.10—10.240.0110.000.0020.000.0040.000.01625510.10—18.75—13.090.0110.000.0020.000.0050.000.01050646.07—35.62—21.110.0130.000.0040.000.0100.000.014Now, the experimental study focuses on the gap between the values of the minimum heuristic and the maximum lower bound. This requires a comparison between the best lower bound (L) and the best heuristic (U), denoted by GAPlu=U−L/L. In Table 14, the maximum gap is 0.74, which is obtained when np=50, and the average time is 98.194s. For np=200, np=300, and np=500, the gap is zero, indicating that the optimal solution is obtained.Table 14
Variation ofGAPlu according to np.
npGAPluTime100.150.274150.370.547500.7498.1941000.0348.5192000.004.6093000.001.1195000.001.632Figure5 shows the variation in GAPlu with the number of new jobs created, which peaks when np=50 and tends asymptotically to zero when np is higher.Figure 5
Variation of theGAPlu value according to np.Table15 illustrates the impact of the number of regions on the analyzed problem and shows that the maximum gap of 0.86 is reached when nr=20. However, a minimum gap of zero is reached for nr=2 with a reasonable time of 0.048s and for nr=10 with a time of 1.262s.Table 15
Variation ofGAPlu according to nr.
nrGAPluTime20.000.04830.150.18650.210.268100.001.262200.8687.197250.0353.175500.0578.235Table16 shows the variation in GAPlu and Time with Class. This table confirms once again that Classes 2 and 3 are more difficult to solve and require more time for that by comparison with Classes 1, 4, and 5. The maximum gap of 0.23 is obtained for Class2, and a value of 0.28 is seen for Class3.Table 16
Variation ofGAPlu according to Class.
ClassGAPluTime10.1425.03520.2326.33730.2829.61740.1824.12650.0621.550The performance of the exact solution was determined by applying theB & B method, and the time limit settled at 1200s. If the time required for solving an instance and obtaining the exact solution exceeded this time limit, the resolution process was stopped, and it was noted that the respective instance remained unresolved.Table17 presents the results obtained by employing the B & B method based on the number of new jobs created. It is vivid that the number of unsolved instances is higher when np=50 with NS=48 and for np=100 with NS=20. The corresponding numbers of nodes are 3,019,072 and 725,107, respectively. However, when the number of new jobs created is greater than 100, the problem is solved rapidly and easily, with a time of 6.572s for np=500 as compared with a time of 195.614s for np=50. A total of 70 instances remained unresolved when employing the B & B method which represents 3.78% of the total number of instances that is 1850.Table 17
Behavior ofNS, NN, and Time according to np.
npgmaxNJ∗NSNNTime100540.80515017121.23950483,019,072195.61410020725,10786.107200246,38815.409300016.108500077786.572Table18 shows that the instances that remained unresolved when using the exact method are concentrated for nr=20, nr=25, and nr=50. The maximum value of Time was observed when nr=20 and was equal to 179.407s.Table 18
Behavior ofNS, NN, and Time according to nr.
nrgmaxNJ∗NSNNTime2090.267304271.098508111.39010077783.85320362,344,630179.40725121,278,25766.58850221,157,241149.563Table19 shows the differences between classes for the exact solution gmaxNJ∗.Table 19
Behavior ofNS, NN, and Time according to Class.
ClassgmaxNJ∗NSNNTime115763,86652.394214510,57351.7173201,008,23969.979413582,93746.72558215,07231.380In Table19, it obvious that the maximum number of unsolved instances was obtained for Class3 with NS=20. Further results obtained by employing the B & B method is presented in Table 20.Table 20
Branch-and-bound result.
npnrgmaxNJ∗NSNNTime1020260.382301310.9565061.0781520330.3973011491.1755056651.95710011.428502010.2723011.1645011.77810013.934203611,723,146870.01725126,391,280296.5191002010.2385011.71810013.44720017.813250112.15150204,350,639491.2752002010.2435011.17610013.06420016.70525018.623502278,32472.6433002010.1765011.13210012.82920016.58625018.030500117.8965002010.1635010.88810046,6648.41820015.91425017.615500116.44The results included in Tables17 and 18 motivated an investigation of np and nr in order to determine the instances which are the most difficult to solve. A study based on the ratio np/nr was carried out. For any ratio np/nr for the given instances amongst the total number of 1850 instances, the unsolved instances NS, the average number of nodes NN, and the average value of Time were calculated.For the total number of instances given at the beginning of this section, there were 22 different values of the rationp/nr. The results are illustrated in Table 21. Indeed, Table 21 shows the performance indicators used for measuring the results obtained by the B & B method for variations in the ratio np/nr.Table 21
Rationp/nr results of branch-and-bound analysis.
Indexnp/nrNSNNTime11.5011.42822323,580,642262.95732.53611,723,146870.01743056651.95753.3301310.956642139,16242.3977502943.326860117.89697.50330.397108018.6231110017.0921212018.0301315016.5861416.66011.1641520014.1321625013.0931730012.8291840011.1761950023,3324.32820100011.13221150010.17622250010.163The maximum average time of870.017s was obtained for np/nr=2.5. It is obvious that the unsolved instances were concentrated for np/nr=2 and np/nr=2.5. It can therefore be concluded that these types of instances are the most difficult to solve. Figure 6 shows the concentrated unsolved instances for index 2 and index 3, which are represented in Table 21 and referred to as np/nr=2 and np/nr=2.5, respectively.Figure 6
Variation ofNS according to n/m.The rationp/nr represents the economic scale that can define the hardness of the problem to give a fair distribution of the projects to create new jobs on the regions. The experimental results give an appreciated gap between regions using heuristics. On the contrary, the exact method gives the optimal solution of the problem analyzed. Reducing the gap related to the new job created between regions decreases the unemployment rate in the internal cities of the country and strengthens regional development.


## 8. Conclusion

The problem analyzed above is of important practical interest as it models real-life situations in the field of economics and finance, such as equal distribution between different regions, and attempts to minimize the differences between them in terms of levels of investment. The solution presented in this paper will therefore be useful from a practical point of view. From a theoretical perspective, the approached problem is a challenging one as it is difficult to solve; thus, its resolution will enhance the theoretical knowledge in this field. The analyses and resolution of this problem may therefore have an important impact on the economy and the industrial sector. In this paper, a comprehensive literature review on resource allocation and optimization studies was presented, and the theory of optimization was applied to a real-life case study to illustrate the importance of this practice. The theoretical and practical analyses are closely related. This study was applied to the industrial sector, and the results achieved by applying heuristics and an exact solution to the analyzed problem demonstrate the importance of optimization applied on the project distribution field. The results contribute to reducing the difference between various industrial regions and to achieving equity among them. More other branching methods can be developed to ameliorate the execution time of the exact solution. The proposed solutions in this paper can be applied to several fields.



---

*Source: 3607547-2020-08-01.xml*