Sage Journals: Discover world-class research

Abstract

In this article, we attempt to solve the issue of optimal scheduling for vessels monitoring video data uploading in maritime cyber physical systems, during the period of sailing from the origin port to destination port. We consider the terrestrial infrastructure-based networking, delivering video packets assisted by the shoreside infostations to the authorities on land. Each video packet has respective elements (i.e. release time, deadline, processing time, and weight) to describe, in which deadline is utilized to demonstrate the time domain limitation before that to upload it successfully. In order to cope with the computation complexity of traditional scheduling algorithms in intermittent infostations scenario, time-capacity mapping method is exploited to transfer it to a continue scenario when classic scheduling algorithms could be utilized with lower time complexity. An ingenious mathematic job-machine scheduling formulation is indicated with the goal of minimizing the total penalties of tardiness of uploaded video packets, taking into account the tardiness and the weights of jobs simultaneously. A genetic based algorithm, as well as an improved genetic algorithm–based optimization scheme, is proposed to target this optimization formulation. Specially, the genetic based algorithm as well as the improved genetic based algorithm are described in detail, including a novel chromosome representation, a heuristic initialization procedure, as well as a modified crossover and mutation process. The effectiveness of the proposed schemes is verified by the simulation results.

Keywords

Job-machine scheduling genetic algorithm maritime cyber physical systems

Introduction

Cyber physical systems (CPSs) as a unified process of computing and physical processes, integrated computing, communication, and control in one of the next generation of intelligent systems. The CPSs interacts with the physical process through the human–computer interaction interface and uses the networked space to manipulate a physical entity in a remote, reliable, real-time, secure, and cooperative way. It focuses on the close integration and coordination of computing resources and physical resources, which involves a wide range of applications, including intelligent transportation systems, telemedicine, aerospace, and other fields.¹ If the popularity of the Internet to the human society has brought earth-shaking changes, then the popularity of CPSs will bring an industrial revolution to mankind. At present, CPSs research has just started, the researchers are faced with both opportunities and challenges. In our study, maritime CPSs target the tight incorporation of wireless communications, control, and computing technologies into the navigation transportation system, which posses the typical characteristics of CPSs revolutionizing the navigation pattern to be safer and more efficient through real-time embedded systems for distributed sensing, computation, and control between cyber and physical systems.²

Obviously, the maritime broadband communication networking could satisfy the tremendous requirements of wireless service at sea.³ Via this network, a bunch of specific services with large data volume could be provided, such as the monitoring videos uploading to the land-based authorities with lower expenditure compared to the existing satellite communications.

The state-of-the-art work on maritime wideband network structures can be summarized as follows. Zhou and Harada⁴ introduced cognitive radio into maritime mesh/ad hoc networks. As we know, the maritime intelligent transportation system has a growing interest in offshore CPSs and has achieved a low cost alternative to the current maritime satellite data transmission. Previously, it used advanced wireless technology to build sea broadband network. For example, Global Interoperability for Microwave Access (WiMAX) technology is used for wireless broadband access to the Singapore Harbor (WISEPORT) project.⁵ The alternative scheme utilized store-carry-and-forward data packet delivery in delay-tolerant networks (DTNs)⁶ and is proposed to meet the intermittent end-to-end path, which is formed by the characteristics of channel on the sea. Our previous work as well as the work by Lin et al.⁷ is based on the developed WiMAX-based mesh technology with DTN characteristics. In this article, the CPSs, an emerging research area which incorporates communication, computing, and control technology, are introduced in maritime scenario to collect data such as monitoring of vessel, compute, and deliver it to the maritime authority on land. By analyzing the big data of surveillance videos, ship owners or the other relative personnel on land could intelligently control the vessel navigation, cargo loading and discharging, and so on. Therefore, maritime CPSs could potentially provide much smarter, efficient, and robust communication and control for maritime society. In our scenario, data delivery can be achieved via infostations shoreside, and long term evolution/store-carry-and-forward interworking maritime CPSs are proposed to achieve marine intelligent transportation systems.^8–10

In this article, we only focus on the video data delivery scheduling issue. Videos are partitioned into packets, with respective release time, deadline, and weight. The data packets delivered after the deadline is not tolerant enough. We define the tardiness of delivered data with penalty, considering tardiness duration and weights of jobs. The goal of this article is to minimize the total penalties of tardiness of delivered data. In the literature, although not in maritime scenarios, the land-based vehicle-assisted data delivery has been broadly investigated,¹¹ and the related literatures on land-based network contribute a solid foundation for our work.^12–16 In this article, time-capacity mapping is applied to convert the initial intermittent connectivity due to intermittent infostations deployment, to a single machine scheduling issue. The goal of our research ensures the quality of the delivered packets via the encounter infostations. And the issue is formulated as a vessel minimizing the total penalties of tardiness of delivered data problem. To solve this problem, a mathematic job-machine scheduling (JMS) method is applied to schedule resources (i.e. frames of infostations) to different packets. Vessels and packets play the role of machines and jobs, respectively.^17–19 An offline scheduling algorithm is proposed depending on a genetic optimization process comprised with a novel chromosome representation, a heuristic initialization procedure as well as a modified crossover and mutation process.

The remainder of this article is organized as follows. System model is given in section “System model” and problem formulation is presented in section “Problem formulation.” An offline scheduling algorithm is proposed depending on a genetic optimization process in section “Solution.” In section “Simulation results,” simulation results are shown to demonstrate the performance of our approach. We conclude this article in section “Conclusion.” As many symbols are used in this article, some important notation definitions are tabulated in Table 1.

Table 1.

Notations and definitions.

Symbol	Definition
$i, j$	The order or index
$M_{k}$	The number of vessel (machine)
$J_{i}$	The number of job (operation)
$r_{j} (d_{j}) (p_{j}) (b_{j}) (e_{j})$	The release time (deadline) (processing time) (beginning time) (ending time) of video packet j proceeded on vessel k
$A_{i}$	The arrival time of order
$D_{i}$	The due date of order (pre-given)
$C P_{i}$	The completion time of order
$T D_{i}$	The tardiness of order, TD_i = max (0, $C P_{i} - D_{i}$ )
$α_{i}$	The weight of tardiness penalty for order (pre-given)
$λ_{i}$	The states if tardiness $T D_{i}$ of order is greater than 0, $λ_{i} = 1$ , else $λ_{i} = 0$
$γ_{i}$	The weight of machine $M_{k}$ processing operation, between 0 and 1
u	Represent a population size
PPN and QTY	Represent the population and a maximum quantity
$CH R_{i}$	An integer string chromosome
PTY	The probability that a machine to process relevant packets
Z	The objective function

System model

We present the details of the system model in this section. In this study, first, we develop a resource allocation and scheduling issue by considering the spread of intermittent network connections because of the intermittent infostations shoreside. The aim of this work is to guarantee the quality of videos as far as possible. Due to ship sailing routes are relatively stable, the global information in terms of time indices (such as release time and deadline) are relatively fixed as well as the schedules of vessels. We take the single vessel scenario into consideration that a vessel generates monitoring videos periodically when sailing from origin port to destination port. These videos could be uploaded to a content server of administrative agencies by infostations deployed along route line. Network topology is shown in Figure 1.

Figure 1.

An illustration of the network topology.

A time-capacity mapping technique is used to transform the original scenario with intermittent network connectivity into a virtually continuous scenario.²⁰ We map the time indices into virtually cumulative capacity values, as shown in Figure 1. The period $[T_{h}^{o}, T_{h + 1}^{i}]$ is defined as the idle period, during which a vessel is not within the coverage of any infostation. For example, $t_{3}$ and $t_{4}$ moments are in an idle period during which no data is transmitted and thus corresponding to the same cumulative capacity $c_{4}$ . On the other hand, $t_{1}$ and $t_{2}$ are in the coverage of infostations and are subsequently related to two different cumulative capacity values $c_{2}$ and $c_{3}$ , respectively.

The time-capacity mapping function $f (t) : [T_{I}, T_{o}] \to [0, 1, \dots \sum_{h = 1}^{H} \sum_{k = 1}^{K} A_{h, k}]$ is given by

f (t) = {\begin{matrix} \sum_{m = 1}^{(t - T_{h_{t}}^{i}) / T_{F}} A_{h_{t}, m} + \sum_{l = 1}^{h_{t} - 1} \sum_{m = 1}^{K_{l}} A_{l, m} \\ if h_{t} \geq 1 and T_{h_{t}}^{i} \leq t \leq T_{h_{t}}^{o} \\ \sum_{l = 1}^{h_{t}} \sum_{m = 1}^{K_{l}} A_{l, m}, otherwise \end{matrix}

(1)

where $h_{t} = \arg max_{h} {T_{h}^{i} \leq t}$ , if $T_{h_{t}}^{i} \leq t \leq T_{h_{t}}^{o}$ , and $h_{t} = 0$ otherwise. Based on the time-capacity mapping, the resource allocation issue could be converted from time-based scheduling to capacity-based scheduling over a continuous horizon,²⁰ such that the JMS theory can be applied to solve the resource allocation problem at a low computational complexity.

Problem formulation

The aim of the issue is achieving better video quality, that is, minimizing the total penalties of tardiness of delivered data considering tardiness and weights of jobs. The offline problem is considered on the precise of knowing all the global information. A network centralized controller is adopted to this issue, which has the ability to schedule resource allocation problem. In this part, we carry out an offline scheduling algorithm that depends on a genetic optimization process, which comprised a novel chromosome representation, a heuristic initialization procedure, as well as a modified crossover and mutation process. These video packets generated by the sailing vessels during the voyage are just like the genes. And these genes are separated into some pieces in a chromosome; therefore, some genes are more outstanding than others, these genes have a strong fitness, and the characters will deliver to next generation as the winner. The operation of the genes is the same as the procedure of uploading the videos to guarantee the high quality. We take into account of this preemption situation that when one video packet is uploading, while the other video needs to be uploaded immediately. Then, the latter video could preempt the band sources of the former as priority, and the former should stop the operation. When the latter is finished uploading the videos, the operation of the former keeps going on.

Therefore, the job-machine problem will be converted into a innovative method to settle which is based on the mathematic method (genetic algorithm (GA)). An effective mathematic JMS problem is represented to minimize the total penalties of tardiness of delivered data considering tardiness and weights of jobs, within each job is expressed as a release time, a deadline, a processing time, and a weight. In the GA, the decision variables in the problem space are represented as individuals of the spatial genetic by the means of coding, and it is a genotype data string structure. At the same time, the objective function value will be converted into fitness value, it is used to evaluate the merits of the individual, and as the basis of genetic operations.

Assumptions

In this work, the model satisfies the following assumptions:

Once a job begins, it will stop until finished.

Without the distraction of other external factors.

Genetic space is empty initially, the algorithm works on the basis of the space.

Constraints

The actual video packet has many special characteristics; therefore, these packets should be subject to some constraints. We describe the characteristics and constraints mathematically in the following:

Arrival time constraints. The job cannot be started until the arrival of the job

A_{i} \leq b_{i}

(2)

Allocation constraints. State if the packets are uploaded to the machine

x_{j b_{j}} = {\begin{matrix} 1, if job j is scheduled at interval [b_{j}, b_{j} + p_{j}] \\ 0, otherwise \end{matrix}

Precedence constraints. The processing time require after the starting time and according to the actual requirement to carry out.

Objective function. According to the different packet demands, different jobs can adjust on the basis of the above constraints. Every packet has a deadline which is regarded as the standards of a job. If the job is accomplished later than the deadline, penalty $α_{i}$ for each time unit of the delay is demanded. Each job has a starting time and generates appropriate assignment, which is equivalent to minimize the total penalties of tardiness of delivered data considering tardiness and weights of jobs.

The objective function can be expressed mathematically as follows

min Z = \sum_{i = 1}^{p} (α_{i} \cdot (C P_{i} - d_{i}) \cdot λ_{i})

(3)

Solution

The GA was first introduced by Holland²¹ in 1975. It is a stochastic heuristics, which encompass semi-random search method whose mechanism is based on the simplifications of evolutionary processes observed in nature. GAs start with an initial population of chromosomes (also called individuals) representing different possible solutions to a problem. A chromosome consists of some genes. GAs work iteratively, each single iteration is called a generation. At each generation, the fitness of each chromosome is evaluated, which is decided by the fitness function, and the chromosome is stochastically selected for the next generation based on its fitness. New chromosomes, called offspring (also called children), are produced by two genetic operators, crossover and mutation. The children are supposed to inherit the excellent genes from their parents, so that the average quality of solutions is better than that in the previous generations. This evolution process is repeated until some termination criteria are met.²² The following sub-sections describe in detail how the GA is developed to solve the above Job-Machine problem in our scenario.

Representation

Because the GA cannot deal with the date of the solution space directly, they must be coded as the spatial genetic genotype data string structure. In constructing the GA, the first thing to solve is to define an appropriate genetic representation (coding). An appropriate representation is the key to all the subsequent steps of the GA. In this article, we can develop a special chromosome representation. A vessel generates videos during the time sailing from origin port to the destination, and each video can be divided into packets. We define the video packets as the genes. Then, each chromosome is a sequence of genes whose length is equal to the capacity of the machine to which packet can be processed. In a chromosome, the weight of each gene contributes to the quality of packets which the corresponding machine processes. Figure 2 presents an example of this representation which considers a problem with eight packets to be assigned to the appropriate machine.

Figure 2.

Sample of the chromosome representation.

Initialization

The GA operates on the basis of a population of chromosomes. Due to the GA group operations requirement, we must prepare a certain number of initial solution of the initial group for genetic operations. The initial population of each individual is generated by random method. The performance of the GA scheme corresponding to a random start is better than from the pre-selected starting population. In this study, each chromosome is initialized by assigning each packet randomly, with the number of packets 1 to n, to the machine which can deal with it. The initialization process can be described as follows:

Step 1. Initialize parameters: index $i = 1$ , u represent a population size, and the population $PPN = {\emptyset}$ and a maximum quantity QTY of packets which the machine can process.

Step 2. Randomly generate an integer string chromosome $CH R_{i}$ , $PPN = PPN \cup CH R_{i}$ .

Step 3. Set $i = i + 1$ , if $i > u$ , STOP, else go to Step 2.

The process for randomly generating a chromosome is detailed as follows:

Step 1. Set index $j = 1$ . For the machine, let $PTY = 1$ , where $PTY = 1$ represents the probability that a machine is selected to process relevant packets.

Step 2. To select the machine which can process packet j.

Step 3. The machine with greater PTY will be selected with a greater probability to process this operation preferentially.

Step 4. Assign operation j to selected machines. At the same time, for the selected machine, let $PTY = PTY - \frac{1}{QTY}$ .

Step 5. Set $j = j + 1$ . If $j > n$ , STOP, else go to Step 2.

Fitness and selection

GA in the search process generally do not need other external information, only use fitness value to evaluate the merits of the individual or solution, and as the basis of genetic operation later. Fitness function is defined as the fitness of each chromosome so as to determine which will reproduce and survive into the next generation. It is relevant to the objective function to be optimized. Given a particular chromosome, the value of fitness function, fitness, represents its probability to survive. The greater the fitness of a chromosome, the greater the probability to survive. In this study, the fitness function fitness is defined as the function of the objective function, which is expressed as follows

fitness = \frac{1}{Z + 1} = \frac{1}{\sum_{i = 1}^{p} (α_{i} \cdot (C P_{i} - d_{i}) \cdot λ_{i}) + 1}

(4)

The selection in GAs, based on the natural evolution law of survival of the fittest, is the process in which chromosomes are selected for the next generation in terms of their fitness. Many selection schemes have been put forward. The tournament selection is usually utilized because it is easy to implement and provides appropriate solutions. In this study, this scheme is used and its procedure can be presented as follows:

Step 1. Set a tournament size s.

Step 2. Generate a random sequence of the chromosomes in the current population.

Step 3. Compare the fitness value of the chromosomes listed in the permutation and select to copy the best one into the next generation. Abandon the strings compared.

Step 4. If the permutation disappears, generate another permutation.

Step 5. Repeat Steps 3 and 4 until no longer need to select the next generation.

The scheme can balance the population diversity and selective pressure by adjusting the tournament size s. The more value of s is large, the more the selective pressure increases while decreasing the population diversity.

Genetic operators

Genetic operators are used to combine existing solutions with other methods and ensure the diversity. The former can be carried out by crossover, and the latter can be put into effect by mutation. The detailed descriptions of the two operators are as follows.

Crossover

The crossover operation is the main genetic operator in GA. Simple crossover can be divided into two steps: first randomly matched for individuals in the population; second, in matching the individual random set intersections, matching the individual exchange part information. Crossover process used for reproduction of a pair of children from a parent chromosome is cross-validation method. A large number of crossover operators have been proposed. Uniform-order crossover is commonly utilized because it has the advantage of preserving the position of some genes and the relative ordering of the rest. In this study, a modified crossover operator similar to the uniform-order crossover is developed and described in detail:

Step 1. Randomize generate a bit string with same length as the chromosomes.

Step 2. Fill in some of the positions in Child 1 by copying the genes from Parent 1 wherever the bit string contains 1. (Now in Child 1, the positions are filled in wherever the bit string contains 1 and positions are left blank wherever the bit string contains 0.)

Step 3. Make a list of the genes from Parent 1 associated with 0 in the bit string.

Step 4. Permute the list of genes so that they follow the same order of genes appeared in Parent 2. For the gene with two or more operations, the first operation in Parent 1 is used for permuting the positions of genes of Child 1 following the order of genes of Parent 2. If the number of a gene in the list is more than the number of corresponding genes with same operations in Parent 2, then the sequence of genes in Parent 2 will be duplicated and append to its end.

Step 5. Fill these permuted genes into the blank positions in Child 1 in the order generated in Step 4.

Step 6. Child 2 is produced using a similar process as above.

The crossover operation is a stochastic process with a probability of crossover. The probability of a typical crossover operator is between 0.6 and 1.0. For the Job-Machine problem in this study, each operation must be processed on the machine. Genes in the chromosome of the machine, therefore, should be independent and the crossover and mutation operations can only be done among genes with the machine. Therefore, for the genes of the machine, we perform the genetic operation respectively. Figure 3 shows an example of the modified uniform-order crossover operator considering situation of machines.

Figure 3.

An example of the modified uniform-order crossover operator considering situation of machines.

Mutation

Mutation operation is processed by the bitwise, and mutation operation is also carried out randomly. In general, the mutation probability is small. Mutation genetic operation is very delicate, it needs use with crossover operation, the purpose is to excavate the diversity of the individuals in the group, to overcome the disadvantage of limited to local solution. The mutation operation is critical to the success of the GA since it diversifies the search directions and avoids convergence to local optima conditions. This is a random variation of operation, which is used to convert a chromosome gene. Only some of the children attend the mutation process. The size of this part composed of mutation probability (the typical value is between 0.0015 and 0.03). Many mutation operators have been put forward. In this study, a modified mutation operation similar to inversion mutation operator is developed. The inverse operation first randomly choose between the two genes with a predetermined chromosome mutation probability. According to an appropriate probability (between 0.6 and 1), the gene with two or more operations will then be divided and the separated operations is recombined with its proximate gene.

Termination criterion

The GA is controlled by a specified number of children and by using a diversity measure to prevent the algorithm. The diversity of the GA is defined as all the standard deviation of the population fitness value of chromosome in a particular generation. If the two termination conditions are met, the GA mechanism shall be terminated.

Improved GA

Basic GA

In order to investigate the effectiveness of the proposed algorithm, the experiment was conducted based on the maritime video packets data transmission from origin port to the destination.

Mode

Only one packet order is processed in the job schedule at any instance of time. Under this mode, if a new packet (packet j) is required to be processed immediately, the current packet (packet i) will be preempted and the new packet is processed. After the new packet is completed, the current packet is resumed. The preemption mode of video packets is illuminated in Figure 4.

Figure 4.

An illumination of preemption mode of scheduling.

Improvement of GA

In the last chapter, we give the solution and the simulation diagram, but in the process of information delivery (maritime video packets transmit from origin port to destination), there are still some problems. In this mode, the deadline of the packets will change with preemption of new packet, which may cause many problems of the algorithm. There is another important reason, lack of local search ability in the basic GA, and there are many factors that affect search behavior, including the determination of initial population encoding strategy, optimizing mechanism, the genetic operation, and many other factors. The basic GA has inherent defects, which leads to the slower convergence speed of optimization process and poor stability. The GA is used to solve the job-machine problem, and it is hard to avoid similar problems.

In order to avoid the premature convergence of local optimum solution to the target function, it is difficult to find the global optimal solution, and the algorithm of this article adopted the following improvements.

Copy operation

In each iteration, only two people at the top of the fitness can continue to reproduce to ensure that the good individual can be further propagated; through the “survival of the fittest” of copy operation in GA, the group continues to evolve in the direction of adaptive evolution, thus copy operation is one of the basic operations of GA.

At present, the proportion of replication is relatively commonly used copy operator; however, this method has some defects. In the execution of a GA, if there are some individuals with better fitness value in the initial population, according to the principles of proportional replication, this part of individuals reproduce many generations, which occupied the main part of the offspring. However, some individuals with bad fitness values are in the position of destruction after the copy operation. And it destroys the diversity of population, which leads to the algorithm easy to fall into premature convergence. Combined with the survival probability method and the optimal retention strategy method, on one hand, the method improves the properties of the diversity of population, on the other hand, it also ensures the convergence of the algorithm.

The main steps of the probability of survival method are as follows:

Step 1. Calculate the average fitness value $\bar{F}$ of the population and the individual fitness value $\bar{F (X)}$ .

Step 2. If $\bar{F (X)} \leq \bar{F}$ , individuals are preserved to next generation, else, calculate $g (X) = (F (X)) / \sum_{X \in S} F (X)$ , and randomly generated a number r between 0 and 1. If $g (X) \geq r$ , the individual will deliver to next generation, otherwise, eliminated.

The main steps of the optimization reserved strategy are as follows:

Step 1. Calculate the fitness value of every individual in present group and find the two individuals with best fitness values.

Step 2. Compare with the best individual from all the individuals and regard the better one as the new individuals.

Step 3. Take the best two individuals into next-generation structure.

Through the above steps, the method ensures the best individual will not be destroyed, but also can search in the direction of the optimal solution. Therefore, the best individual preservation strategy is an important condition of convergence.

Mutation operation

Each iteration of the highest fitness four individuals will take the mutation operation, which produces four new individual populations:

Step 1. Calculate the fitness value of every individual in present group and find the four individuals with best fitness values.

Step 2. Carry out the mutation operation on these individuals and obtain new individuals.

Crossover operation

In the above operations, the selected excellent individuals will proceed to cross operation and then produce four new individual populations.

Putting forward the above improvements is based on the individual which can be evolutionary; the stronger the individual can be evolutionary, the group has the higher quality and the faster the speed of evolution. In fact, individuals in the group can be more evolutionary if GA optimization speed is faster. Individuals can be evolutionary which reflects its contribution to the group quality and speed; how to evaluate the individual can be evolutionary and emphasized the importance of individual, which can improve the evolutionary efficiency. In the actual problems at the same time, the efficiency of the work is improved.

The flow chart is shown in Figure 5.

Figure 5.

The flow chart of improved GA.

The genetic optimized results in this study are obtained on the basis of the following setting:

Population size = 20;

Maximum number of generation = 200;

Crossover probability = 0.6;

Mutation probability = 0.01.

Simulation results

According to the results generated from the experiments, the efficiency of the job-machine problem could be different with different parameters. In this study, the objective function value is converted into fitness value, it is used to evaluate the merits of the individual, and as the basis of genetic operations. According to the procedure, if we change the deadline or the completion time of the packet, the figure will change into irregular and have no convergence. And the penalty of tardiness of the scheduling result is equal or very close to zero, which makes it become more effective after using this algorithm, in the feasible processes of the experiment; the evolutionary track of the fitness over generations is shown in Figure 6. From Figure 6, we find the effectiveness of our proposed GA-based scheduling algorithm.

Figure 6.

The evolutionary track of the fitness over generations.

The standards of algorithm performance is commonly used computing speed, the merits of the solution, and the stability of the algorithm.

In this study, the job-machine problem is modeled as GA problem, the objective function value is converted into fitness value, it is used to evaluate the merits of the individual, and as the improved genetic operations. According to the improved simulation results from the experiments, we can get the best fitness value as we want. During the process, we select the two best individual fitness in each iteration, and the aim of operation is to guarantee the outstanding individuals enter into the next generation. In the mutation operation, it is improved within the allowable range so that the individual satisfies the constraint. The cross operation can make a big difference about the above improvements. And the penalty of tardiness of the scheduling result is equal or very close to zero, which makes it become more effective after using this improved algorithm, in the feasible processes of the experiment, and the evolutionary track of the fitness over generations after improvements is shown in Figures 7 and 8.

Figure 7.

The evolutionary track of the fitness over generations after improvements.

Figure 8.

The evolutionary track of the fitness over generations after improvements with different parameters.

From Figure 7, we find the effectiveness of our proposed GA-based scheduling algorithm. Compared with Figure 6, we find that the improved GA has reduced the local convergence of the early, and the computing speed and convergence speed are better than that in Figure 6. The best value of two experiments is nearly equal, which proves the improvements still adapt to this study (job-machine problem). In the late stage of evolution, with the increase in number of evolution, group solution sets close to the optimal solution gradually, the improved GA still has the stability. From Figure 8, we give some different parameter values about the improvement. Compared with the conclusion about Figure 6, Figure 8 shows good performance about the improvement. We find the effectiveness of our proposed improved GA-based scheduling algorithm.

Conclusion

In this article, an innovative paradigm maritime CPSs is developed. An effective mathematic JMS issue is described to minimize the total penalties of tardiness of delivered data considering tardiness and weights of jobs. And an offline scheduling algorithm based on GA is proposed to optimize the scheduling process. Simulation results demonstrate the effectiveness of the proposed algorithm to solve the JMS issue in maritime CPSs. At the same time, this study also gives the improved GA which is based on JMS issue. In this article, there are still some deficiencies about the improved algorithm, in the future work, we will focus on the JMS issue in maritime CPSs.

Footnotes

Academic Editor: Wei Yu

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported, in part, by Research Project for FY2017 of International Association of Maritime Universities, China Postdoctoral Science Foundation under Grant 2013M530900, Special Financial Grant from the China Postdoctoral Science Foundation under Grant 2015T80238, Natural Science Foundation of China under Grant 61401057, Science and technology research program of Liaoning under Grant L2014213, Dalian science and technology project under Grant 2015A11GX018, NSERC, Canada, Research Funds for the Central Universities 3132016007, China Postdoctoral International Academic Exchange Fund, The Open Research Project of the State Key Laboratory of Industrial Control Technology, Zhejiang University, China (No. ICT170310) and also supported by Scientific Research Foundation for the Returned Overseas Chinese Scholars from Ministry of Human Resources and Social Security.

References

Rajkumar

Lee

Sha

. Cyber-physical systems: the next computing revolution. In: Proceedings of the 2010 47th ACM/IEEE design automation conference (DAC), Anaheim, CA, 13–18 June 2010, pp.731–736. New York: IEEE.

Kim

K-D

Kumar

PR.

Cyber-physical systems: a perspective at the centennial. P IEEE 2012; 100: 1287–1308.

Zheng

Cai

. A study on application-aware scheduling in wireless networks. IEEE T Mobile Comput 2017; 16: 1787–1801.

Zhou

M-T

Harada

Cognitive maritime wireless mesh/ad hoc networks. J Netw Comput Appl 2012; 35: 518–526.

Cellular-news, maritime WiMAX network launched in Singapore, 2008, http://www.cellular-news.com/story/29749.php.

Fall

. A delay-tolerant network architecture for challenged internets. In: Proceedings of the ACM Conference on Applications, technologies, architectures, and protocols for computer communications, Karlsruhe, 25–29 August 2003. New York: IEEE.

Lin

H-M

Pang

A-C

. Performance study on delay tolerant networks in maritime communication environments. In: Proceedings of the 2010 IEEE OCEANS, Sydney, NSW, Australia, 24–27 May 2010.

Zheng

Cai

. Scheduling flows with multiple service frequency constraints. IEEE Internet Things 2017; 4: 496–504.

Zheng

Cai

. An application-aware scheduling policy for real-time traffic. In: Proceedings of the 35th IEEE international conference on distributed computing systems, Columbus, OH, 29 June–2 July 2015, pp.421–430. New York: IEEE.

10.

Duan

Cai

. Distributed auctions for task assignment and scheduling in mobile crowdsensing systems. In: Proceedings of the 37th IEEE international conference on distributed computing systems, Atlanta, GA, USA, 5–8 June 2017.

11.

Cheng

Zhang

. Vehicle-assisted data delivery for smart grid: an optimal stopping approach. In: Proceedings of the 2013 IEEE International Conference on Communications, Budapest, 9–13 June 2013.

12.

Liu

Zhu

. Location privacy preserving dynamic spectrum auction in cognitive radio network. In: Proceedings of the 2013 IEEE 33rd international conference on distributed computing systems, Philadelphia, PA, 8–11 July 2013.

13.

Ren

Zhang

. Dynamic channel access to improve energy efficiency in cognitive radio sensor networks. IEEE T Wirel Commun 2016; 15: 3143–3156.

14.

Deng

Zhang

. Maximizing network utility of rechargeable sensor networks with spatiotemporally-coupled constraints. IEEE J Sel Area Comm 2016; 34: 1307–1319.

15.

Big data in mobile social networks: a QoE oriented frame-work. IEEE Network 2016; 30(1): 52–57.

16.

Zhu

. A novel design for content delivery over software defined mobile social networks. IEEE Network 2015; 29(4): 62–67.

17.

Berman

Dasgupta

Multi-phase algorithms for throughput maximization for real-time scheduling. J Comb Optim 2000; 4(3): 307–323.

18.

Bar-Noy

Guha

Naor

Approximating the throughput of multiple machines in real-time scheduling. J Comput 2001; 31(2): 331–352.

19.

Durr

Thang

Online scheduling of bounded length jobs to maximize throughput. J Sched 2012; 15(5): 653–664.

20.

Liang

Zhuang

Efficient on-demand data service delivery to high-speed trains in cellular/infostation integrated networks. IEEE J Sel Area Comm 2012; 30(4): 780–791.

21.

Holland

. Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press.

22.

Guo

Wong

Leung

SYS

. Mathematical model and genetic optimization for the job shop scheduling problem in a mixed-and multi-product assembly environment: a case study based on the apparel industry. Comput Ind Eng 2006; 50: 202–219.

Genetic optimization–based scheduling in maritime cyber physical systems

Abstract

Keywords

Introduction

System model

Problem formulation

Assumptions

Constraints

Solution

Representation

Initialization

Fitness and selection

Genetic operators

Crossover

Mutation

Termination criterion

Improved GA

Basic GA

Mode

Improvement of GA

Copy operation

Mutation operation

Crossover operation

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References