CN111800310B - Scheduling method for task management module of Internet of things test cloud platform - Google Patents
Scheduling method for task management module of Internet of things test cloud platform Download PDFInfo
- Publication number
- CN111800310B CN111800310B CN202010554714.2A CN202010554714A CN111800310B CN 111800310 B CN111800310 B CN 111800310B CN 202010554714 A CN202010554714 A CN 202010554714A CN 111800310 B CN111800310 B CN 111800310B
- Authority
- CN
- China
- Prior art keywords
- test
- task
- algorithm
- scheduling
- test task
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000012360 testing method Methods 0.000 title claims abstract description 541
- 238000000034 method Methods 0.000 title claims description 24
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 119
- 230000002068 genetic effect Effects 0.000 claims abstract description 23
- 230000008901 benefit Effects 0.000 claims abstract description 13
- 230000035772 mutation Effects 0.000 claims description 12
- 238000000638 solvent extraction Methods 0.000 claims description 11
- 238000005192 partition Methods 0.000 claims description 9
- 238000003780 insertion Methods 0.000 claims description 4
- 230000037431 insertion Effects 0.000 claims description 4
- 238000006467 substitution reaction Methods 0.000 claims description 4
- 238000007726 management method Methods 0.000 description 15
- 210000000349 chromosome Anatomy 0.000 description 11
- 238000013142 basic testing Methods 0.000 description 6
- 230000008569 process Effects 0.000 description 6
- 238000013468 resource allocation Methods 0.000 description 6
- 238000009826 distribution Methods 0.000 description 5
- 238000002474 experimental method Methods 0.000 description 5
- 238000005457 optimization Methods 0.000 description 4
- 108090000623 proteins and genes Proteins 0.000 description 4
- 230000009286 beneficial effect Effects 0.000 description 3
- 238000010586 diagram Methods 0.000 description 3
- 230000006978 adaptation Effects 0.000 description 2
- 238000011156 evaluation Methods 0.000 description 2
- 230000006870 function Effects 0.000 description 2
- 238000013439 planning Methods 0.000 description 2
- 230000003044 adaptive effect Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 238000005094 computer simulation Methods 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000006073 displacement reaction Methods 0.000 description 1
- 238000005429 filling process Methods 0.000 description 1
- 238000012423 maintenance Methods 0.000 description 1
- 238000004519 manufacturing process Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000004083 survival effect Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L43/00—Arrangements for monitoring or testing data switching networks
- H04L43/50—Testing arrangements
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/01—Protocols
- H04L67/12—Protocols specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/50—Network services
- H04L67/60—Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/50—Network services
- H04L67/60—Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources
- H04L67/61—Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources taking into account QoS or priority requirements
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Health & Medical Sciences (AREA)
- Computing Systems (AREA)
- General Health & Medical Sciences (AREA)
- Medical Informatics (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses a scheduling algorithm of a task management module of an Internet of things test cloud platform, which comprises the following steps: reading a test task scheduling request, and determining a test case set to be tested, expected latest completion time, priority and test benefit of the test task; reading an automatic test system of the Internet of things test cloud platform, wherein the automatic test system information comprises a test case set, test cost, deployment geographic position and test queue of each automatic test system; inquiring a test task division scheme meeting the test task scheduling request according to a test task division algorithm of a genetic algorithm; if the test task division scheme meeting the test task scheduling request is inquired, outputting the test task division scheme, and if the test task division scheme meeting the test task scheduling request is not inquired, rejecting the test task scheduling request; receiving a test task division scheme and outputting a result; and outputting a final scheduling result.
Description
Technical Field
The invention relates to the technical fields of the Internet of things, a cloud platform, test task management, scheduling algorithms and the like, in particular to a scheduling algorithm of a task management module of the Internet of things test cloud platform.
Background
With the wide application of diversified intelligent internet of things equipment to various aspects of production and life, the performance requirements of people on the internet of things equipment are gradually improved, and the test requirements of the internet of things equipment are rapidly increased. The traditional equipment test is limited by single machine test, excessive manual participation processes and the like, and cannot meet the requirement of large-scale equipment test of the internet of things. The Internet of things testing cloud platform is built for solving the problems; based on the idea of cloud testing, the Internet of things testing cloud platform integrates dispersed testing resources, adjusts the testing flow, and further achieves the aims of improving testing efficiency and improving testing income. The testing task is the core of the whole testing process, and the management of the testing task is also the key for realizing the testing cloud platform of the internet of things.
The test task management module integrating efficient test task scheduling and real-time control of the test tasks is designed and realized, the management efficiency of the test tasks of the equipment of the Internet of things is low, and the problem that the maximum test benefit is realized by dividing different subtasks according to actual requirements and constraints is to be solved is solved.
Disclosure of Invention
Aiming at the defects in the prior art, the invention provides a scheduling algorithm for a task management module of an Internet of things test cloud platform, so that the management efficiency of test tasks is improved, the running speed is increased and the like.
The scheduling algorithm of the task management module of the Internet of things test cloud platform comprises the following steps: step S1, reading a test task scheduling request, and determining a test case set to be tested, the expected latest completion time, the priority and the test benefit of the test task; step S2, reading an automatic test system of the Internet of things test cloud platform, wherein the information of the automatic test system comprises a test case set, test cost, deployment geographic position and test queue of each automatic test system; step S3, inquiring a test task division scheme meeting the test task scheduling request according to a test task division algorithm of a genetic algorithm; step S4, if the test task partition plan meeting the test task scheduling request is inquired, the test task partition plan is output, and if the test task partition plan meeting the test task scheduling request is not inquired, the test task scheduling request is rejected; step S5, receiving a test task division scheme and outputting a result; and step S6, outputting a final scheduling result.
The test task is provided based on the test requirement and is a set of testable atomic test cases. The test task scheduling algorithm is mainly responsible for reasonably allocating test resources for the test tasks and determining the execution sequence of the test tasks. The test task scheduling algorithm mainly solves the problems of test task division and subtest task scheduling. The scheduling algorithm of the task management module of the Internet of things test cloud platform provided by the invention considers the relation between the test cost and the number of subtasks on the basis of determining the test task division problem, and the test task division algorithm based on the genetic algorithm is provided, so that the aim of maximizing the test benefits of the subtasks is fulfilled on the premise of meeting the test task deadline. The sub-test task scheduling problem in the text is to further optimize the execution sequence of the test queues of each automatic test system based on the test task priority on the basis of the test task division result, and achieve the aim of optimizing test resource allocation.
Further, the test task division algorithm based on the genetic algorithm comprises the following steps:
step a, randomly generating a plurality of test task division schemes to form a division scheme collection;
b, selecting any two test task division schemes from the division scheme collection to carry out cross operation, and generating a new test task division scheme;
c, selecting any two test task division schemes from the division scheme collection to perform mutation operation, and generating a new test task division scheme;
step d, reserving the test task division scheme with high fitness in the division scheme set, and eliminating the test task division scheme with low fitness;
and e, circularly performing the steps b to d for a plurality of times to generate an optimal test task division scheme.
Further, the fitness comprises the testing capacity requirement, the latest testing time and the testing cost.
Further, the fitness function is:
g is the benefit of the test task and is a fixed value; m represents the number of subtasks of the partitioning scheme(ii) a n is the number of test cases;
the test cost of the test case i divided in the automatic test system j is shown.
Preferably, the interleaving uses an order interleaving method.
Preferably, the mutation is a substitution mutation method.
Further, the test case is a minimum test unit executable by the automatic test system, and the test case set to be tested includes a plurality of test cases.
Further, in order to adapt to various test environments, the automatic test system can test a plurality of test cases, and one test case can be tested by a plurality of automatic test systems.
Further, in order to improve the utilization rate, the step S5 further includes: and finishing the test queue optimized scheduling of the automatic test system according to the sub-test task scheduling algorithm based on the priority.
Further, the sub-test task scheduling algorithm based on priority comprises the following steps: firstly, arranging unscheduled test cases in each automatic test system in a descending order according to priority; then, if the test case is the highest priority, the test case is directly placed at the head of the test queue, otherwise, a proper position is searched for insertion according to the priority and the expected latest completion time constraint; and finally, setting a scheduling identifier to obtain an optimized test queue. The algorithm schedules and rearranges the execution sequence of the test cases in the test queue based on the priority of the test tasks, completes the deep optimization of the test resource allocation of the automatic test system and improves the utilization rate of the test resources.
The invention has the beneficial effects that:
according to the task scheduling algorithm of the Internet of things test cloud platform task management module, the management efficiency of test tasks is improved, and the running speed is increased; deep optimization of test resource allocation of the automatic test system is completed, and the utilization rate of test resources is improved; on the premise of meeting the test task deadline, the goal of maximizing the test benefits of the sub-test tasks is realized.
Drawings
In order to more clearly illustrate the detailed description of the invention or the technical solutions in the prior art, the drawings that are needed in the detailed description of the invention or the prior art will be briefly described below. Throughout the drawings, like elements or portions are generally identified by like reference numerals. In the drawings, elements or portions are not necessarily drawn to scale.
FIG. 1 is a schematic diagram of a cross-order method according to an embodiment of the present invention;
FIG. 2 is a schematic diagram of an alternative variation method according to an embodiment of the present invention;
FIG. 3 is a diagram illustrating test resources of an automatic test system according to another embodiment of the present invention;
FIG. 4 is a graph of test task scheduling request acceptance rate according to another embodiment of the present invention;
FIG. 5 is a bar graph of test yield for another embodiment of the present invention;
FIG. 6 is a graph illustrating test resource utilization according to another embodiment of the present invention;
FIG. 7 is a graph of weighted latency according to another embodiment of the present invention.
Detailed Description
Embodiments of the present invention will be described in detail below with reference to the accompanying drawings. The following examples are only for illustrating the technical solutions of the present invention more clearly, and therefore are only examples, and the protection scope of the present invention is not limited thereby.
It is to be noted that, unless otherwise specified, technical or scientific terms used herein shall have the ordinary meaning as understood by those skilled in the art to which the invention pertains.
Example one
The scheduling algorithm of the task management module of the Internet of things test cloud platform comprises the following steps: step S1, reading a test task scheduling request, and determining a test case set to be tested, the expected latest completion time, the priority and the test benefit of the test task; step S2, reading an automatic test system of the Internet of things test cloud platform, wherein the information of the automatic test system comprises a test case set, test cost, deployment geographic position and test queue of each automatic test system; step S3, inquiring a test task division scheme meeting the test task scheduling request according to a test task division algorithm of a genetic algorithm; step S4, if the test task partition plan meeting the test task scheduling request is inquired, the test task partition plan is output, and if the test task partition plan meeting the test task scheduling request is not inquired, the test task scheduling request is rejected; step S5, receiving a test task division scheme and outputting a result; and step S6, outputting a final scheduling result.
The test task is provided based on the test requirement and is a set of testable atomic test cases. The test task scheduling algorithm is mainly responsible for reasonably allocating test resources for the test tasks and determining the execution sequence of the test tasks. The test task scheduling algorithm mainly solves the problems of test task division and subtest task scheduling. The scheduling algorithm of the task management module of the Internet of things test cloud platform provided by the invention considers the relation between the test cost and the number of subtasks on the basis of determining the test task division problem, and the test task division algorithm based on the genetic algorithm is provided, so that the aim of maximizing the test benefits of the subtasks is fulfilled on the premise of meeting the test task deadline. The sub-test task scheduling problem in the text is to further optimize the execution sequence of the test queues of each automatic test system based on the test task priority on the basis of the test task division result, and achieve the aim of optimizing test resource allocation.
In this embodiment, the test task partitioning algorithm based on the genetic algorithm includes the following steps:
step a, randomly generating a plurality of test task division schemes to form a division scheme collection; b, selecting any two test task division schemes from the division scheme collection to carry out cross operation, and generating a new test task division scheme; c, selecting any two test task division schemes from the division scheme collection to perform mutation operation, and generating a new test task division scheme; step d, reserving the test task division scheme with high fitness in the division scheme set, and eliminating the test task division scheme with low fitness; and e, circularly performing the steps b to d for a plurality of times to generate an optimal test task division scheme.
Genetic Algorithm (Genetic Algorithm) is an Evolutionary Algorithm (Evolutionary Algorithm) that applies biological growth laws to simulate building artificial computational models, and is based on the Evolutionary theory of darwinian and the Genetic principle of mendelian [30 ]. Following the biological evolution law of 'winning or losing, and survival of the fittest', the genetic algorithm generates a new population by selecting the optimal individuals in each generation of population, and then performing intersection and variation operations, and repeating the iteration process until the optimal individuals converge to obtain the final result.
Genes, chromosomes and populations are three important concepts in genetic algorithm, and an algorithm model and the three concepts are organically fused together, so that the realization of coding is a key step for applying the genetic algorithm. In the test division algorithm, test cases contained in a test task are coded from 0, and meanwhile, an automatic test system mounted under an internet of things test cloud platform is also coded from 0. Therefore, a feasible solution for test task division can be represented as a one-dimensional integer array TDN, where the array subscript represents the test cases of the test task, the array element values represent the automatic test systems to which the test cases are divided, and N represents the number of test cases included in the test task. That is, TD [ i ] ═ j indicates that the ith test case of the test task is divided into the jth automatic test system.
Based on the above coding, three important concepts of genetic algorithms are introduced herein as follows: gene: the corresponding relation between the test cases in the test tasks and the divided automatic test systems; chromosome: a one-dimensional gene sequence corresponding to a partitioning scheme of the test task; population: a set of chromosomes represents a set of partitioning schemes for a test task.
The genetic algorithm has three genetic operators, namely selection, crossover and mutation, and the design of the three operators in the algorithm is specifically described as follows:
the selection operator is a 'natural selection' theory in the genetic algorithm, and by reserving chromosomes with high fitness and eliminating chromosomes with low fitness, the population can be converged and evolved more quickly towards an expected direction. The main objective of the test task partitioning algorithm herein is to guarantee the test net gain maximization while meeting the test capability requirement and the test latest time. On the premise of fixed test yield, the low test cost consumption is ensured; meanwhile, the management and maintenance cost of the test sample and the number of the test subtasks are in positive correlation, and the target of the algorithm can be met if the average net gain of the test subtasks is larger.
In this embodiment, the fitness includes a test capability requirement, a test latest time, and a test cost. The fitness function is:
g is the benefit of the test task and is a fixed value; m represents the number of subtasks of the partitioning scheme; n is the number of test cases;
the test cost of the test case i divided in the automatic test system j is shown.
Preferably, in this embodiment, the crossing uses a sequential crossing method, as shown in fig. 1, and randomly selects two crossing point subscripts (starting from 0) of two chromosomes in the parent, i.e., 2 and 4 in the example of fig. 1. The elements between the intersections are first swapped, 345 in parent 1 into child 2 and 213 in parent 2 into child 1. Each new child then fills the parent element, starting one bit after the second intersection, encountering the existing element skip. The filling process is described below by taking child 1 as an example: filling the parent first element 1 starting from bit 5, skipping since 1 already exists in the child, filling the parent element 2, also existing, skipping again until the parent element 4 is selected; bit 6 fills parent element 5 and bit 7 fills parent element 6; now, the child has been filled to the end, the child head is returned to fill the parent element 7, and then the parent element 8 is filled, so that the construction of the child 1 is completed. Offspring 2 constructs the same way.
In this embodiment, preferably, the variation is a substitution variation method, and the genetic algorithm complements a new gene sequence to the population through variation operation to generate a new chromosome, which is beneficial to finding an optimal division scheme. In the algorithm, a replacement Mutation (Displacement Mutation) method is adopted to complete Mutation operation, and a specific idea is shown in fig. 2. Randomly selecting a chromosome in a parent according to the mutation probability p, then selecting an element string in the chromosome, reinserting to a new position in the remaining element string, thereby generating a new chromosome to replace the original chromosome and entering the next generation evolution process.
In this embodiment, the test case is the smallest test unit executable by the automatic test system, and the test case set to be tested includes a plurality of test cases.
In this embodiment, the automatic test system can test a plurality of test cases, and one test case can be tested by a plurality of automatic test systems.
In this embodiment, differences of different testing tasks of the internet of things testing cloud platform are reflected in testing requirements and testing contents, and are also reflected in priority of the testing tasks. High priority test tasks represent high test yield, stable test requirements and as short a test latency as possible. Therefore, when the test task is scheduled, it is necessary to take the priority of the test task into consideration of the scheduling algorithm. The test task partitioning algorithm based on genetic algorithm introduced in the previous subsection focuses on distributing the test cases contained in the test tasks to different automatic test systems with the goal of maximizing the test yield, and then adding the test cases to the end of the test queue maintained by the automatic test systems. Because the test task division algorithm is performed in the dimension of the test tasks, the sequence of the test cases in the test queue of each automatic test system is only determined by the scheduling operation execution time of the test tasks, and the difference of the priority among different test tasks cannot be reflected, which is not beneficial to realizing the purpose of maximizing the time benefit and the test efficiency of the test resources.
The sub-test task scheduling algorithm based on priority described in this embodiment is designed to solve the above problem. The sub-test task scheduling algorithm is a scheduling algorithm of an automatic test system level, secondary optimization of resource allocation of a test queue of the automatic test system is completed according to priorities of tasks corresponding to different test cases, and the utilization rate of test resources is further improved. The self-test task scheduling algorithm designed herein is executed when the test task partitioning algorithm is successfully executed, the algorithm influence range is the automatic test system in which the queue information in the test task partitioning algorithm result changes, and the test queue of the automatic test system is not allocated with a new test subtask in the test task partitioning process and does not need to be optimized again. After the algorithm starts, traversing a target automatic test system set, and executing the following operations: firstly, arranging unscheduled test cases in each automatic test system in a descending order according to priority; then, if the test case is the highest priority, the test case is directly placed at the head of the test queue, otherwise, a proper position is searched for insertion according to the priority and test time constraint; and finally, modifying the scheduling identification to obtain an optimized test queue.
So the step S5 further includes: and finishing the test queue optimized scheduling of the automatic test system according to the sub-test task scheduling algorithm based on the priority.
In this embodiment, the priority-based sub-test task scheduling algorithm includes the steps of: firstly, arranging unscheduled test cases in each automatic test system in a descending order according to priority; then, if the test case is the highest priority, the test case is directly placed at the head of the test queue, otherwise, a proper position is searched for insertion according to the priority and the expected latest completion time constraint; and finally, setting a scheduling identifier to obtain an optimized test queue. The algorithm schedules and rearranges the execution sequence of the test cases in the test queue based on the priority of the test tasks, completes the deep optimization of the test resource allocation of the automatic test system and improves the utilization rate of the test resources.
In this embodiment, the test case, the test task, the automatic test system, and the test queue model are important elements in the test task scheduling algorithm, and the four elements are defined as follows:
(1) the test case is the smallest test unit which can be executed by the automatic test system mounted under the Internet of things test cloud platform and has the characteristics of being not divisible and being independent of each other. The test duration t is an important attribute of the test case and is also an important influence factor of the test task division algorithm. The test cases and the automatic test systems are in a many-to-many relationship, that is, one test case can be tested by a plurality of automatic test systems, and one test system can also test a plurality of different test cases.
(2) Test task the test task in the internet of things test cloud platform is a set of test cases, and a quintuple (C, T, L, P, G) is used herein to represent a test task. Wherein, C ═ { C ═ C1，c2，c3，…， cnIs the set of test cases, for each ciC all have basic test duration attribute ti. T is the expected latest completion time of the test task and is one of the important constraints of the scheduling algorithm of the test task. L ═ p1，p2，…，pmAnd the attribute is a set of expected test regions of the test tasks and is a reference attribute when the test tasks are scheduled. P is the priority of the test task, and G represents the test benefit brought by the completion of the test task.
(3) Automatic test system the automatic test system is the entity that thing networking test cloud platform carried out the test task, and this paper uses a quadruple (C, M, l, Q) to sign an automatic test system. Similar to the test task, C ═ { C ═ C1，c2，c3，…，cnIs the set of test cases, for each ciC all have basic test duration attribute ti。M＝{m1，m2，m3，…，mnIs the test cost of the automatic test system, each miE, M corresponds to the test cost of the test case of the automatic test system. l is the deployment geographical location of the automatic test system. Q is a test queue maintained by the automatic test system, for each QjE.g., Q, also needs to satisfy QjBelongs to C, and the test queue has the attribute of current test completion time tq. It should be noted that a test subtask is the result of a test task numerator algorithm, representing some automationThe set of test cases to which the test system is assigned.
(4) Each automatic test system mounted under the test cloud platform of the test queue internet of things maintains a test queue Q, and the test queue is a one-dimensional array formed by a series of test cases. When the automatic test system finishes testing a certain test case, the next test case to be tested is obtained from the head of the test queue maintained by the automatic test system. The test queue is abstracted into a binary group { C, n, t }, wherein C represents a test case set in the test queue, and the test cases in the set can be repeated; n represents the number of test cases in the current test queue; t represents the automatic test system test environment switching time.
In addition, the test case models in the test queue are slightly different from the base test case model. In this section, the test cases in the test queue are represented by a quadruple { tt, p, flag, T }, tt represents the test duration of the test case, p represents the priority of the test case, flag represents whether the test case has completed scheduling (0 represents not scheduled, 1 represents completed scheduling), and T represents the latest test completion time of the test case.
Example two
Based on the practical experimental method of the first embodiment.
1. The experimental environment is as follows:
the algorithm is written by using Java language, the experimental environment is a notebook computer, and the algorithm is mainly configured as follows: the 8GB, 64-bit Windows8.1 operating system and Inteli7 processor are used as the memory. The section verifies the effectiveness of the test task scheduling algorithm from four evaluation dimensions of test task scheduling acceptance rate, test resource utilization rate, test income and weighted waiting time. To ensure the applicability of the algorithm, the basic test resources in the experiment are known and fixed, as shown in fig. 3:
the test resources used in the experiment include 10 homogeneous ordinary automatic test systems and 5 customized automatic test systems, the ordinary automatic test systems have a measurable test case set with the scale of 50, and the customized automatic test systems add 10 customized test cases on the basis of the homogeneous automatic test systems, that is, the measurable test case set is 60. The test task request priority is subjected to normal distribution of [1,5], the latest completion time is subjected to random distribution of [20,100], the test case test duration is subjected to random distribution of [1,5], and the test task profit is subjected to random distribution of [10,50 ].
2. And (3) analyzing an experimental result:
the initial adaptation algorithm is selected as a comparison experiment of the algorithm, the initial adaptation algorithm distributes the test tasks to the automatic test system of the test case set which is firstly adapted to the test tasks all the time when the test tasks are divided, and the test queue of the automatic test system executes the test according to the first-in first-out rule. To simplify the following description, the test Task scheduling Algorithm herein is denoted as GPA (Task Planning Algorithm based on Genetic Algorithm and priority) and the comparison Algorithm is denoted as FMA (Task Planning Algorithm based on First-match).
As shown in fig. 4, the acceptance rate of GPA algorithm and FMA algorithm for the test task scheduling request is the same basic test resource capability. As can be seen from the graph, as the number of the test task scheduling requests increases, the acceptance rate of the test task scheduling requests gradually decreases, but the acceptance rate of the GPA algorithm is always higher than that of the FMA algorithm. Under the condition that the scheduling request number of the test tasks is small, because the test resources are sufficient, the difference of the acceptance rate between the two algorithms is not large; however, under the conditions of large scheduling request number of test tasks and tense test resources, the FMA algorithm only selects the automatic test system which is firstly adapted, so that most of the requests cannot meet scheduling conditions and are rejected, and the GPA algorithm comprehensively considers the test capability conditions among different automatic test systems to divide and schedule the test tasks, so the acceptance rate is superior to that of the FMA algorithm.
The test yield is an important index for evaluating the test task scheduling algorithm, and as shown in fig. 5, the GPA algorithm and the FMA algorithm receive the test yields of the same number of test task scheduling requests under the same basic test resource condition. It can be seen from the figure that, under the condition of fewer test task scheduling requests, the gains of the two algorithms are kept consistent, and as the number of the test task scheduling requests increases, the gain of the GPA algorithm is gradually greater than that of the FMA algorithm, because the GPA algorithm needs to meet the target of the highest average gain of subtasks in the test task dividing process, and meanwhile, the request acceptance rate of the GPA algorithm is higher than that of the FMA algorithm under the condition of the larger number of the test task requests.
As shown in fig. 6, the GPA algorithm and FMA algorithm test resource utilization under the same basic test resource capability. The Test Resource Utilization (TRU) is calculated according to the following formula:
wherein, tiRepresenting the actual test duration of each test resource, T representing the time difference between the start of the first test task and the completion of the test of the last test task, and N representing the number of test resources.
Under the condition that the scheduling request number of the test tasks is low, because the scheduling requests of the test tasks are completely accepted, the utilization rate of the test resources of the GPA algorithm is slightly higher than that of the FMA algorithm, but after the request number is changed to 40, because the FMA algorithm adopts the first adaptive mode, the number of automatic test systems meeting the requirements under the condition that the request number is increased is sharply reduced, the subsequent scheduling requests of the test tasks cannot be increased, the resource utilization rate cannot be improved, and at the moment, the test resource utilization rate of the GPA algorithm is greatly higher than that of the FMA algorithm.
In this embodiment, a Weighted Waiting Time (WWT) evaluation test task scheduling algorithm is used to adjust the scheduling of different priority test tasks, and the calculation method is as follows:
WWT＝∑ci∈C piwti
in which wtiRepresenting the waiting test time of the ith test case in the test queue.
As shown in fig. 7, the weighted latency of the GPA algorithm and the FMA algorithm in case the same test task scheduling request is completed. As the test subtask distribution conditions of different automatic test system test queues are different, the weighted waiting time of the horizontal comparison of each algorithm has no fixed development trend, but the vertical comparison shows that the weighted waiting time of the FMA algorithm is higher than that of the GPA algorithm. The GPA algorithm adopts a priority-based sub-test task scheduling algorithm in a test queue of the automatic test system, and reduces the waiting time of a high-priority task under the condition of meeting the latest completion time of a test task, so that the weighted waiting time is lower than that of an FMA algorithm.
The effectiveness of the test task scheduling algorithm based on the genetic algorithm and the priority on the test task division and scheduling problem is proved from four dimensions of test task scheduling request acceptance rate, test income, test resource utilization rate and weighted waiting time in the experiment.
Finally, it should be noted that: the above embodiments are only used to illustrate the technical solution of the present invention, and not to limit the same; while the invention has been described in detail and with reference to the foregoing embodiments, it will be understood by those skilled in the art that: the technical solutions described in the foregoing embodiments may still be modified, or some or all of the technical features may be equivalently replaced; such modifications and substitutions do not depart from the spirit and scope of the present invention, and they should be construed as being included in the following claims and description.
Claims (7)
1. The scheduling method of the task management module of the Internet of things test cloud platform is characterized by comprising the following steps:
step S1, reading a test task scheduling request, and determining a test case set to be tested, the expected latest completion time, the priority and the test benefit of the test task;
step S2, reading an automatic test system of the Internet of things test cloud platform, wherein the information of the automatic test system comprises a test case set, test cost, deployment geographic position and test queue of each automatic test system;
step S3, inquiring a test task division scheme meeting the test task scheduling request according to a test task division algorithm of a genetic algorithm;
step S4, if the test task partition plan meeting the test task scheduling request is inquired, the test task partition plan is output, and if the test task partition plan meeting the test task scheduling request is not inquired, the test task scheduling request is rejected;
step S5, receiving a test task division scheme and outputting a result;
step S6, outputting a final scheduling result;
the test task division algorithm based on the genetic algorithm comprises the following steps:
step a, randomly generating a plurality of test task division schemes to form a division scheme collection;
b, selecting any two test task division schemes from the division scheme collection to carry out cross operation, and generating a new test task division scheme;
c, selecting any two test task division schemes from the division scheme collection to perform mutation operation, and generating a new test task division scheme;
step d, reserving the test task division scheme with high fitness in the division scheme set, and eliminating the test task division scheme with low fitness;
e, circularly performing the steps b to d for a plurality of times to generate an optimal test task division scheme;
the fitness comprises the testing capacity requirement, the latest testing time and the testing cost, and the fitness function is as follows:
g is the benefit of the test task and is a fixed value; m represents the number of subtasks of the partitioning scheme; n is the number of test cases;
the test cost of the test case i divided in the automatic test system j is shown.
2. The scheduling method of the internet of things test cloud platform task management module according to claim 1, wherein: the crossing adopts a sequence crossing method.
3. The scheduling method of the internet of things test cloud platform task management module according to claim 1, wherein: the mutation adopts a substitution mutation method.
4. The scheduling method of the internet of things test cloud platform task management module according to claim 1, wherein: the test case is the minimum test unit executable by the automatic test system, and the test case set to be tested comprises a plurality of test cases.
5. The scheduling method of the internet of things test cloud platform task management module according to claim 1, wherein: the automatic test system can test a plurality of test cases, and one test case can be tested by a plurality of automatic test systems.
6. The IOT test cloud platform task management module scheduling method of claim 1, wherein the step S5 further comprises: and finishing the test queue optimized scheduling of the automatic test system according to the sub-test task scheduling algorithm based on the priority.
7. The scheduling method of the task management module of the internet of things test cloud platform of claim 6, wherein the priority-based sub-test task scheduling algorithm comprises the steps of: firstly, arranging unscheduled test cases in each automatic test system in a descending order according to priority; then, if the test case is the highest priority, the test case is directly placed at the head of the test queue, otherwise, a proper position is searched for insertion according to the priority and the expected latest completion time constraint; and finally, setting a scheduling identifier to obtain an optimized test queue.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010554714.2A CN111800310B (en) | 2020-06-17 | 2020-06-17 | Scheduling method for task management module of Internet of things test cloud platform |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010554714.2A CN111800310B (en) | 2020-06-17 | 2020-06-17 | Scheduling method for task management module of Internet of things test cloud platform |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111800310A CN111800310A (en) | 2020-10-20 |
| CN111800310B true CN111800310B (en) | 2021-11-26 |
Family
ID=72803438
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010554714.2A Active CN111800310B (en) | 2020-06-17 | 2020-06-17 | Scheduling method for task management module of Internet of things test cloud platform |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111800310B (en) |
Citations (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103049383A (en) * | 2012-12-31 | 2013-04-17 | 博彦科技（上海）有限公司 | Development and testing cloud system |
| CN103795744A (en) * | 2012-10-30 | 2014-05-14 | 上海今日在线科技发展有限公司 | On-line test cloud service platform |
| CN108255720A (en) * | 2018-01-12 | 2018-07-06 | 中国计量大学 | Software automatic test system based on cloud computing framework |
| CN108701265A (en) * | 2016-03-14 | 2018-10-23 | 欧姆龙株式会社 | Learning Service provides device |
| EP3441896A1 (en) * | 2012-09-14 | 2019-02-13 | InteraXon Inc. | Systems and methods for collecting, analyzing, and sharing bio-signal and non-bio-signal data |
| CN109409763A (en) * | 2018-11-08 | 2019-03-01 | 北京航空航天大学 | A kind of dynamic test assignment dispatching method and dispatching platform based on Greedy grouping strategy |
| CN110147316A (en) * | 2019-04-18 | 2019-08-20 | 西北工业大学 | Reduce method of test example in concurrent program |
| CN110210789A (en) * | 2019-06-17 | 2019-09-06 | 广东电网有限责任公司 | Resource distribution dispatching method, the device, equipment of power grid test business |
| CN111064633A (en) * | 2019-11-28 | 2020-04-24 | 国网甘肃省电力公司电力科学研究院 | A method for automatic test resource allocation of cloud-side collaborative power information communication equipment |
| CN111224845A (en) * | 2020-01-03 | 2020-06-02 | 杭州涂鸦信息技术有限公司 | Equipment automatic testing system and method based on Internet of things cloud |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102122251B (en) * | 2011-03-21 | 2016-09-14 | 北京航空航天大学 | A kind of many spacecraft parallel tests method for scheduling task based on genetic algorithm |
| CN103795743A (en) * | 2012-10-30 | 2014-05-14 | 上海今日在线科技发展有限公司 | Safe and intelligent cloud service method |
| CN104811491A (en) * | 2015-04-17 | 2015-07-29 | 华南理工大学 | Cloud computing resource scheduling method based on genetic algorithm |
| CN106936892A (en) * | 2017-01-09 | 2017-07-07 | 北京邮电大学 | A kind of self-organizing cloud multi-to-multi computation migration method and system |
-
2020
- 2020-06-17 CN CN202010554714.2A patent/CN111800310B/en active Active
Patent Citations (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP3441896A1 (en) * | 2012-09-14 | 2019-02-13 | InteraXon Inc. | Systems and methods for collecting, analyzing, and sharing bio-signal and non-bio-signal data |
| CN103795744A (en) * | 2012-10-30 | 2014-05-14 | 上海今日在线科技发展有限公司 | On-line test cloud service platform |
| CN103049383A (en) * | 2012-12-31 | 2013-04-17 | 博彦科技（上海）有限公司 | Development and testing cloud system |
| CN108701265A (en) * | 2016-03-14 | 2018-10-23 | 欧姆龙株式会社 | Learning Service provides device |
| CN108255720A (en) * | 2018-01-12 | 2018-07-06 | 中国计量大学 | Software automatic test system based on cloud computing framework |
| CN109409763A (en) * | 2018-11-08 | 2019-03-01 | 北京航空航天大学 | A kind of dynamic test assignment dispatching method and dispatching platform based on Greedy grouping strategy |
| CN110147316A (en) * | 2019-04-18 | 2019-08-20 | 西北工业大学 | Reduce method of test example in concurrent program |
| CN110210789A (en) * | 2019-06-17 | 2019-09-06 | 广东电网有限责任公司 | Resource distribution dispatching method, the device, equipment of power grid test business |
| CN111064633A (en) * | 2019-11-28 | 2020-04-24 | 国网甘肃省电力公司电力科学研究院 | A method for automatic test resource allocation of cloud-side collaborative power information communication equipment |
| CN111224845A (en) * | 2020-01-03 | 2020-06-02 | 杭州涂鸦信息技术有限公司 | Equipment automatic testing system and method based on Internet of things cloud |
Non-Patent Citations (2)
| Title |
|---|
| "云测试平台的任务调度研究";任进;《中国优秀硕士学位论文全文数据库》;20170331;全文 * |
| "云环境下基于改进遗传算法的任务调度算法";李建锋，彭舰;《计算机应用》;20110131;全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN111800310A (en) | 2020-10-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Ziarati et al. | On the performance of bee algorithms for resource-constrained project scheduling problem | |
| CN111654416B (en) | Internet of things testing cloud platform and method | |
| CN116401037B (en) | Genetic algorithm-based multi-task scheduling method and system | |
| CN113064879A (en) | Database parameter adjusting method and device and computer readable storage medium | |
| CN113821318B (en) | Internet of things cross-domain subtask combination collaborative computing method and system | |
| CN115330189A (en) | Workflow optimization scheduling method based on improved moth flame algorithm | |
| CN118963953B (en) | A method for determining priority of cloud computing task scheduling based on genetic algorithm | |
| CN117455193A (en) | Task allocation method and device | |
| CN108830408A (en) | A kind of equipment support task multi-objective planning method that oriented mission is resource matched | |
| Awadallah et al. | Nurse scheduling using harmony search | |
| CN119003181A (en) | Cloud edge collaborative algorithm programming method, device, equipment and storage medium | |
| CN119597493A (en) | Distributed computing resource intelligent evolution method and system based on digital twin | |
| CN116450366B (en) | Multi-objective optimal scheduling method, equipment and medium for satellite measurement, operation and control resources | |
| Zhang et al. | Sustainable AIGC workload scheduling of geo-distributed data centers: A multi-agent reinforcement learning approach | |
| Zhou et al. | A novel mission planning method for UAVs’ course of action | |
| Li et al. | SLA-based task offloading for energy consumption constrained workflows in fog computing | |
| CN110633784A (en) | Multi-rule artificial bee colony improvement algorithm | |
| CN111984403A (en) | Method and system for distributing and deploying software components in distributed system | |
| CN114647493B (en) | A cloud task scheduling method and device based on immune annealing algorithm | |
| CN111800310B (en) | Scheduling method for task management module of Internet of things test cloud platform | |
| WO2022129631A1 (en) | Solving mixed integer programs using neural networks | |
| Nematpour et al. | Enhanced genetic algorithm with some heuristic principles for task graph scheduling. | |
| CN112163790B (en) | Airport ground resource scheduling method, electronic device and computer readable storage medium | |
| CN113031522A (en) | Low-power-consumption scheduling method suitable for periodically dependent tasks of open type numerical control system | |
| CN116700928A (en) | Task scheduling information generation method, device, equipment and storage medium |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |