CN109885383B - A Non-Unit Time Task Scheduling Method with Constraints - Google Patents

Abstract

The invention relates to a non-unit time task scheduling method with constraint conditions, which is used for realizing the following steps: sequencing a plurality of tasks to be executed within a preset time period according to task values; dividing a preset time period into a plurality of time slots with the same width; placing tasks in a time slot according to the ordering for execution, comparing the running time of the tasks with the time slot when each placement is performed, allowing the execution if the running time does not exceed the width of the time slot, maintaining a task scheduling scheme when new tasks are added each time, and generating a corresponding task scheduling scheme when each maintenance is performed; and comparing all the generated task scheduling schemes with the task number of non-unit time executed by the scheduling scheme, and selecting the corresponding scheduling scheme with the maximum task number of non-unit time as an optimal task scheduling scheme. The beneficial effects of the invention are as follows: improved task scheduling efficiency and reduced system resource consumption.

Description

A non-unit time task scheduling method with constraints

Technical Field

The invention relates to a non-unit time task scheduling method with constraint conditions, belonging to the field of computing data processing.

Background Art

In order to complete as many tasks as possible within a limited time on a single processor, it is necessary to optimize the scheduling of these tasks. Therefore, this is an optimal scheduling problem, and each task needs to be given a deadline and timeout penalty as constraints. Most computing tasks cannot be completed in a single unit of time. The time to complete a task is composed of multiple units of time, and task scheduling also needs to consider priority issues.

Summary of the invention

In view of the above problems, the present invention proposes a non-unit time task scheduling method with constraints. This paper conducts a detailed analysis of the task scheduling problem for non-unit time. After decomposing the problem, the similarities of related problems are obtained. The task scheduling problem can be regarded as a relatively simple problem for analysis. Finally, it is improved by combining the solutions to multiple simple problems. A non-unit task scheduling algorithm with constraints is proposed. Experiments have proved that the algorithm proposed in this paper can use constraints to give the optimal scheduling in non-unit time task scheduling, and has excellent performance.

An overview of several example aspects of the present disclosure is as follows. This overview is provided for the convenience of the reader to provide a basic understanding of these embodiments rather than to completely limit the scope of the invention. This overview is not an extensive review of all contemplated embodiments, and is neither intended to identify key or important elements of all aspects, nor to describe the scope of any or all aspects. Its sole purpose is to present some concepts of one or more embodiments in a simplified form as a prelude to a more detailed description presented later. For convenience, the term "some embodiments" may be used herein to refer to a single embodiment or multiple embodiments of the present disclosure.

The technical solution of the present invention includes a non-unit time task scheduling method with constraints, characterized in that the method includes: S1, sorting multiple non-unit time tasks with constraints to be executed within a preset time period according to task value; S2, dividing the preset time period into multiple time slots with the same width; S3, placing the non-unit time tasks in the time slot for execution according to the sorting of step S1, comparing the task running time with the time slot each time the task is placed, allowing execution if the running time does not exceed the time slot width, and using multiple non-unit time tasks that have been running and the corresponding time slot width as a task scheduling scheme, maintaining the task scheduling scheme each time a new task is added, and generating a corresponding task scheduling scheme each time the maintenance is performed; S4, comparing all task scheduling schemes generated in step S3 and the number of non-unit time tasks executed by the scheduling schemes, and selecting the corresponding scheduling scheme with the largest number of non-unit time tasks as the optimal task scheduling scheme.

According to the non-unit time task scheduling method with constraints, the constraints are deadlines and corresponding penalties.

According to the non-unit time task scheduling method with constraints, a task includes a task serial number, a task running time, a task deadline and a task value, wherein the task value is the timeout penalty of the task.

According to the non-unit time task scheduling method with constraints, step S3 specifically includes: comparing the running time of the non-unit time task to be added to the time slot with the time slot width; if the running time of the non-unit time task is greater than the time slot width, the non-unit time task is prohibited from being added to the time slot for running, and the task scheduling plan is not updated at the same time, and the original task scheduling plan is used to find the next non-unit time task; if the running time of the non-unit time task is less than the time slot width, the corresponding non-unit time task is added to the time slot for running, and the task scheduling plan is updated at the same time, and the new task scheduling plan is used to find the next non-unit time task.

According to the non-unit time task scheduling method with constraint conditions, the length of the time slot can be customized.

According to the non-unit time task scheduling method with constraints, the method also includes: if the multiple time slots with the same width within the preset time are integers, then the task scheduling is performed according to step S3; if the preset time period includes multiple standard time slots with the same width and an additional time slot, and the time slot is smaller than the multiple standard time slots with the same width, then the additional time slot is merged with the tail time slot and placed at the tail. Step S3 is executed for multiple non-unit time tasks that are not placed in the time slot, and the maximum value task that can be placed in the tail time slot is selected for execution.

According to the non-unit time task scheduling method with constraints, step S3 also includes: each time a task is added, a corresponding task scheduling scheme is generated, and the scheduling scheme includes the total time slot length, the number of tasks and the total task value; all task scheduling schemes generated each time a task is added are compared, and the scheduling scheme with the largest total time slot length, the largest number of tasks and the highest total task value is used as a solution to multiple non-unit time tasks with constraints to be executed.

The beneficial effects of the present invention are: converting the non-unit time task scheduling problem into a relatively simple problem for analysis, and finally combining and improving the solution to the converted problem, proposing a non-unit task scheduling with constraints, thereby improving the efficiency of task scheduling and reducing the consumption of system resources.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a general flow chart of the method according to the present invention.

DETAILED DESCRIPTION

The technical solution of the present invention includes a non-unit time task scheduling method with constraints, which is suitable for the following clear and complete description of the concept, specific structure and technical effects of the present invention in combination with the embodiments and drawings, so as to fully understand the purpose, solution and effect of the present invention.

It should be noted that, unless otherwise specified, when a feature is referred to as being "fixed" or "connected" to another feature, it may be directly fixed or connected to the other feature, or it may be indirectly fixed or connected to the other feature. In addition, the descriptions of up, down, left, right, etc. used in the present disclosure are only relative to the relative positional relationship of the components of the present disclosure in the accompanying drawings. The singular forms of "a", "said" and "the" used in the present disclosure are also intended to include the plural forms, unless the context clearly indicates other meanings. In addition, unless otherwise defined, all technical and scientific terms used herein have the same meaning as those generally understood by those skilled in the art. The terms used in this specification are only for describing specific embodiments and are not intended to limit the present invention. The term "and/or" used herein includes any combination of one or more related listed items.

It should be understood that, although the term first, second, third etc. may be adopted to describe various elements in the present disclosure, these elements should not be limited to these terms. These terms are only used to distinguish the same type of elements from each other. For example, without departing from the scope of the present disclosure, the first element may also be referred to as the second element, and similarly, the second element may also be referred to as the first element. The use of any and all examples or exemplary language ("for example", "such as" etc.) provided herein is only intended to better illustrate embodiments of the present invention, and unless otherwise required, the scope of the present invention will not be limited.

In order to complete as many tasks as possible within a limited time on a single processor, it is necessary to optimize the scheduling of these tasks. This is an optimal scheduling problem [1], and it is necessary to set a deadline and timeout penalty for each task as constraints.

Figure 1 shows the overall flow chart of the method according to the present invention. Specifically, it includes: S1, sorting multiple non-unit time tasks with constraints to be executed within a preset time period according to task value; S2, dividing the preset time period into multiple time slots with the same width; S3, placing the non-unit time tasks in the time slots for execution according to the sorting of step S1, comparing the task running time with the time slot each time the task is placed, allowing execution if the running time does not exceed the time slot width, and taking multiple non-unit time tasks that have been running and the corresponding time slot width as the task scheduling scheme, maintaining the task scheduling scheme each time a new task is added, and generating a corresponding task scheduling scheme each time the maintenance is performed; S4, comparing all the task scheduling schemes generated in step S3 and the number of non-unit time tasks executed by the scheduling scheme, and selecting the corresponding scheduling scheme with the largest number of non-unit time tasks as the optimal task scheduling scheme.

The technical solution of the present invention further provides the following technical solution

Non-unit time tasks need to run for a certain number of units of time. The time spent switching between tasks is ignored in the following analysis. Assume that the running time of a non-unit time task a is , and a can be obtained from any time point Start at any point in time End (assuming that task a has not been completed), the remaining completion time of task a is ,After a certain number of time units, task a can continue to run from another time point until When , the task is considered completed. Let S be a set of non-unit time tasks. A schedule for S is a task execution sequence in S. ,in Indicates that the task is from Start running at time point, at time point Pause (or end), the execution sequence specifies starting from time point 0, and any task can be run at any time point.

The input of the problem is as follows: a set of n non-unit time tasks ; Given a period of time T (including T time units), as the maximum time span for the execution of the task sequence; given a task The corresponding non-negative integer deadline , and the task Request in Completed within; given task The corresponding non-negative integer time , and the task The running time is units of time; given a task The corresponding non-negative integer penalty , if the task Not in If you complete it within the time limit, you will be punished. , otherwise there is no penalty. The essence of the problem is to find a suitable schedule in the set S so that the sum of penalties is minimized.

1. Problem Analysis

Problem Description: Given n items with known weights and value And a backpack with capacity , find the most valuable subset of items that can fit into the knapsack [6]. Assume that all weights and knapsack capacities are positive integers; the total value need not be an integer.

The instance defined by the first i items, , with the right ,value and the backpack capacity j, .make is the optimal solution for this instance. Here, the capacity j of all subsets that fit into the first i items of the knapsack is divided into two categories: excluding the i-th item and including the i-th item. Note:

1. In the subset that does not include the i-th item, the value of the best subset is defined as ; 2. In the subset including the i-th item, generate the best subset and the first one suitable for the knapsack Optimal subset capacity of items The value of the optimal subset is .

Therefore, the value of the optimal solution among all feasible subsets of the first i items is the maximum of these two values. If the i-th item does not fit into the knapsack, the value of the optimal subset selected from the first i items is the same as the value of the optimal subset selected from the first Select from among the projects, and you will get:

Define the initial conditions as follows:

From the definition of the problem, by comparing the 0-1 knapsack problem with the non-unit time task scheduling problem, we find that if the deadline condition of the latter is removed, and the given T unit time is regarded as the "maximum load weight" of the knapsack, the running time of each task is regarded as the "weight" of the task, and the corresponding timeout penalty is regarded as the "value" of the task, then the non-unit time task scheduling problem can be regarded as the 0-1 knapsack problem. Correspondingly, the method for solving the optimal solution of the 0-1 knapsack problem can be similarly used as a reference for the solution method of the non-unit time task scheduling problem.

2.2 Analysis and reasoning of the unit time task scheduling problem with deadlines and penalties

Similar to the scheduling of non-unit-time tasks, a unit-time task is a job, such as a program to be run on a computer, that takes only one unit of time to complete. Given a finite set S of unit-time tasks [8], the schedule of S is to permute the order in which these tasks are executed.

The problem has the following input:

1. Collection Unit time task;

2. A set of n integer deadlines , so that each satisfy and tasks Should be by time Finish;

3. A set of n non-negative weights or penalties If the task Not on deadline If it is completed before, there will be a penalty, otherwise there is no penalty.

In summary, we want to find a schedule S that minimizes the total penalty due to missed deadlines.

Therefore, the search finds the best schedule where the set A of assigned tasks lies. After A is determined, a canonical ordering of the best schedule can be produced by listing the elements of the actual schedule A in order of monotonically increasing deadlines and then listing the near-term tasks (S-A).

If there exists a schedule for these tasks, then set A has no late tasks. Clearly, the set of early tasks in the schedule forms a separate set of tasks. Consider the question of whether a given set of tasks A is separate. For ,make represents the number of tasks in A whose deadline is t or earlier, .

Lemma 1 For a task set A, the following statements are equivalent.

1. Set A is unique.

2. For ,have .

3. If the tasks in A are scheduled in order of monotonically increasing deadlines, no task will be late.

It is easy to see that in the unit time task scheduling problem, changing the task completion time from a single unit time to multiple unit times can be regarded as a non-unit time task. Therefore, except for the two constraints of the deadline and corresponding penalty induced by the non-unit time, the non-unit time scheduling task is a generalized unit time scheduling task.

1. Algorithm Problem Transformation

3.1 Transformation of unit time task scheduling problem

From 2.2, we can see that the difference between the problem in this paper and the problem of scheduling tasks per unit time is that the tasks in the latter are all per unit time, so it is only necessary to ensure that the tasks can be started before the deadline; while the tasks in this paper require several unit time. To run, if we want to ensure the task We must ensure that we are not "punished" Can Started running before, and had enough time ( ) makes Can (or before) completion.

Since the non-unit time tasks in this paper do not need to run continuously, we can put the non-unit time tasks Split into unit time tasks, each task has a deadline of , the task The penalty is defined as:

• If it belongs to of If all unit time tasks can be completed on or before their respective deadlines, the penalty is 0;

• If any of If the unit time task is not completed on or before its own deadline, the penalty is .

After the non-unit time task scheduling problem has been transformed as above, we can consider whether it can be solved using the algorithm for solving the unit time task scheduling problem. The problem gives the concept of independent set A and its equivalent form, and transforms its solution into the problem of constructing an independent set A of the task set S so that the sum of the timeout penalties of the tasks contained in set A is maximized. To construct an independent set A , we need to consider how to determine whether a task a with a running time of t and a deadline of d can be added to an existing independent set A to form a new independent set. For unit time tasks , from the equivalent form of the independent set A, we can know that as long as , then task a can be added to the independent set A. However, for the non-unit time task a in this paper, since it is necessary to ensure that all t unit time tasks belonging to a can be completed on d (or before), it must satisfy , task a can be added to the independent set A. Therefore, for unit time tasks and non-unit time tasks, the judgment conditions are the same.

Lemma 2: Given a task a with a running time of t and a deadline of d , and an existing independent set A , a can be added to A to form a new independent set if a satisfies the following conditions:

Assume there is a set with a (sum of timeout penalties) larger than A , and task a is the task with the smallest timeout penalty d in A , then there must be a task that is not in set A and has a timeout penalty of Mission , so that and Can be added to set Aa , then just replace task a and task , we can get a set larger than A. But we cannot find such a task , because if and Ability to join collections ,So It must already be in set A , because when constructing set A, tasks are selected from large to small according to their timeout penalties. So it can be proved that A is a maximal independent set of S.

However, for non-unit time task scheduling problems, using the method in the unit time task scheduling problem cannot guarantee that the obtained set A is the largest.

For example, given a time slot of T = 7 time units, containing 5 tasks as shown in Table 1:

Table 1

Current Tasks , , , , Yes If the tasks are sorted from large to small, we can try to find a maximum independent set A using the solution to the unit time task scheduling problem with deadlines and penalties. ,because ,so A can be added. Then consider , ,so You can also add A. Then , ,so Also added to A. At this time, the state of the time slot is shown in Table 2 (where the unit time tasks belonging to the same non-unit time task are represented by the same task number):

Table 2

The only remaining slot is time point 1, so the following tasks and First, the total penalty of the task currently in the time slot is calculated to be 15, but this is not the maximum value, because we can find a task scheduling method as shown in Table 3, which makes the total penalty 16.

Table 3

3.2 0-1 Knapsack Problem Transformation

As can be seen from 2.1, the difference between the 0-1 backpack and the problem in this article is that the latter adds a "deadline" constraint on the "items" (i.e., tasks). In this case, in order to ensure that the "items" can be put into the "backpack", in addition to having "space", the "deadline" constraint must also be met.

The following is another description of the non-unit time task scheduling problem, which makes it closer to the 0-1 knapsack problem:

Given N known running times , the value is and the deadline is and a time slot of length T units, find a task schedule that can fit into the given time slot and has the greatest value while meeting the task deadline.

From the recursive formula (1) of the knapsack problem, we can see that for the ith item, if this item is not selected or cannot be added to the knapsack, the maximum value that the first i items can obtain is the same as the first i - 1 items. Otherwise, a solution that can place the ith item (i.e. ), compare this solution with the previous one The total value of the items, select the largest one as the maximum value of the first i items, that is This recursive formula is also applicable to the problem in this paper, but it cannot guarantee that the i- th task will be added to the solution. After that, the deadline can still be met. Therefore, it is also necessary to judge the solution before selecting the i- th task. After adding the i -th task, can the deadline constraint still be met? If not, the i- th task cannot be selected. The recursive formula of this paper is given below:

At present, we need to consider how to judge a given solution After adding the i- th task, can the deadline still be met? , the only information available is the current maximum value, which obviously cannot make a judgment, so what information needs to be added?

In the previous analysis, given a known independent set A and a task a , we can determine whether task a can be added to A. Therefore, the additional information is that each solution The corresponding independent set A is the task that has been added to A. Expand to a table of length N + 1 , where N is the number of tasks, Indicates the maximum value corresponding to the current solution. For 1 ,

In order to use the previous method to solve the set A , we need to sort the tasks by value from large to small.

Algorithm Design Based on the analysis in 3.1 and 3.2, we can get the following algorithm according to the definition of non-unit time task scheduling problem and the solutions of 0-1 knapsack problem and unit time task scheduling problem:

Input: Given T units of time, N tasks ( task[1..N]), each task contains 4 attributes (1 ≤i≤N ):

• task[i].num: the task number

• task[i].t: the running time of the task

• task[i].d: the deadline of the task

• task[i].v: the value of the task (or timeout penalty)

Output: The maximum value that can be obtained, and the corresponding task scheduling scheme, that is, for the time slot of T units of time

Which task is run at each point? If the corresponding time slot is empty, it means that any task can be run at this point without affecting the final result. 1: SortByValue(task[1..N]);

2:fori←0toNdo

3:forj←0toTdo4:fork←0toNdo5:F[i][j][k]←0;6:endfor7:endfor8:endfor9:fori←1toTdo10:forj←1toNdo11:iftask[j].t>ithen12:F[ j][i][0]←F[j-1][i][0]13:copyF[j-1][i][1..N]toF[j][i][1..N ]14:else15:if(F[j-1][i][0] F[j-1][i-task[j].t][0]+task[j].v)or(check(F[j-1][i-task[j].t],j, i)=FALSE)then16:F[j][i][0]←F[j-1][i][0]17:copyF[j-1][i][1..N]toF[j ][i][1..N]18:else19:F[j][i][0]←F[j-1][i-task[j].t][0]+task[j]. v20:copyF[j-1][i-task[j].t][1..N]toF[j][i][1..N]21:F[j][i][j]← 122:endif23:endif24:endfor25:endfor26:printSchedule

The entire algorithm is based on the algorithm of the 0-1 knapsack problem, adding the maintenance of each plan and the judgment of whether a task can be added to a certain plan.

In line 1, tasks are sorted by value from large to small, and lines 2-8 initialize the table to be maintained. .

The length of the time slot i in line 9 increases from 1 to T. After each increase, the length of the time slot j in line 10 represents the calculation of the recursive formula (3) from task 1 to task N.

Line 11: If the running time of task j is greater than the current time slot length i, then task j cannot run; Line 15: If the solution Better, or when the time slot length is i, the solution If you cannot join task j, you still choose the solution Otherwise, line 18 is in the solution Note that in lines 13, 17, and 20, the corresponding solutions are copied to the current solution. In line 21, since task j is added, the corresponding Set to 1. Finally, line 27 outputs the maximum value and the scheduling plan

Check function implementation:

Input:

• Current solution S[1..N], if S [ i ]=1( ), indicating that the solution includes task i;

• The newly added a- th task;

• The length T of the current time slot.

• A timeslot structure of length T + 1 (time point 0 cannot be used) timeslots, which is initially T + 1 disjoint sets and supports the following operations:

1. FindEmpty(k): Find a time point before position k that is not used. If not found, return 0;

2.Use(p,i): Use the time point at position p for task i, and merge the set to which time point p belongs with the set before p. Output: If the a - th task can be added to plan S, then return TRUE, otherwise return FALSE. 1:fori1toado2:ifS[i]=1ori=athen3:forj←task[i].ddowntotask[i].d-task[i].tdo4:ifj>Tthen5:k←T6:else7:k←j8:endif9:p←timeslots.FindEmpty(k)10:ifp=0then11:returnFALSE12:endif13:timeslots.Use(p,i)14:endfor15:endif16:endfor17:returnTRUE

In the first row, since the previous tasks are selected from the 1st to the Nth, when detecting the ath task, only the scan .

In the second line, if S [ i ]=1, it means that the i-th task is already in the solution S. If i = a , although , but we can first assume that a can be added to S, and then determine whether the assumption is true.

In the third line, j is reduced from task[i].d to task[i].t, which is equivalent to dividing task j into task[i].t unit time tasks with deadlines of .

Lines 4-8, if the deadline j of the task is longer than the length of the current time slot, then it can only start from the last point of the time slot. The following work is to find a time point for each unit time task. If a time point p can be found, then p is assigned to task i. If it cannot be found (p=0), it means that the previous assumption is not true, so FALSE is returned, otherwise TRUE is returned.

The following is an analysis of the time complexity of the algorithm. Before that, we need to analyze the time complexity of check. If we look at the pseudocode directly, the time complexity of check is not easy to analyze. Consider analyzing it from another angle. First, the implementation of check is based on a fast disjoint set forest with rank merging and path compression, in which FindEmpty(k) is based on the FIND-SET operation, and Use(p,i) is based on the UNION operation. For a given time slot of length T, check can only perform at most T FindEmpty(k) and T Use(p,i) operations, because each time an empty time point is found, the time point will be used. When all T time points are used, check will either return FALSE or TRUE. Therefore, the time complexity of check can be approximately regarded as O ( T ).

Let's analyze the time complexity of schedule again. Assume that the first line uses a time complexity of The sorting algorithm of , lines 2-8 are obviously , considering the worst case, each loop needs to execute the check, then the time complexity of lines 9-25 is Finally, printSchedule can be used in Completed. Therefore, the time complexity of the entire scheduling algorithm is .

4. Experiments and results.

The algorithm for solving the non-unit time task scheduling problem combines the 0-1 knapsack problem and the unit time task scheduling problem. If a set of tasks whose running time is all 1 is input, then the problem to be solved degenerates into the unit time task scheduling problem. If a set of tasks whose deadline is greater than or equal to the time slot length T is input, then the problem degenerates into the 0-1 knapsack problem. In other words, the problems that can be solved by the 0-1 knapsack problem and the unit time task scheduling problem can also be solved by the algorithms of the non-unit time task scheduling problem.

So, set three sets of data:

1. Data on the 0-1 knapsack problem in existing technology

2. Data on the Problem of Unit-Time Task Scheduling with Penalty in the Prior Art

3. Regarding the data of the non-unit time task scheduling problem, this set of data comes from Example (1). We already know that the algorithm for the unit time task scheduling problem cannot solve this set of data. So we can try to see if the algorithm for Problem 0 can solve it.

4. Regarding the data of non-unit time task scheduling problem, this set of data modifies the task deadline based on the third set of data, making the maximum obtainable value smaller.

3.1 Test Data

The first set of data:

Table 4 The first set of data

The second set of data:

Table 5 The second set of data

The third set of data:

Table 6 The third set of data

The fourth set of data:

Table 7 The fourth group of data

3.2 Experimental Results

Group 1:

Table 8 Experimental results of the first set of data

Table 9 The first group of strategies

The obtained maximum value and loading strategy are consistent with the results of the above-mentioned prior art on the data of the 0-1 knapsack problem, but the obtained table is different because the items (tasks) are sorted.

Group 2:

Table 10 The second set of experimental results

Table 11 The second group of strategies

The obtained scheduling strategy is consistent with the scheduling strategy of the above-mentioned prior art regarding unit time task scheduling with penalty. The algorithm in this paper calculates the maximum value, but the results are consistent.

Group 3:

Table 12 Results of the third group of experiments

Table 13 The third group of strategies

This is consistent with the analysis of the examples in the article.

Group 4:

Table 14 Results of the fourth group of experiments

Table 15 The fourth group of strategies

By comparison, it can be seen that the algorithm proposed in this paper can use constraints to give the optimal schedule in non-unit time task scheduling, and its performance is excellent.

This paper makes a detailed analysis of the non-unit time task scheduling problem. By decomposing the problem and comparing the decomposition results with other related problems, the non-unit time task scheduling problem is transformed into a relatively simple problem for analysis. Finally, a non-unit time task scheduling algorithm with constraints is proposed by combining the solution to the transformed problem and improving it. Experiments have verified that the algorithm can solve problems 0, 1, and 2, and can use constraints to give the optimal schedule with excellent performance. The time complexity of the algorithm is . It should be appreciated that embodiments of the present invention may be implemented or implemented by computer hardware, a combination of hardware and software, or by computer instructions stored in a non-transitory computer-readable memory. The methods may be implemented in a computer program using standard programming techniques - including a non-transitory computer-readable storage medium configured with a computer program, wherein the storage medium so configured causes the computer to operate in a specific and predefined manner - according to the methods and drawings described in the specific embodiments. Each program may be implemented in a high-level procedural or object-oriented programming language to communicate with a computer system. However, if desired, the program may be implemented in assembly or machine language. In any case, the language may be a compiled or interpreted language. In addition, the program may be run on a programmed application-specific integrated circuit for this purpose.

Furthermore, the operations of the processes described herein may be performed in any suitable order unless otherwise indicated herein or otherwise clearly contradicted by context. The processes described herein (or variations and/or combinations thereof) may be performed under the control of one or more computer systems configured with executable instructions, and may be implemented as code (e.g., executable instructions, one or more computer programs, or one or more applications) that is executed collectively on one or more processors, by hardware, or a combination thereof. A computer program includes a plurality of instructions that may be executed by one or more processors.

Further, the method can be implemented in any type of computing platform that is operably connected to a suitable computer, including but not limited to a personal computer, a minicomputer, a mainframe, a workstation, a network or distributed computing environment, a separate or integrated computer platform, or in communication with a charged particle tool or other imaging device, etc. Various aspects of the present invention can be implemented in machine-readable code stored on a non-transitory storage medium or device, whether removable or integrated into a computing platform, such as a hard disk, an optical read and/or write storage medium, a RAM, a ROM, etc., so that it can be read by a programmable computer, and when the storage medium or device is read by the computer, it can be used to configure and operate the computer to perform the process described herein. In addition, the machine-readable code, or a portion thereof, can be transmitted via a wired or wireless network. When such media includes instructions or programs that implement the above steps in conjunction with a microprocessor or other data processor, the invention herein includes these and other different types of non-transitory computer-readable storage media. When programmed according to the methods and techniques of the present invention, the present invention also includes the computer itself.

The computer program can be applied to input data to perform the functions herein, thereby converting the input data to generate output data stored in a non-volatile memory. The output information can also be applied to one or more output devices such as a display. In a preferred embodiment of the present invention, the converted data represents physical and tangible objects, including specific visual depictions of physical and tangible objects produced on the display.

The above are only preferred embodiments of the present invention. The present invention is not limited to the above embodiments. As long as the technical effects of the present invention are achieved by the same means, any modifications, equivalent substitutions, improvements, etc. made within the spirit and principles of the present invention shall be included in the scope of protection of the present invention. Within the scope of protection of the present invention, its technical solutions and/or implementation methods may have various modifications and changes.

Claims (2)

1. A non-unit time task scheduling method with constraint conditions is characterized by comprising the following steps:

s1, sorting a plurality of non-unit time tasks with constraint conditions to be executed within a preset time period according to task values;

s2, dividing a preset time period into a plurality of time slots with the same width;

s3, placing tasks with non-unit time in time slots for execution according to the step S1 sequence, comparing the task running time with the time slots when each time is placed, allowing execution if the running time does not exceed the time slot width, maintaining the task scheduling scheme when a plurality of tasks with non-unit time and corresponding time slot widths are already running as a task scheduling scheme, generating a corresponding task scheduling scheme when new tasks are added each time, generating a corresponding task scheduling scheme when each maintenance is performed, and merging the additional time slots with the standard time slots at the tail part if the additional time slots are smaller than the standard time slots with the same width, placing the additional time slots at the tail part for executing the tasks for a plurality of tasks with non-unit time which are not placed in the time slots, and selecting the maximum value task which can be placed in the tail time slots for execution;

s4, comparing all task scheduling schemes generated in the step S3 with the number of tasks in non-unit time executed by the scheduling schemes, and selecting a corresponding scheduling scheme with the maximum number of tasks in non-unit time as an optimal task scheduling scheme;

wherein the constraint conditions are deadlines and corresponding penalties;

the task comprises a task sequence number, a task running time, a task deadline and a task value, wherein the task value is a timeout penalty of the task;

the step S3 specifically includes:

comparing the running time of the non-unit time task to be added into the time slot with the width of the time slot, if the running time of the non-unit time task is larger than the width of the time slot, prohibiting the non-unit time task from being added into the time slot for running, simultaneously, not updating the task scheduling scheme, and searching for the next non-unit time task by using the original task scheduling scheme;

if the running time of the non-unit time task is smaller than the width of the time slot, adding the corresponding non-unit time task into the time slot for running, updating a task scheduling scheme, and searching for the next non-unit time task by using a new task scheduling scheme;

the step S3 further includes: generating a corresponding task scheduling scheme for each task adding, wherein the corresponding scheduling scheme comprises a total time slot length, a task number and a total task value; comparing all task scheduling schemes generated by adding tasks once, and taking the scheduling scheme with the maximum total time slot length, the maximum task number and the highest total task value as the scheduling scheme for solving a plurality of non-unit time tasks with constraint conditions to be executed.

2. The non-unit time task scheduling method with constraint conditions according to claim 1, wherein the length of the time slot can be set in a self-defined manner.