Sage Journals: Discover world-class research

Abstract

In order to enhance the efficiency of offshore companies, a multi-objective scheduling system based on hybrid non-dominated sorting genetic algorithm was proposed. An optimized model for multi-objective and multi-execution mode was constructed under the condition of taking time, cost, and resource into account, and then the mathematical model for the same was established. Moreover, the key techniques of the proposed system were elaborated, and the flowchart was designed. Aiming at the weaknesses of non-dominated sorting genetic algorithm which is short for non-dominated sorting genetic algorithm-II in the facet of local search and computational efficiency, Pareto-dominated simulated annealing algorithm was applied in search global solution. Finally, by simulation examples and industrial application, the robustness and outperformance of the improved algorithm were verified.

Keywords

Hybrid non-dominated sorting genetic algorithm multi-objective scheduling system offshore project Pareto-dominated simulated annealing algorithm

Introduction

Since the depletion of land resources, along with the increasing development of marine resources, offshore project, as a typical large-scale engineering project, on how to shorten the construction period and reduce the cost has always been a subject to study.

Every event in large-scale engineering projects contains a certain amount of predecessors and successors which may occur under the impact of multi-execution mode, which is an alternative plan for those events. The selection principle depends on the target that the project emphasizes and reduces the time and activities of the critical paths without considering the supply ability of its constraints. In actual projects, the majority minimize time span merely by means of resources. However, in fact, resource supply ability and allocation situation exert direct impact on the project scheduling plan.¹ Given that the influential degree of factors such as time, cost, and resources varies under different execution modes,^2,3 the optimization of these factors under multi-objective and multi-execution modes (MOMEMs) is of certain research background and significance. The problem-solving process of project scheduling is for realizing an optimized allocation and achieving the most comprehensive benefits by making an accurate plan.⁴ Without a relatively good scheduling plan, companies have difficulties in surviving in the market.

As offshore equipment project is a large-scale engineering project, delay, resource shortage, and low construction rate often occur during the production process. Additionally, it involves different departments and has to coordinate with multiple disciplines in production; thus, the concerned decision-makers give different priorities to the project. But due to its special working environment which is restricted by many uncertain factors, such as sea state and climate, the offshore company usually completes the project on time according to the contract at the expense of cost and resource. Therefore, by optimizing the project scheduling of multiple objectives, targets, such as cost and resources, are set within the acceptable range under the premise of meeting with the deadline, which benefits the overall interest of offshore companies and fulfills the demand of actual production construction.

Furthermore, this article comprises the following parts: some related works are outlined based on the literature in section “Literature review.” The “Mathematical model for multi-objective and multi-execution mode offshore project scheduling” section describes the problem, illustrates and sets up a mathematical model, and preprocesses the fourth level network plan of offshore projects. Next “The proposed multi-objective scheduling system based on NSGA-II” introduces the hybrid non-dominated sorting genetic algorithm (NSGA-II) in detail. The “Simulation examples” section looks into the relevant statistics and result analysis of example verification. The “Conclusions and future work” section concludes the whole article and points out the research directions that need to be further investigated at later stages.

Literature review

Recent publications relevant to this article are mainly concerned with two research streams: multi-objective scheduling approaches and genetic algorithm optimization. In this section, we try to summarize the relevant literature.

Multi-objective scheduling approaches

In the past decades, much research has been carried out to solve the problem of multi-objective optimization in project scheduling. Swarm intelligence algorithm was widely applied in the field of multi-objective optimization. Ghoddousi et al.³ conducted research on three objectives of resource-constrained project scheduling, namely, time, cost, and resource deviation, by adopting the traditional NSGA-II, and arrived at a group of satisfactory Pareto optimal solutions. Senouci and Al-Derham⁴ optimized two objectives of linear construction projects, namely, time and cost, by adopting genetic algorithm. Furthermore, a conclusion was reached that the longer the time, the less the cost by example verification. Using the evolutionary algorithm, Tavana et al.⁵ researched into the relation among time, cost, and quality of project scheduling and verified the validity of those algorithms by comparing Pareto optimal solutions of different algorithms. Fuzzy programming algorithm was applied by Baky⁶ and Shahnazari-Shahrezaei and Tavakkoli-Moghaddam⁷ to look into the multi-objective optimization of multi-level distribution and human resource multi-objective and multi-skill scheduling. Safari⁸ and Cao et al.⁹ set up a new mathematical model and studied multi-objective redundancy allocation by applying an improved NSGA-II. Xiong et al.¹⁰ put forward a multi-objective evolutionary algorithm targeting the multi-objective problem of stochastic breakdown of machines in the flexible job shop.

Yannibelli and Amandi¹¹ researched multi-objective project scheduling with the shortest time and the most efficient human resource allocation. Besides, non-dominated optimal solutions were obtained, and feasibility and validity of algorithms were verified by integrating simulated annealing algorithm with the evolutionary algorithm. Li and Du¹² proposed hybrid genetic algorithm to solve the optimization problem of the limited multi-objective problem and compared the solution with NSGA-II, which effectively proved the algorithm’s feasibility. Eshtehardian et al.¹³ used genetic algorithm and fuzzy theory to research into time and cost with a consideration of uncertain resources.

Damak et al.¹⁴ compared the impact that different algorithms had on project scheduling optimization under multi-execution mode. Mori and Tseng¹⁵ studied scheduling problems limited by resources under the non-preemptive and multi-execution mode and performed example verification by genetic algorithm. Mika et al.^16,17 researched the multi-payment mode in project scheduling limited by resources by employing the simulated annealing method and tabu search algorithm, which was also used to study the project scheduling of multi-execution modes under the premise of setting up relevant time in advance. Buddhakulsomsiri and Kim^18,19 studied project scheduling of multi-execution modes limited by resources in accordance with the premise that resources could be terminated, activities could be stopped, and various emphatic aspects present. Elloumi and Fortemps²⁰ came up with an evolutionary algorithm based on ordering rule for the purpose of solving project scheduling of multi-execution modes limited by resources.

Genetic algorithm optimization

Genetic algorithm^21,22 describes problem solutions as chromosomes which form into a group of chromosomes and put into the problem environment. NSGA was proposed by Srinivas and Deb²³ in 1994. Similar to the standard genetic algorithm, NSGA realizes dual goals of multi-objective optimization algorithm using the scheme of assigning the non-dominated solutions’ fitness values and sharing the diversity of each individual from the non-inferior layer. In 1998, Zitzler²⁴ considered an external population P to introduce elitism. The external population, commonly known as the archive population, saves the final non-dominated solutions from the comparison of the new found non-dominated solutions and the external populations. This method is called strength Pareto evolutionary algorithm (SPEA), which not only saves the optimal solution but also makes a better development of population in the search space. Later, in 2001, Zitzler et al.²⁵ made the improvement based on SPEA, including the fitness assignment strategy, keep diversity method, and the non-dominated set adjustment. Based on NSGA, in 2002, Deb et al.²⁶ proposed NSGA-II.

According to the principle of survival of the fittest, chromosomes surviving in the environment are selected and copied, namely, regeneration, and then by genetic operators, for example, crossover and mutation, new chromosomes which are better adapted to the environment are generated. Actually, NSGA-II is of elitist strategy which suits for solving large-scale project optimization. However, due to its limited local search function, it is difficult to find out the globally optimal solution. Therefore, it needs to be improved. Pareto-dominated simulated annealing algorithm (PDMOSA), which simulates the temperature-fall process in physics and adopts Pareto-dominated rules, possesses very strong local search ability. Therefore, this article conducts global search using NSGA-II and integrating PDMOSA to realize complementary advantages, and proposes a hybrid NSGA-II. After example verification of some statistics in the fourth level network plan of actual offshore projects, it obtains the Pareto optimal solutions, providing certain references to the optimization of actual offshore companies’ project scheduling.

Discussion

It can be seen that the multi-objective optimization problem possesses a sound research foundation. Meanwhile, project scheduling of multi-execution mode limited by resources is widely researched by many scholars, which can be shown specifically as follows: First, the problem model is closely related to the actual situation, and the algorithms have a large adaptability, which are mostly swarm intelligence algorithms. Second, research aims of different research fields are basically the same, but there is a large application space for the problem model and algorithm strategy, which means that a single algorithm can be improved, multi-algorithms can be integrated, and different algorithms can be referred to.

Although much research about project scheduling of MOMEMs has been done, the following aspects need to be further considered. First, the fourth level network decomposition of offshore field, as one type of large-scale engineering projects, may guide the work to some extent, but its research foundation on this kind of large-scale engineering project is still weak. Second, it is possible that MOMEM may coexist in actual production and construction; therefore, both of these two situations should be considered, but the amount of research concerning this is rather small. Third, resources, which play indispensable and decisive roles in the construction and production of offshore equipment, have to be taken into account together with time and cost.

Mathematical model for multi-objective and multi-execution mode offshore project scheduling

Preprocessing of fourth level network plan for offshore project

Through the actual investigation of an offshore company, offshore companies adopt P6 (Primavera 6.0) as the theoretical guidance to decompose offshore projects into first, second, third, and fourth levels. However, due to the influence of related factors, for instance, the owners, in the construction process, the real work guidance is fourth level or fifth level plans. Some of these fourth level plans can be decomposed into fifth level plans, but the rest of them are indecomposable. Therefore, the fourth level plan after decomposition is a complete network plan including all the activities, successor and predecessor relations, and so on. In the optimization of multi-objective and multi-execution mode offshore project scheduling (MOMEMOPS), preprocessing is needed for dealing with the fourth level network plan.

As shown in Figure 1(a), S ₄ and E ₄, which are virtual activities, stand for the beginning activity and ending activity of the fourth level network plan, respectively. The corresponding time, direct cost, and resource consumption are 0. Suppose all the activities cannot be decomposed into fifth level plans except J ₄. S ₅ and E ₅, which are virtual activities, stand for the beginning activity and ending activity of the fifth level plans, respectively. The starting time of J ₄₁ and J ₄₃ is the starting time of S ₅. The ending time of J ₄₂ and J ₄₃ is the ending time of E ₅. Figure 1(b) shows the combination of them.

Figure 1.

Preprocessing of fourth level network plan for offshore project: (a) fourth level network plan decomposition and (b) combination of fourth level network plan.

In the fourth level plan of the offshore project, each activity is relatively independent. First, the logical relationships of the sub-activities which can be seen as the activities in the fifth level plan only exist in the inside of the fourth level plan activity itself. Second, reflect in the key resource consumption, which are used variously by different activities of the fourth level plan. In other words, sub-activities belong to the different activities that are not affected directly by each other, based on the coarse-grained fourth level plan. Therefore, first optimize for each activity in the fourth level plan through the fifth level plan which is composed of sub-activities and all the activities, and then with the result participate in the calculation as a whole.

Mathematical model

In line with the features of offshore companies’ fourth level network plan, a complete offshore project may be described as a directed network graph of nodes after fourth level network plan decomposition and fifth level plan combination. In this article, a network graph of nodes can be expressed as G = (V, E), where E is the directed arc group linking all the nodes in the set of node V. The number of activities is J, and j is one of the activities of J, namely, j = 1, ..., J. In this network graph, node 0 and node J + 1 exist, which represent the beginning and end of the virtual activities, respectively. Activity j can only begin after the completion of the predecessor group P_j .

Each activity j can complete in several different executive modes M_j = {1, ..., M_j }. In terms of carrying out j in execution mode m∈M_j , the demand quantity for renewable resources in each execution period is expressed as r_jmk ; meanwhile, the corresponding cost is c_jm , and time for j in execution mode m is d_jm . Suppose j begins under mode m, neither the interruption of activity nor the change of mode is permitted. It is a must to complete the time d_jm consecutively. At the same time, renewable resources exist throughout the project, and the maximized supply capacity of every kind of renewable resource k∈{1, ..., K} in each period is R_k .

Definition

$α_{c}$ is the adoption coefficient, to decide the probability of choosing the executive mode. Combined with the optimization algorithm, usually randomly generated execution mode of activities, in the actual production, executive models often differ in the choice, and we define the adoption coefficient $α_{c}$ with the executive mode $m$ preferences in accordance with experience

\sum_{1}^{n} α_{cm} = 1, m = 1, 2, \dots, n

In the initial adoption coefficient of choice, generally, $α_{cm}^{0} = 1 / n$ , or based on experience, reference to the history of outstanding mode q to artificially increase the adoption possibility, otherwise reduce

α_{cq} = \frac{1}{n} (1 + η), q \in {1, 2, \dots, n}

In each iteration of the optimization process, update the learning experience, and the original adoption coefficient correction is as follows

α_{cq}^{ξ + 1} = e^{\frac{ξ + 1}{N}} \cdot α_{cq}^{ξ} + (1 - e^{\frac{ξ + 1}{N}}) \cdot \frac{accep t_{num} {mod ep}}{ξ + 1}

where $accep t_{num} {mod ep}$ is the number of execution mode p accepted in the history of iterative calculation, and N is the maximum number of iterations.

The essence of project management lies in realizing the stated objective by efficient resource allocation and time scheduling.²⁷ This article aims to obtain the comprehensive optimal Pareto set of time, cost, and resources with the consideration of predecessors and successors of different activities by NSGA-II. Managers, according to the actual situations, compare the significance degrees³ of these three factors and choose the most beneficial plan for the companies.

In the preceding parts, three objective functions are established according to the derivations of time, cost, and resources with time and resource as the constraint conditions. Time is in line with the relation of predecessor and successor, while resource represents the constraint of resource supply capacity in unit. These three functions attempt to solve three problems: first, project cost minimization of the deadline, namely, the deadline problem; second, project time minimization of a given feasible budget plan, namely, time minimization problem; and, third, according to the constructed alternative solutions, select scheduling plans in accordance with actual construction situation and project managers’ preferences for their own objective functions, namely, problem of comprehensive scheduling plan for time, cost, and resources.

The mathematical model for MOMEMOPS can be expressed as follows

Min F_{t} = f_{J}

(1)

\begin{matrix} Min F_{c} = \sum_{j} \sum_{m \in M_{j}} (x_{jm} \times c_{jm}) + f_{J} \times c_{i} + y_{J} \times c_{p} \\ \times (f_{J} - T_{contract}) \end{matrix}

(2)

{MinM}_{x}^{dev} = \sum_{k = 1}^{K} {\sum_{t = 1}^{T} (r_{k} (t) - \frac{1}{T} \sum_{t = 1}^{T} r_{k} (t))}^{2}

(3)

\sum_{m \in M_{j}} x_{jm} = 1, j \in V

(4)

f_{j} - \sum_{m \in M_{j}} x_{jm} \cdot d_{jm} \geq f_{i}, \forall (i, j) \in E

(5)

\begin{matrix} \sum_{j \in A_{t}} \sum_{m \in M_{j}} (x_{jm} \cdot r_{jmk}) \leq R_{k}, k = 1, \dots, K, \\ A_{t} = 〈 j f_{j} - d_{j} < t \leq f_{j} 〉 \end{matrix}

(6)

x_{jm} = {\begin{matrix} 1 & if activity j is executed in mode m \\ 0 & else \end{matrix}

(7)

y_{J} = {\begin{matrix} 1 & f_{J} > T_{contract} \\ 0 & f_{J} \leq T_{contract} \end{matrix}

(8)

Objective functions (1–3) represent the smallest mutation of time, cost, and resources. The project ending time is the end time of J, namely, f_J . Costs include three parts, namely, indirect cost, direct cost, and penalty term. The third function is minimizing the resource deviation.²⁸ Function (4) means that j can only be carried out under one type of execution mode. Function (5) indicates that successor j can be implemented after the completion of predecessor i. Function (6) means that resource usage amount under a fixed execution mode within a certain period of time cannot exceed its largest supply capacity. Functions (7) and (8) are decision variables.

The proposed multi-objective scheduling system based on NSGA-II

Algorithm strategy

Due to the large work load of offshore projects, the length of chromosome increases, resulting in a huge solution space of the whole problem. Besides, because elitism strategy has to compare every individual in the Pareto solution set, the calculation efficiency becomes rather low. Although the rate of crossover and variation can protect the diversity of population to a certain degree, the change of a genetic locus will greatly destroy the formed optimal Pareto solution set owing to the fact that chromosome is made up of activity sequence and execution mode sequence. Hence, it is difficult for the traditional NSGA-II to obtain a globally optimal solution. PDMOSA, by virtue of the annealing process in solid matter which decreases with the temperature and Pareto acceptance principle, conducts search. With certain acceptance of inferior solutions, it is of certain kick and strong local search ability.

NSGA-II possesses strong global search ability; however, its local search capacity is relatively weak. Therefore, obtaining a globally optimal solution is rather difficult with NSGA-II. After integrating PDMOSA and conducing crossover and derivation, global search is done on those individuals produced, which may enhance the convergence ability of the algorithm to a large degree and quickly acquire the globally optimal solution.

Algorithm strategy mainly includes population initialization, decoding, non-dominated sorting, tournament selection, genetic operation, and PDMOSA operation. First, initialize the population as the parent one and then decode chromosomes and calculate the value of objective functions. After non-dominated sorting and tournament selection, the parent population will do the crossover operation and mutation operation with certain probabilities, from which the offspring population can be obtained. However, integration of PDMOSA is needed to conduct local search for the purpose of enhancing the population stability. As a result, the offspring population will be confirmed and will combine with the parent for further non-dominated sorting and then will be selected as the new parent population. Finally, an optimal Pareto solution will be produced after the process of iteration when the termination condition is satisfied. The specific procedures are shown in Figure 2.

Figure 2.

The flowchart of the proposed approach.

Generative rule of initial population

In view of the research problem of this article, chromosome in NSGA-II has to represent two kinds of information, namely, activity sequence information and execution mode sequence information. Figure 3 is a network figure showing simple successor and predecessor relations. Figure 4 is an example coding this network figure. Suppose only two kinds of execution modes exist: one is the common execution mode marked as M ₁, and the other is an execution mode with an increase in resources to shorten the time, which is marked as M ₂. There are only two types of execution modes in this article; hence, the probability is chosen from M ₁ and M ₂ at random.

Figure 3.

Network sample graph.

Figure 4.

Coding sample graph.

Decoding rule

In hybrid NSGA-II, information concerning the activity sequence and execution mode of chromosomes is expressed in the form of solution. Serialized scheduling is adopted in this article. Because the constraint conditions concerned are time and resource, the sequence of a two-dimensional template drawing is applied to conduct decoding. A concrete decoding process is shown in Table 1.

Table 1.

Introduction for decoding rule.

Introduction for decoding steps:

The algorithm consists of h = 1, ..., J stages; in each stage, only one activity j* is selected and scheduled at the earliest feasible start time with respect to its execution mode, precedence relationship, and resource availability. The algorithm terminates at stage number J, when all the activities are in the scheduled set PS_h . Let

~ R_{k} (t) = R_{k} - \sum_{j \in A_{t}} r_{jmk}

be the remaining capacity of resource type k at time instant t and let

F_{h} = 〈 f_{j} j \in P S_{h} 〉

be the set of all finish times. The start time of activity j* is calculated by first determining the earliest precedence feasible start time ES_j *. Activity list is represented by

ρ = {j_{1}, \dots, j_{h}, \dots, j_{J}}

Step 1: Initialization h = 1, PS_h = {0}, F_h = {0};

Step 2: If

| P S_{h} | < J

, then turn to step 3, or else end;

Step 3: Calculated by the following formula

F_{h'} ~ R_{k} (t)

j^{*} : = j_{h}, d_{j^{*}} : = d_{j^{*} m}

E S_{j^{*}} = max_{i ∋ P_{j^{*}}} {F_{h}}

S_{j^{*}} = min {t | E S_{j^{*}} \leq t, r_{j^{*} mk} \leq ~ R_{k} (τ), τ = t, \dots, t + d_{j^{*}} - 1, k = 1, \dots, K}

f_{j^{*}} = S_{j^{*}} + d_{j^{*}}

F_{h + 1} : = F_{h} \cup {f_{j^{*}}}; P S_{h} : = P S_{h} \cup {j^{*}}

h : = h + 1

, turn to step 2.

Rapid non-dominated sorting and crowding distance calculation

When all the objective function values of populations are calculated via individual decoding, rapid non-dominated sorting^3,9 is employed to layer the current populations and give them corresponding serial numbers. The serial numbers of some individuals are the same. In terms of selection, crowding distance calculation^3,9 is needed for the consideration of population diversity.

Tournament selection

This is done by choosing two individuals randomly and comparing their corresponding serial numbers. If their serial numbers are different, then choose the individual with the smaller serial number; if the serial numbers are the same, then compare their corresponding crowding distances and choose the individual with bigger crowding distance.

Crossover and mutation operation

Crossover operation

The crossover operation is the most important operation step in genetic algorithm. Therefore, a correct design is needed. Due to the existence of two coding chromosomes of MOMEM, the single-point crossover method proposed by Ghoddousi³ and Hartmann² is applied, which can be seen in Figure 5: q ₁ and q ₂ are chosen randomly according to the activity sequence and execution mode correspondingly. After the selection of q ₁, the activity sequence before q ₁ is interlaced with the offspring individuals and is excluded from the parental activity sequence. The rest of the activity sequence is orderly interlaced with offspring individuals, and then the interlace operation of activity sequence is completed.

Figure 5.

Crossover operation.

Mutation operation

The mutation operation will be implemented in activity sequence and execution mode sequence. However, the execution rules are different. In activity sequence, an activity should be selected first at random, for instance, activity 2 in Figure 6; find out the immediate predecessor at the top of activity 2, namely, activity 0, and successor 4 at the bottom; a number will be produced from activity 0 to activity 4 (0 and 4 are excluded) to represent the location of the activity, for instance, 2; and then move activity 2 to location 2 with the other activities moving forward or backward without changing the sequence. As for the mutation of execution mode, choose a number from 1 to 6 at random, such as location 5 in Figure 6, and then change the execution mode at the corresponding location to the other alternative execution mode.

Figure 6.

Mutation operation.

PDMOSA operation

Good individuals of the offspring population produced by crossover and mutation might be destroyed. The integration of PDMOSA is for conducting local search and revision so as to increase population stability. In the following, some concepts and formulas of PDMOSA will be introduced, and specific procedures are shown in Figure 7:

Fitness degree: add the number of solutions governing individual Y in optimal Pareto solution set with 1, and individual Y is a domain solution produced by stochastic disturbance;

Stochastic disturbance rule: adopt mutation operation in NSGA-II and take probability 1 to conduct mutation and obtain a domain solution;

Probability P: $P = \exp (- Δ S' / T)$ , where $Δ S' = S'_{i - 1, current} - S'_{i, current}$ ; $S'_{i - 1, current}$ stands for the fact that the current solution in i − 1 iteration is based on the fitness value governed by Pareto. $S'_{i - 1, generated}$ represents the fact that the current solution in i iteration is based on the fitness value governed by Pareto;

Cooling strategy: the higher the temperature, the bigger the acceptance probability of domain solution. Probability of acceptance decreases with the falling of the temperature, and the population becomes stable, namely, T = q × T.

Figure 7.

Simulated annealing algorithm based on Pareto-dominated rule.

Simulation examples

In this section, two simulation examples are put forward to validate the proposed algorithm based on the multi-objective scheduling system. The first simulation example is used to verify the feasibility and efficiency of the proposed algorithm, and the second simulation example is provided to prove the outperformance of the proposed algorithm. In our experiments, the configurations of simulation environment are shown in Table 2.

Table 2.

Configurations of simulation environment.

Index	Parameter name	Parameter content
1	Simulation platform	PC
2	Operation system	Windows 7
3	CPU	2.4 GHz
4	Memory	4 G
5	Development environment	VC++ 6.0
6	Simulation engine	MATLAB 2012b
7	Data storage format	Txt

Simulation example 1

In order to verify the feasibility of the proposed algorithm, the actual project statistics of an offshore company are taken as the example. Because of the huge amount of offshore project statistics, this article takes the fourth level plan corresponding to cantilever block construction as a verification object. Activities 6₀–6₁₅ belong to the fifth level plan and represent the sub-activities of the sixth activity in the fourth level plan. Meanwhile, it considers the other related third factors and assumes that the activity cannot be interrupted once it begins. Figure 8 illustrates the network graph, and corresponding statistics are included in Table 3.

Figure 8.

Network graph of offshore project.

Table 3.

Project statistics of cantilever block construction.

Index	Name	Predecessor	Executionmode	Time (days)	Resource demand(persons)	Direct cost (US$)
0	Virtual beginning activity	–	–	0	0	0
1₀	Virtual beginning of activity 1	0	–	0	0	0
1₁	Composite beams prefabrication	1₀	1	2	9	2600
			2	5	5	1900
1₂	Deck panel 6 prefabrication	1₀	1	3	5	1700
			2	4	3	1100
1₃	Sliding shoes lifting	1₁, 1₂	1	3	7	1300
			2	5	3	900
1₄	Deck panel 6 installation	1₂	1	2	6	1900
			2	4	4	1600
1₅	Reinforcement rolling	1₄	1	2	8	2200
			2	5	2	1700
1₆	Virtual ending of activity 1	1₅	–	0	0	0
2₀	Virtual beginning of activity 2	1	–	0	0	0
2₁	Bulwark prefabrication	2₀	1	3	3	2200
			2	5	1	1600
2₂	Gangway flat iron prefabrication	2₁	1	4	4	1700
			2	6	2	1400
2₃	Rail flat iron prefabrication	2₂	1	5	9	2800
			2	7	7	2200
2₄	Water-retaining flat iron	2₃	1	2	6	3800
			2	3	4	3100
2₅	Virtual ending of activity 2	2₄	–	0	0	0
3₀	Virtual beginning of activity 3	2	–	0	0	0
3₁	Gangway flat iron installation	3₀	1	3	7	3300
			2	4	3	2500
3₂	Rail flat iron installation	3₁	1	8	11	3200
			2	9	6	2300
3₃	Water-retaining flat iron	3₂	1	6	6	1600
			2	7	3	1200
3₄	Plant bottom case	3₂	1	3	6	1300
			2	4	4	1000
3₅	Virtual ending of activity 3	3₃, 3₄	–	0	0	0
4₀	Virtual beginning of activity 4	3	–	0	0	0
4₁	Equipment pre-installation	4₀	1	6	9	3300
			2	9	6	1900
4₂	Equipment installation	4₁	1	2	7	1300
			2	5	2	1100
4₃	Piping accessories prefabrication	4₀	1	2	7	1600
			2	3	4	1100
4₄	Bulwark pretreatment	4₂	1	3	8	1400
			2	7	5	1000
4₅	Gangway spraying	4₃, 4₄	1	2	6	1200
			2	6	2	1100
4₆	Virtual ending of activity 4	4₅	–	0	0	0
5₀	Virtual beginning of activity 5	4	–	0	0	0
5₁	Pipeline system prefabrication	5₀	1	5	3	2000
			2	6	2	1600
5₂	Indoor outfitting	5₁	1	3	6	1900
			2	4	3	1500
5₃	Pipeline system installation	5₁	1	2	8	1700
			2	6	5	1500
5₄	Cable bracket parts	5₃	1	3	7	2200
			2	7	3	2100
5₅	Telecommunication spare	5₂, 5₄	1	4	8	3300
			2	7	6	2200
5₆	Cable bracket installation	5₅	1	4	9	2800
			2	7	3	1900
5₇	Cable bracket laying	5₆	1	7	9	3100
			2	9	6	2100
5₈	Virtual ending of activity 5	5₇	–	0	0	0
6₀	Virtual beginning of activity 6	5	–	0	0	0
6₁	Steel material	6₁	1	3	10	3000
			2	6	3	1800
6₂	Steep cutting	6₂	1	2	6	1200
			2	5	2	1000
6₃	Matching	6₃	1	2	6	1200
			2	4	2	800
6₄	Segmented monolithic cantilever 1	6₄	1	3	8	2400
			2	5	4	2000
6₅	Segmented monolithic cantilever 2	6₄	1	3	9	2700
			2	6	4	2400
6₆	Segmented monolithic cantilever 3	6₄	1	4	6	2400
			2	5	4	2000
6₇	Segmented monolithic cantilever 4	6₄	1	3	7	2100
			2	5	3	1500
6₈	Cantilever assembly segment 1	6₅, 6₆	1	2	9	1800
			2	3	5	1500
6₉	Cantilever assembly segment 2	6₇, 6₈	1	3	8	3000
			2	5	7	2400
6₁₀	Staging large cantilever assembly	6₉, 6₁₀	1	5	9	4500
			2	8	4	3200
6₁₁	Cantilever block painting	6₁₁	1	5	8	4000
			2	6	5	3000
6₁₂	Cantilever segments close	6₁₁	1	8	12	9600
			2	9	10	9000
6₁₃	Cantilever segments outfitting	6₁₁	1	3	6	1800
			2	5	2	1000
6₁₄	Cantilever segments inspection	6₁₂, 6₁₃, 6₁₄	1	2	6	1200
			2	3	3	900
6₁₅	Virtual ending of activity 6	6₁₅	–	0	0	0
7₀	Virtual beginning of activity 7	6	–	0	0	0
7₁	Stand-alone debugging	7₀	1	3	8	2000
			2	7	5	1600
7₂	Module support framework (MSF) weighing	7₁	1	2	9	2200
			2	6	4	1900
7₃	Chunk structural capping	7₂	1	2	7	1300
			2	3	3	1000
7₄	Virtual ending of activity 7	7₃	–	0	0	0
8	Virtual ending activity	7	–	0	0	0

According to the decomposing model strategy of the fourth level network plan in the section “Preprocessing of fourth level network plan for offshore project,” first optimize for each activity in the fourth level plan. Taking the sixth activity as an example, the sub-activities 6₀–6₁₅ will be scheduled. In order to find an optimal Pareto solution set of the best combination of time, cost, and resources the parameters of hybrid NSGA-II are listed as follows: the largest repetition number is 100, initial population size is 30, crossover probability Pc is 0.9, mutation probability PM is 0.1, initial temperature is 60°C, annealing coefficient q is 0.7, and repetition for twice, namely, a1 is 20 and b1 is 6.

As shown in Figure 8, the sixth activity contains 16 sub-activities. Activity 6₀ and activity 6₁₅ stand for the virtual beginning activity and virtual ending activity, respectively. Every activity has an optional execution mode having different statistics. Assume that only one kind of renewable resource is optional, and its daily supply capacity is 14. Indirect cost is not taken into account in this article. Time lasts for 60 days at the most. If the total time exceeds 60 days, US$5000 per day is the penalty. Table 3 displays the detailed information.

After running the algorithm 100 times, an optimal Pareto solution set of 30 solutions is produced. Derivations of time, cost, and resources are as follows: 39–56 days, US$35,300–US$41,000, and 232.635–942.542. Table 4 indicates that the shorter the time, the higher the cost. It matches with the actual production and construction situation, namely, increasing cost for speeding up the project. However, the higher the cost, the smaller the resource derivation. Seen from another perspective, the bigger the resource derivation, the more unstable the use of resource. It leads to the project delay. Completing the project before the deadline without receiving any penalty is the only way to lower the cost.

Table 4.

Optimal Pareto solution set.

Index	Time (days)	Cost (US$)	Resource derivation	Index	Time (days)	Cost (US$)	Resource derivation
1	46	35,300	726.208	16	40	38,600	473.25
2	40	37,200	232.635	17	49	35,800	572.539
3	41	36,200	260.334	18	52	36,400	448.063
4	44	35,800	457.216	19	42	36,400	603.539
5	56	35,700	613.125	20	51	35,900	521.984
6	51	35,400	641.365	21	40	38,500	559.265
7	39	38,200	438.98	22	43	36,900	441.687
8	47	35,000	908.128	23	44	37,000	574.727
9	39	39,200	380.903	24	44	37,200	534.548
10	46	36,700	585.935	25	48	35,600	763.917
11	44	36,800	330.793	26	46	38,700	404.663
12	47	35,500	745.391	27	43	37,500	468.488
13	41	37,300	328.443	28	49	41,000	402.84
14	49	35,300	880.865	29	43	36,800	607.986
15	44	35,900	716.407	30	48	35,500	942.542

When the time period is 46 days, derivations of one cost and resource are US$35,300 and 726.20, respectively, and derivations of another cost and resource are US$36,700 and 585.935, respectively. It conveys that a non-inferior solution appears with cost and resource derivations within a fixed time, and it may induce the deterioration of another solution. Similarly, when the cost is US$36,400, derivations of one period and resource are 52 days and 448.063, respectively, and derivations of another period and resource are 42 days and 603.539, respectively. All in all, the multi-objective problem is the optimal Pareto solution set for obtaining an acceptable objective solution without deteriorating the other solutions. But decision-makers have to take all the factors into consideration in terms of selecting a good scheduling plan.

The optimal Pareto solution sets of the activities in the fourth level plan can be obtained by the same method. Each solution in the set can be seen as an execution mode of the activity in a new round of computing, which can be screened earlier to reduce the amount of computation. Table 5 shows the final solutions about the fourth level plan.

Table 5.

Fourth level plan optimal Pareto solution set.

Index	Time (days)	Cost (US$)	Resource derivation	Index	Time (days)	Cost (US$)	Resource derivation
1	135	89,600	423.192	6	127	91,300	557.265
2	137	86,500	565.775	7	141	84,100	651.239
3	142	83,300	789.130	8	130	89,900	442.044
4	129	90,300	337.161	9	126	90,900	398.631
5	121	94,100	592.173	10	144	81,200	543.016

Simulation example 2

For the purpose of clearly demonstrating the advantages of hybrid NSGA-II, this article lists optimal Pareto solution sets and two-dimensional scatter diagrams (Figures 9 –11) obtained by hybrid NSGA-II, NSGA-II, and PDMOSA. Conclusions are drawn by comparing these diagrams.

Figure 9.

Hybrid NSGA-II algorithm results.

Figure 10.

NSGA-II algorithm results.

Figure 11.

PDMOSA results.

In this simulation example, hybrid NSGA-II, NSGA-II, and PDMOSA were provided to solve the problem of simulation example 1. The configurations of simulation environment for the three algorithms were uniform. In NSGA-II, the number of chromosomes in the population is 30, the crossover probability is 0.9, and the mutation probability is 0.1. In simulated annealing algorithm, the initial temperature is 60°C, annealing coefficient q is 0.7, and repetition for twice, namely, a1 is 20 and b1 is 6. The parameters of hybrid NSGA-II were in common with simulation example 1.

The fixed crossover, mutation probability, and enormous problem scale of NSGA-II result in easy destruction of optimal Pareto solution in the search process. It is difficult to obtain the globally optimal solution. As it possesses elitist strategy, the diversity of solutions is effectively protected, which may be proved by the wide distribution of solutions in Figure 10. But, there is no certain trend.

PDMOSA is of strong local search ability and accepts inferior solutions to a certain probability. At the same time, the acceptance rule adopts fitness function value rather than objective function, which makes the calculation easy and close to the non-inferior solution. Similarly, in Figure 11, the distribution scale of solution is not very wide, and there is a certain phenomenon of cluster, which means that the population diversity is not well displayed.

Combining the advantages and disadvantages of NSGA-II and PDMOSA and applying PDMOSA to conduct a local search of offspring population after the crossover mutation of NSGA-II so as to avoid the occurrence of population destruction resulted from crossover mutation. As shown in Figure 9, it is better than the other two algorithms either in terms of population distribution or the smoothness of Pareto optimal surface. Therefore, the improvement measures are applicable.

The average deviation, maximum deviation, percent of best solution, and computing time of the three algorithms (hybrid NSGA-II, NSGA-II, and PDMOSA) are shown in Table 6.

Table 6.

Comparison of hybrid NSGA-II, NSGA-II, and PDMOSA.

Algorithms	Average deviation (%)	Maximum deviation (%)	Percent of best solution	Computing time (s)
Hybrid NSGA-II	1.09	22.1	96.6	41.33
NSGA-II	2.85	29.2	78.4	39.63
PDMOSA	4.81	40.8	73.4	40.38

NSGA: non-dominated sorting genetic algorithm; PDMOSA: Pareto-dominated simulated annealing algorithm.

Application of the proposed approach

The proposed algorithm has been applied and validated in our self-developed schedule optimization software for offshore companies shown in Figure 12. In our self-developed scheduling optimization software called SOSOP, an optimal activity sequence is generated through the proposed algorithm, and it can be used to efficiently assist the schedule control manager to develop progress reports. The project schedule is listed on the left of the interface, and the project Gantt chart can be generated automatically and intelligently with high efficiency and low cost. Similar to the simulation example 1, the optimization results will be shown as the graphical visualization after the raw data input of the activities.

Figure 12.

Application of the proposed algorithm: (a) planning list, (b) project Gantt, (c) completion state, (d) progress curve, and (e) workload statistics.

Conclusion and future work

Time, cost, and resources are the three important aspects of engineering projects. It is very difficult for the decision-makers to make out a plan with optimal application of these three factors. Using hybrid NSGA-II, this article searches out an optimal Pareto solution set for the decision-makers to make the most beneficial decisions according to their own preferences:

The establishment of a mathematical model is fully considered in the offshore project, which improved from the existing ones. Then through the combination of an improved model and the hybrid algorithm, this article builds a relationship among the three objectives and obtains the optimal solution. However, the software developed in the final result has a certain applied value in the offshore industry.

This article conducts optimization of three objectives, namely, time, cost, and resources, as well as different execution modes, and achieves a satisfactory optimal Pareto solution set; hence, when an objective becomes optimal, its solution will not become inferior.

This article adopts hybrid NSGA-II and integrates simulated annealing algorithm to make up for the weaknesses of NSGA-II, namely, weak local search ability and difficult convergence. By comparing the results, the advantages of hybrid NSGA-II, which absorbs the advantages of NSGA-II and PDMOSA, are clearly demonstrated, and its disadvantages are avoided. The optimal Pareto solution set obtained from the search is widely distributed and acceptable.

According to the research statistics, the pursuit of optimization of a certain objective among multiple objectives might possibly worsen the rest of the objectives rather than obtaining the optimal solution of these three objectives. Decision-makers have to choose from the solution set obtained from the search. However, the project scheduling problem of MOMEM, a very complicated problem, does exist in real life. Owing to the complexity of the offshore project’s fourth level network, this article still has its research limitations, and the following questions need to be investigated further in the future:

As the network graph of offshore project is rather complicated, a fourth level network plan is usually applied and decomposed to guide the actual project. Project scheduling of MOMEM under this network graph should be further explored.

Because simulated annealing algorithm is integrated in hybrid NSGA-II, a lot of parameters of these two kinds of algorithms have to be set up. A correct parameter setting directly influences the function of the algorithms. The impact that various parameters have on the results brought about by algorithms has to be discussed later.

In fact, multiple resources and multiple projects coexist in offshore project construction; hence, project scheduling of MOMEM under the situation of multiple projects needs to be researched deeper.

Footnotes

Academic Editor: Duc T Pham

Declaration of conflicting interests

The authors declare that there is no conflict of interests regarding the publication of this article.

Funding

This research was supported by the National Natural Science Foundation of China (no. 51209045) and the High Technology for Ship Scientific Research Program of the Ministry of Industry and Information Technology of the People’s Republic of China.

References

Chen

Weng

. A two-phase GA model for resource-constrained project scheduling. Automat Constr 2008; 18: 285–298.

Hartmann

. Project scheduling with multiple modes: a genetic algorithm. Ann Oper Res 2001; 102: 111–135.

Ghoddousi

Eshtehardian

Jooybanpour

. Multi-mode resource-constrained discrete time-cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm. Automat Constr 2013; 30: 216–227.

Senouci

Al-Derham

. Genetic algorithm-based multi-objective model for scheduling of linear construction projects. Adv Eng Softw 2008; 39: 1023–1028.

Tavana

Abtahi

A-R

Khalili-Damghhani

. A new multi-objective multi-mode model for solving preemptive time-cost-quality trade-off project scheduling problems. Expert Syst Appl 2014; 41: 1830–1846.

Baky

. Fuzzy goal programming algorithm for solving decentralized bi-level multi-objective programming problems. Fuzzy Set Syst 2009; 160: 2701–2713.

Shahnazari-Shahrezaei

Tavakkoli-Moghaddam

. Solving a multi-objective multi-skilled manpower scheduling model by a fuzzy goal programming approach. Appl Math Model 2013; 37: 5424–5443.

Safari

. Multi-objective reliability optimization of series-parallel systems with a choice of redundancy strategies. Reliab Eng Syst Safe 2012; 108: 10–20.

Cao

Murat

Chinnam

. Efficient exact optimization of multi-objective redundancy allocation problems in series-parallel systems. Reliab Eng Syst Safe 2013; 111: 154–163.

10.

Xiong

Xing

Chen

. Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. Int J Prod Econ 2013; 141: 112–126.

11.

Yannibelli

Amandi

. Hybridizing a multi-objective simulated annealing algorithm with a multi-objective evolutionary algorithm to solve a multi-objective project scheduling problem. Expert Syst Appl 2013; 40: 2421–2434.

12.

. BSTBGA: a hybrid genetic algorithm for constrained multi-objective optimization problems. Comput Oper Res 2013; 40: 282–302.

13.

Eshtehardian

Afshar

Abbasnia

. Time-cost optimization: using GA and fuzzy sets theory for uncertainties in cost. Constr Manage Econ 2008; 26(7): 679–691.

14.

Damak

Jarboui

Siarry

. Different evolution for solving multi-mode resource-constrained project scheduling problems. Comput Oper Res 2009; 36: 2653–2659.

15.

Mori

Tseng

. A genetic algorithm for multi-mode resource constrained project scheduling problem. Eur J Oper Res 1997; 100: 134–141.

16.

Mika

Waligora

Weglarz

. Tabu search for multi-mode resource-constrained project scheduling with scheduled-dependent setup times. Eur J Oper Res 2008; 187: 1238–1250.

17.

Mika

Waligora

Weglarz

. Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. Eur J Oper Res 2005; 164: 639–668.

18.

Buddhakulsomsiri

Kim

. Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur J Oper Res 2006; 175: 279–295.

19.

Buddhakulsomsiri

Kim

. Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur J Oper Res 2007; 178: 374–390.

20.

Elloumi

Fortemps

. A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem. Eur J Oper Res 2010; 205: 31–41.

21.

Zitzler

Thiele

. Multi-objective evolutionary algorithm: a comparative case study and the strength Pareto approach. IEEE Trans Evolut Comput 1999; 3(4): 257–271.

22.

Villasanti

von Luken

Baran

. Dispatch of hydroelectric generating units using multi-objective evolutionary algorithm. In: IEEE/PES transmission and distribution conference and exposition: Latin America, Sao Paulo, Brazil, 8–11 November 2004, pp. 929–934. New York: IEEE.

23.

Srinivas

Deb

. Multi-objective function optimization using nondominated sorting genetic algorithms. Evol Comput 1995; 2(3): 221–248.

24.

Zitzler

. Evolutionary algorithms for multiobjective optimization: methods and applications. Doctoral Thesis, ETH no. 13398, Swiss Federal Institute of Technology, Zurich, Switzerland, 1999.

25.

Zitzler

Laumanns

Thiele

. SPEA2: improving the strength Pareto evolutionary algorithm. Eidgenössische Technische Hochschule Zürich (ETH), Institut für Technische Informatik und Kommunikationsnetze (TIK). 2001

26.

Deb

Pratap

Agrawal

. A fast and elitist multi objective genetic algorithm: NSGA-II. IEEE Trans Evolut Comput 2002; 6(2): 182–197.

27.

Badiru

. Project management tools for engineering and management professionals. Norcross, GA: Industrial Engineering and Management Press, 1997, pp.3–5.

28.

Leu

Yang

Huang

. Resource leveling in construction by genetic algorithm-based optimization and its decision support system application. Automat Constr 2000; 10(1): 27–41.

Development of a multi-objective scheduling system for offshore projects based on hybrid non-dominated sorting genetic algorithm

Abstract

Keywords

Introduction

Literature review

Multi-objective scheduling approaches

Genetic algorithm optimization

Discussion

Mathematical model for multi-objective and multi-execution mode offshore project scheduling

Preprocessing of fourth level network plan for offshore project

Mathematical model

Definition

The proposed multi-objective scheduling system based on NSGA-II

Algorithm strategy

Generative rule of initial population

Decoding rule

Rapid non-dominated sorting and crowding distance calculation

Tournament selection

Crossover and mutation operation

Crossover operation

Mutation operation

PDMOSA operation

Simulation examples

Simulation example 1

Simulation example 2

Application of the proposed approach

Conclusion and future work

Footnotes

Declaration of conflicting interests

Funding

References