SCHEDULING METHOD FOR UNRELATED PARALLEL MACHINE AND RELATED DEVICE THEREFOR
20230078835 · 2023-03-16
Inventors
- Jianjiang WANG (Changsha, CN)
- Jin LIU (Changsha, CN)
- Guanfei YU (Changsha, CN)
- Manhao MA (Changsha, CN)
- Jianghan ZHU (Changsha, CN)
- Jing YU (Changsha, CN)
Cpc classification
International classification
Abstract
A scheduling scheme for an uncorrelated parallel machine is provided in this disclosure, in which a complex overlapping relationship between time windows are analyzed deeply and the upper bound for the linear relaxation of the model is improved. A new preprocessing algorithm is designed, which can successfully schedule more objects to be processed. Specifically, firstly, the first variable indicating whether the object to be processed is scheduled to the time window corresponding to the implementer and the second variable indicating the start time when the object to be processed is allocated to the time window are introduced into the model, and then conflicts or relationships between the time windows are analyzed, the corresponding scheduling scheme can be obtained according to different situations and the scheduling can be performed according to the scheduling scheme. A new improved mixed integer linear programming model (MILP) is obtained.
Claims
1. A scheduling method for an unrelated parallel machine, comprising: processing a first object to be processed, via an implementer, within a corresponding time window in response to determining that a first variable is 1, and taking a second variable to be 0 in response to determining that the first variable is 0; and scheduling the first object to be processed according to the first variable and the second variable, wherein the first variable indicates whether the first object to be processed is scheduled to a time window corresponding to the implementer, if the first object to be processed is scheduled to the time window corresponding to the implementer, the first variable is 1, otherwise, the first variable is 0; and the second variable indicates a start time when the first object to be processed are allocated to the time window, and each object to be processed is processed at most once; processing a second object to be processed, via the implementer, before the first object to be processed in response to determining that a latest end time of the first object to be processed is less than a sum of an earliest start time of the second object to be processed and a switching time of the implementer; and processing the second object to be processed after the first object to be processed in response to determining that the latest end time of the first object to be processed is greater than the sum of the earliest start time of the second object to be processed and the switching time of the implementer; processing the first object to be processed before the second object to be processed, via the implementer, in response to determining that a third variable is 1; and processing the first object to be processed after the second object to be processed in response to determining that a fourth variable is 1; wherein the third variable and the fourth variable respectively indicate scheduling orders of the first object to be processed and the second object to be processed, and the third variable and the fourth variable satisfy a switching time constraint, a consistency constraint and a domain constraint; and establishing a mixed integer linear programming model according to above conditions via the implementer, solving the mixed integer linear programming model to obtain a scheduling scheme for scheduling an object to be processed with a maximum total revenue, and scheduling each object to be processed according to the scheduling scheme, thus obtaining an improved upper bound for a linear relaxation of the mixed integer linear programming model; thereby improving efficiency in scheduling at least the first object to be processed and the second object to be processed via the implementer; and operating the implementer to perform switching operations according to the scheduling scheme; wherein: the implementer comprises at least one satellite in at least one orbit; the first object to be processed comprises a first observation target of the at least one satellite and the second object to be processed comprises a second observation target of the at least one satellite; the switching operations are performed between continuously observing the first observation target and the second observation target; the switching operations comprise sensor shutdown, yawing, attitude stabilization and restarting; and visibility is determined by the at least one orbit of the at least one satellite and a target position, and thus time windows of observation are calculated based on the first observation target, the second observation target, and the at least one satellite; thus the first observation target and the second observation target are pre-scheduled, thereby reducing a scale of problem solving with addition of effective inequalities, and a tighter upper bound of linear relaxation of the mixed integer linear programming model facilitates problem solving.
2. The scheduling method of the unrelated parallel machine according to claim 1, wherein the method further comprises preprocessing the time window before solving the mixed integer linear programming model, and the preprocessing comprises: acquiring time node information of each implementer; accessing the time nodes on the implementer in sequence according to the time node information, updating an end time of an accessed time window in response to determining that the number of the accessed time windows is less than or equal to 3, with the updated end time not exceeding a current time node, and scheduling remaining objects to be processed; pre-scheduling the first object to be processed in the accessed time window in response to determining that the first object to be processed in the accessed time window can be successfully scheduled, and deleting time windows of the objects to be processed on all implementers in the accessed time windows; and pre-scheduling the first object to be processed before the end time of the time window in time sequence in response to determining that the number of the accessed time windows is greater than 3, updating a start time of time windows of the remaining objects to be processed in the accessed time windows after successfully pre-scheduling one object to be processed each time, and scheduling the remaining objects to be processed until a number of time windows of remaining unscheduled objects to be processed is less than or equal to 3.
3. The scheduling method of the unrelated parallel machine according to claim 1, wherein the mixed integer linear programming model is expressed as:
4. The scheduling method of the unrelated parallel machine according to claim 3, wherein the processing the first object to be processed within a corresponding time window in response to determining that the first variable is 1 and taking the second variable to be 0 in response to determining that the first variable is 0 indicates time window constraint, comprises:
ws.sub.jk.sup.lx.sub.jk.sup.l≤t.sub.jk.sup.k,j∈J,k∈M,l∈TW.sub.jk
(we.sub.jk.sup.l−p.sub.j).Math.x.sub.jk.sup.l≥t.sub.jk.sup.l,j∈J,k∈M,l∈TW.sub.jk wherein t.sub.j, j∈J∪{0, n+1} is the second variable, indicating the start time corresponding to the time window tw.sub.jk.sup.l to which a workpiece j is assigned, and p.sub.j indicates processing time.
5. The scheduling method of the unrelated parallel machine according to claim 3, wherein the processing the second object to be processed before the first object to be processed in response to determining that the latest end time of the first object to be processed is less than the sum of the earliest start time of the second object to be processed and the switching time of the implementer comprises:
t.sub.ik.sup.g−t.sub.jk.sup.l≥(p.sub.j+Δ.sub.k).Math.x.sub.jk.sup.l−(we.sub.jk.sup.l+Δ.sub.k).Math.(1−x.sub.ik.sup.g) wherein, t.sub.j, j∈J∪{0, n+1} represents the second variable, p.sub.j represents the processing time, and Δ.sub.k represents the -switching time of the implementer for each implementer k, k∈M; the processing the second object to be processed after the first object to be processed in response to determining that the latest end time of the first object to be processed is greater than the sum of the earliest start time of the second object to be processed and the switching time of the implementer comprises:
t.sub.jk.sup.l−t.sub.ik.sup.g≥(p.sub.i+Δ.sub.k).Math.x.sub.ik.sup.g−(we.sub.ik.sup.g+Δ.sub.k).Math.(1−x.sub.jk.sup.l)
6. The scheduling method of the unrelated parallel machine according to claim 3, wherein the third variable and the fourth variable satisfy the switching time constraint, the consistency constraint and the domain constraint, the switching time constraint comprising:
t.sub.jk.sup.l−t.sub.ik.sup.g≥(we.sub.ik.sup.g+Δ.sub.k).Math.y.sub.ijk.sup.g.sup.
t.sub.ik.sup.g−t.sub.jk.sup.l≥(we.sub.jk.sup.l+Δ.sub.k).Math.y.sub.jik.sup.l.sup.
y.sub.ijk.sup.g.sup.
t.sub.ij.sup.k∈R.sup.+,i,j∈J,k∈M.
7. The scheduling method of the unrelated parallel machine according to claim 3, wherein scheduling remaining objects to be processed comprises: in response to determining that the number of accessed time windows is two, letting η.sup.k.sub.ij=p.sub.i+p.sub.j+Δ.sub.k, where p.sub.i and p.sub.j represent processing time of the objects to be processed I and j, and Δ.sub.k represents the switching time, and the overlapping time windows of the objects I and j to be processed are [ws.sub.ik.sup.l.sup.
8. The scheduling method of the unrelated parallel machine according to claim 6, wherein scheduling remaining objects to be processed comprises: in response to determining that the number of accessed time windows is three, letting ws.sub.ik.sup.l.sup.
9. A scheduling device for an unrelated parallel machine, comprising: a first processing module configured to process a first object to be processed within a corresponding time window in response to determining that a first variable is 1, and take a second variable to be 0 in response to determining that the first variable is 0; and schedule the first object to be processed according to the first variable and the second variable, wherein the first variable indicates whether the first object to be processed is scheduled to a time window corresponding to an implementer, if the first object to be processed is scheduled to the time window corresponding to the implementer, the first variable is 1, otherwise, the first variable is 0; and the second variable indicates a start time when the first object to be processed is allocated to the time window, and each object to be processed is processed at most once; a second processing module configured to process a second object to be processed before the first object to be processed in response to determining that a latest end time of the first object to be processed is less than a sum of an earliest start time of the second object to be processed and a switching time of the implementer; and process the second object to be processed after the first object to be processed in response to determining that the latest end time of the first object to be processed is greater than the sum of the earliest start time of the second object to be processed and the switching time of the implementer; a third processing module configured to process the first object to be processed before the second object to be processed in response to determining that a third variable is 1; and process the first object to be processed after the second object to be processed in response to determining that a fourth variable is 1; wherein the third variable and the fourth variable respectively indicate scheduling orders of the first object to be processed and the second object to be processed, and the third variable and the fourth variable satisfy a switching time constraint, a consistency constraint and a domain constraint; a scheduling module configured to establish a mixed integer linear programming model according to above conditions, solving the mixed integer linear programming model to obtain a scheduling scheme for scheduling an object to be processed with a maximum total revenue, and schedule each object to be processed according to the scheduling scheme, thus obtaining an improved upper bound for a linear relaxation of the mixed integer linear programming model; thereby improving efficiency in scheduling at least the first object to be processed and the second object to be processed via the implementer; and operating the implementer to perform switching operations according to the scheduling scheme; wherein: the implementer comprises at least one satellite in at least one orbit the first object to be processed comprises a first observation target of the at least one satellite and the second object to be processed comprises a second observation target of the at least one satellite; the switching operations are performed between continuously observing the first observation target and the second observation target; the switching operations comprise sensor shutdown, yawing, attitude stabilization and restarting; and visibility is determined by the at least one orbit of the at least one satellite and a target position, and thus time windows of observation are calculated based on the first observation target, the second observation target, and the at least one satellite; thus the first observation target and the second observation target are pre-scheduled, thereby reducing a scale of problem solving with addition of effective inequalities, and a tighter upper bound of linear relaxation of the mixed integer linear programming model facilitates problem solving.
10. An electronic device, comprising a memory, a processor and a computer program stored on the memory and operable on the processor, the processor implementing the method of claim 1 when executing the program.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
[0017] In order to explain technical schemes in this disclosure or related technologies more clearly, the drawings required in the description of the embodiments or the related art will be briefly introduced below; obviously, the drawings in the following description are only embodiments of the present disclosure, and other drawings can be obtained according to these drawings by those of ordinary skill in the art without paying creative labor.
[0018]
[0019]
[0020]
[0021]
[0022]
[0023]
[0024]
[0025]
[0026]
[0027]
[0028]
DETAILED DESCRIPTION
[0029] In order to make the objects, technical schemes and advantages of the disclosure more clear, the disclosure will be further described in detail with reference to specific embodiments and drawings.
[0030] It should be noted that, unless otherwise defined, technical terms or scientific terms used in the embodiments of this disclosure shall have a general meaning understood by those with general skills in the field to which this disclosure pertains. Words “first”, “second” and the like used in the embodiments of this disclosure do not indicate any order, quantity or importance, but are only used to distinguish different components. Similar words such as “including” or“containing” mean that the elements or objects appearing before the words encompass listed elements or objects appearing after the word and their equivalents, with other elements or objects being not excluded. Similar words such as “connected to” or “connected with” are not limited to physical or mechanical connection, but can include electrical connection, direct or indirect. An expression such as “upper”, “lower”, “left” and “right” is only used to express a relative positional relationship. When an absolute position of a described object changes, the relative positional relationship may also change accordingly.
[0031] As mentioned in the background art, the scheduling problem of the unrelated parallel machine exists in all aspects of production and life. In realizing this disclosure, the applicant found that existing solutions to the scheduling problem of the unrelated parallel machine with multiple time windows are very limited. Many scholars have studied the scheduling problem of the unrelated parallel machine with the time windows, and extended their research work to a field of satellite scheduling. In order to improve antenna utilization of a Tracking and Data Relay Satellite System (TDRSS), Rojanasoonthon and Bard studied the scheduling problem of the uncorrelated parallel machines with the time windows. Firstly, a mixed integer linear programming model is established, but considering this complex model, it is difficult to solve large-scale problems in reality. They used two heuristic algorithms to solve the model, the first one is the Greedy Randomized Adaptive Search Algorithm (GRASP), which contains two stages. In a first stage, the object to be processed are sorted by a greedy function, and each object to be processed is scheduled one by one in order to generate an initial feasible solution. In a second stage, a local optimal solution is searched by inserting the object to be processed and swapping neighborhood. Then, a heuristic algorithm similar to dynamic programming is proposed, which is called R-B algorithm. A basic idea of the R-B heuristic algorithm is to construct a directed acyclic graph from priority relations among the objects to be processed, and then to search a longest path of the directed graph. An optimal solution usually cannot be obtained for meta-heuristic algorithms and optimality of the solution also cannot be guaranteed and evaluated, Rojanasoonthon and Bard thus further try to solve the optimal solution to this problem. Based on a special structure of the problem, the mixed integer linear programming model is reconstructed into independent subset major problems and multiple short-path pricing subproblems, and a branch and price algorithm is designed. More comprehensively, the above GRASP heuristic algorithm is used to solve a pricing subproblem. In their research, each object to be processed has multiple time windows, but each object to be processed has only one or two time windows at most on each implementer, and a situation with more time windows is not considered.
[0032] Chen studied a scheduling problem of Earth observation satellites, which is a variant of the scheduling problem of the uncorrelated parallel machines with the time windows. In the study, each object to be processed has multiple time windows on each implementer. By analyzing interdependence among feasible time windows, a new mixed integer linear programming model is designed, and linear relaxation of the model is tightened by improved constraints. Then, a preprocessing algorithm is proposed to reduce a problem size and facilitate solving the algorithm. However, in practical work, because of introduction of a “big M” parameter in the traditional model, it is difficult to obtain a tight upper bound for the linear relaxation of the model. In the traditional model, for any two objects to be processed and any implementer k, it is necessary to define a 0-1 variable y.sub.ij.sup.k, I, j∈J, k∈M, so the number of the variables y.sub.ij.sup.k is n.sup.2m. Therefore, a loose upper bound for the linear relaxation and a large number of 0-1 variables make the traditional model difficult to solve effectively.
[0033] In view of this, a scheduling scheme for an uncorrelated parallel machine is provided in one or more embodiments of this disclosure, in which a complex overlapping relationship between time windows are further analyzed deeply and the upper bound for the linear relaxation of the model is improved. A new preprocessing algorithm is designed, which can successfully schedule more objects to be processed. Specifically, firstly, the first variable indicating whether the object to be processed is scheduled to the time window corresponding to the implementer and the second variable indicating the start time when the object to be processed is allocated to the time window are introduced into the model, and then conflicts or relationships between the time windows are analyzed, the corresponding scheduling scheme can be obtained according to different situations and the scheduling can be performed according to the scheduling scheme. A new improved mixed integer linear programming model (MILP) is obtained, which avoids introduction of a “big M” variable and has a tighter upper bound for linear relaxation. The introduction of 0-1 variables among all objects to be processed is avoided, and solving efficiency of the scheduling scheme can be improved.
[0034] Hereinafter, technical schemes on one or more embodiments of the present disclosure will be explained in detail through specific embodiments.
[0035] Referring to
[0036] In S101, an object to be processed within a corresponding time window is processed in response to determining that a first variable is 1, and a second variable is taken to be 0 in response to determining that the first variable is 0; and the object to be processed is scheduled according to the first variable and the second variable. The first variable indicates whether the object to be processed is scheduled to a time window corresponding to an implementer, if the object to be processed is scheduled to the time window corresponding to the implementer, the first variable is 1, otherwise, the first variable is 0; and the second variable indicates a start time when the object to be processed are allocated to the time window, and each object to be processed is processed at most once.
[0037] In this embodiment, the object to be processed and the implementer may be different in different implementation scenarios. In a scenario of machining mechanical parts, the object to be processed may be a part to be machined, and the implementer may be a lathe. In a vehicle routing problem, the object to be processed can be a path of the vehicle, and the implementer can be the vehicle itself; and in a scenario of satellite scheduling, the object to be processed can be a task of the satellite, and the implementer can be the satellite itself.
[0038] In S102, the second object to be processed is processed before the first object to be processed in response to determining that a latest end time of the first object to be processed is less than a sum of an earliest start time of the second object to be processed and switching time of the implementer; and the second object to be processed is processed after the first object to be processed in response to determining that the latest end time of the first object to be processed is greater than the sum of the earliest start time of the second object to be processed and the switching time of the implementer.
[0039] In S103, the first object to be processed is processed before the second object to be processed in response to determining that the third variable is 1; and the first object to be processed is processed after the second object to be processed in response to determining that the fourth variable is 1. The third variable and the fourth variable respectively indicates scheduling orders of the first object to be processed and the second object to be processed, and the third variable and the fourth variable satisfy switching time constraint, consistency constraint and the domain constraint.
[0040] In S104, a mixed integer linear programming model is established according to above conditions, and solved to obtain a scheduling scheme for scheduling the object to be processed with a maximum total revenue, and the object is scheduled according to the scheduling scheme.
[0041] In this step, the mixed integer linear programming model can be expressed as:
[0042] Here, the model represents a maximum total profit of scheduling the object to be processed, which includes two virtual object to be processed, namely {0, n+1}, which correspond to a starting and ending objects to be processed, J represents a set of the objects to be processed, M represents a set of the implementers, I, j∈J∪{0, n+1}, k∈M, l∈TW.sub.jk and for each object j to be processed, j∈J, the profit is w.sub.j, x.sub.jk.sup.l represents the first variable and is a binary variable. If the object j to be processed is scheduled to a 1-th time window on an implementer k, x.sub.jk.sup.l=1, Otherwise, x.sub.jk.sup.l=0; there are multiple time windows for each object to be processed j and each implementer k, which are defined as TW.sub.jk={tw.sub.jk.sup.1, tw.sub.jk.sup.2, . . . , tw.sub.ik.sup.|TW.sup.
[0043] In this embodiment, each object to be processed should be scheduled within a certain time window. Otherwise, it cannot be scheduled. In addition, each object to be processed should be processed once without interruption, so this model focuses on non-preemptive scheduling, and a scheduling goal is to maximize the total profit of the object to be processed.
[0044] In this embodiment, the mixed integer linear programming model specifically includes:
[0045] This constraint ensures that each object to be processed is scheduled at most once.
x.sub.jk.sup.l∈{0,1},i,j∈J,k∈M,l∈TW.sub.jk
[0046] This constraint is domain constraint of the first variable.
ws.sub.jk.sup.lx.sub.jk.sup.l≤t.sub.jk.sup.k,j∈J,k∈M,l∈TW.sub.jk
(we.sub.jk.sup.l−p.sub.j).Math.x.sub.jk.sup.l≥t.sub.jk.sup.l,j∈J,k∈M,l∈TW.sub.jk
[0047] The above two constraints are time window constraints, which correspond to the following in step S101: the object to be processed within the corresponding time window is processed in response to determining that the first variable is 1, and the second variable is taken to be 0 in response to determining that the first variable is 0. In which, t.sub.j, j∈J∪{0, n+1} is the second variable, which is a real variable, indicating the start time corresponding to the time window tw.sub.jk.sup.l to which a workpiece j is assigned, and p.sub.j indicates processing time.
[0048] For two time windows tw.sub.ik.sup.g and tw.sub.jk.sup.l of two objects I, j to be processed (the first object to be processed and the second object to be processed) on the implementer k, if we.sub.jk.sup.l-p.sub.j-ws.sub.ik.sup.g<Δ.sub.k, which means that if both objects to be processed are scheduled to the implementer k, that is, x.sub.ik.sup.g=1 and x.sub.jk.sup.l=1, then the object to be processed j must be processed before the object to be processed I, thus it is obtained that:
t.sub.ik.sup.g−t.sub.jk.sup.l≥(p.sub.j+Δ.sub.k).Math.x.sub.jk.sup.l−(we.sub.jk.sup.l+Δ.sub.k).Math.(1−x.sub.ik.sup.g)
[0049] This constraint is a switching time constraint, which corresponds to the following in step S102: the second object to be processed is processed before the first object to be processed in response to determining that a latest end time of the first object to be processed is less than a sum of an earliest start time of the second object to be processed and switching time of the implementer. Here, t.sub.j, j∈J∪{0, n+1} represents the second variable, p.sub.j represents the processing time, and Δ.sub.k represents implementer switching time for each implementer k, k∈M.
[0050] For two time windows tw.sub.ik.sup.g and tw.sub.jk.sup.l of two objects I, j to be processed on the implementer k, if we.sub.ik.sup.g−p.sub.i−ws.sub.jk.sup.l<Δ.sub.k, which means that if both objects to be processed are scheduled to the implementer k, that is, x.sub.ik.sup.g=1 and x.sub.jk.sup.l=1, then the object to be processed j must be processed before the object to be processed I, thus it is obtained that:
t.sub.jk.sup.l−t.sub.ik.sup.g≥(p.sub.i+Δ.sub.k).Math.x.sub.ik.sup.g−(we.sub.ik.sup.g+Δ.sub.k).Math.(1−x.sub.jk.sup.l)
[0051] This constraint is a switching time constraint, which corresponds to the following in step S102: the second object to be processed is processed after the first object to be processed in response to determining that the latest end time of the first object to be processed is greater than the sum of the earliest start time of the second object to be processed and switching time of the implementer.
[0052] If both objects to be processed I, j are scheduled to the implementer k, a processing order of the two objects to be processed cannot be confirmed. Therefore, it is necessary to introduce an auxiliary 0-1 variable: a third variable y.sub.ijk.sup.g.sup.
t.sub.jk.sup.l−t.sub.ik.sup.g≥(we.sub.ik.sup.g+Δ.sub.k).Math.y.sub.ijk.sup.g.sup.
t.sub.ik.sup.g−t.sub.jk.sup.l≥(we.sub.jk.sup.l+Δ.sub.k).Math.y.sub.jik.sup.l.sup.
[0053] In addition, the first variable x.sub.jk.sup.l (0-1 variable), the third variable and the fourth variable y.sub.jik.sup.l.sup.
[0054] Meanwhile, the third variable y.sub.ijk.sup.g.sup.
y.sub.ijk.sup.g.sup.
t.sub.ij.sup.k∈R.sup.+,i,j∈J,k∈M.
[0055] It can be seen that in this embodiment, by introducing the second variable t.sub.j, j∈J∪{0, n+1} and the auxiliary 0-1 variable y.sub.ijk.sup.g.sup.
[0056] A specific application scenario of the scheduling method for the unrelated parallel machine according to the present disclosure is given in the following. Algorithms are realized by calling CPLEX 12.8 API with C++. A compiler is Visual Studio 2017, running on Intel I core Ii7-5960x CPU @ 3.00 ghz (16 processors) computer, with 64 Gb memory and Windows 7 operating system.
[0057] In order to evaluate performance of the disclosed model and algorithms, a large number of problem instances are created through simulation. In this example, the object to be processed is the workpiece, and the implementor is a machine. Numbers of machines are 5, 10, 15 and 20 respectively. In addition, a number of time windows in each time interval is randomly generated in ranges of [5,10], [10,15], [15,20] and [20,25]. According to the number of the machines, a number of the workpieces is set from small to large. Therefore, a minimum number of the workpieces is 100 and the maximum number of the workpieces is 1200. The processing time of workpieces is uniformly distributed in a range of [240,360], and the switching time of each machine is uniformly distributed and randomly generated in a range of [180,300]. In addition, a scheduling period is set to be 24 hours. A length of the time window is generated in a interval [400,2000] in seconds. With combination of different numbers of machines and workpieces, a total of 47 problem instances were produced. Detailed parameters of all problem instances are given in Table 1.
TABLE-US-00001 TABLE 1 Test Instance. Instance [M] [I] [J] [EJ] [TW] 5-5-100 [5, 10] 100 98 430 5-5-200
[5, 10] 200 179 438 5-10-200 5 [10, 15] 200 193 741 5-10-100
[10, 15] 400 350 752 5-15-200 5 [15, 20] 200 200 1030 5-15-100
[15, 20] 400 379 1043 5-20-200 5 [20, 25] 200 200 1306 5-20-400 5 [20, 25] 400 385 1313 5-20-600
[20, 25] 600 573 13
10-5-200 10 [5, 10] 200 196 898 10-5-400 10 [5, 10] 400 3
7 914 10-10-200 10 [10, 15] 200 200 1482 10-10-400 10 [10, 15] 400 307 1480 10-10-600 10 [10, 15] 600 556 1484 10-15-400 10 [15, 20] 400 398 2118 10-15-600 10 [15, 20] 600 584 2102 10-15-800 10 [15, 20] 800 755 2084 10-20-400 10 [20, 25] 400 399 2661 10-20-600 10 [20, 25] 600 594 2678 10-20-800 10 [20, 25] 800 793 2698 10-20-1000 10 [20, 25] 1000 961 2716 15-5-200 15 [5, 10] 200 200 1323 15-5-400 15 [5, 10] 400 391 1330 15-5-600 15 [5, 10] 600 548 1332 15-10-400 15 [10, 15] 400 3
9 2248 15-10-600 15 [10, 15] 600
2215 15-10-800 15 [10, 15] 800 766 2229 15-15-400 15 [15, 20] 400 400 3100 15-15-600 15 [15, 20] 600 599 3188 15-15-800 15 [15, 20] 800 793 3150 15-15-1000 15 [15, 20] 1000 979 3155 15-20-600 15 [20, 25] 600 599 4031 15-20-800 15 [20, 25] 800 797 4027 15-20-1000 15 [20, 25] 1000 99
4040 20-5-400 20 [5, 10] 400 395 17
1 20-5-600 20 [5, 10] 600
88 1780 20-5-800 20 [5, 10] 800 731 1846 20-10-400 20 [10, 15] 400 400 2981 20-10-600 20 [10, 15] 600 596 2970 20-10-800 20 [10, 15] 800 792 3018 20-10-1000 20 [10, 15] 1000 973 2990 20-15-600 20 [15, 20] 600 60
4227 20-15-800 20 [15, 20] 800 797 4219 20-15-1000 20 [15, 20] 1000 991 4179 20-20-800 20 [20, 25] 800 800 5365 20-20-1000 20 [20, 25] 1000 998 5380 20-20-1200 20 [20, 25] 1200 1191 5425
indicates data missing or illegible when filed
[0058] In table 1, a column “Instance” represents an identifier of each instance. In addition, columns “|M|”, “|I|”, “|J|”, “|EJ|” and “|TW|” respectively represent a number of the machines, a number of the time windows in each interval, a number of the workpieces, a number of effective workpieces (with available time windows) and a total number of the time windows.
[0059] In order to test the performance of the model and algorithms in this embodiment, solution results are compared with those of Chen et al. Comparison results are shown in Table 2, where “Objective” represents an objective function value, that is, the total profit of the object to be processed. “Gap” represents a distance between a feasible solution and a upper bound of the optimal solution, which is calculated by (UB−Fea)/UB, where UB represents the upper bound of the optimal solution and Fea represents the objective function value of the feasible solution. Solution time is set to be 20 minutes. If the optimal solution is found within 20 minutes, the solution time is displayed in the column “Time(s)”.
[0060] As shown in Table 2, both the method of this embodiment and the method of Chen et al. can provide the a solution to most instances. Specifically, the number of instances for which the optimal solution is obtained by the method of this embodiment is larger than that by Chen et al. (39>34). In addition, for most (21) of instances (33) for which both of the methods can get the optimal solution, the solution time of the method in this embodiment is shorter than that of Chen et al. The main reasons are as follows: 1) The preprocessing algorithm in this embodiment makes more workpieces pre-scheduled, which reduces scale of problem solving; 2) with more effective inequalities are added, the upper bound of linear relaxation of the model in this embodiment is tighter, which facilitates problem solving.
TABLE-US-00002 TABLE 2 Performance evaluation of the model and solving algorithms in this embodiment. Upper Our model algorithms Ch et
model algorithms [7] Instance b
nd Objective Gap Time(s) Objective Gap Time(s) 5-5-100
76
76 0 0.076 576 0 0.077 5-5-200 1012 1012 0 0.089 1012 0 0.144 5-10-200 1081 1081 0 0.171 1081 0 0.125 5-10-
00 1
1
8 0 15.303 1
68 0 63.733 5-15-200 1129 1129 0 16.458 1129 0 30.
1 5-15-
00 2110 2110 0 207.059 2110 0 259.941 5-20-200 1129 1129 0 40.981 1129 0 116.818 5-20-
00 2163 2163 0 1050.110 2161 0.001 — 5-20-600 313
1036 0.
9 — 1029 0.672 — 10-5-200 1103 1103 0 0.078 1103 0 0.047 10-5-400 2041 2041 0 0.125 2041 0 0.125 10-10-200 1129 1129 0 0.1
1129 0 0.078 10-10-400 2237 2237 0 0.265 2237 0 0.265 10-10-600 3045 3045 0 0.686 3045 0 60.139 10-15-400 2241 2241 0 86.769 2241 0 105.800 10-15-600 3205 3205 0 189.321 3205 0 318.077 10-15-800 4095 4095 0 740.211 4067 0.010 — 10-20-400 2173 2173 0 106.921 2173 0 219.001 10-20-600 3238 3238 0 509.098 3238 0 525.2
1 10-20-800 4320 2422 0.439 — 151 0.
65 — 10-20-1000 5302 179 0.966 — 5028 0.052 — 15-5-200 1111 1111 0 0.078 1111 0 0.063 15-5-400 2172 2172 0 0.124 2172 0 0.109 15-5-600 3024 3024 0 0.234 3024 0 0.2
15-10-400 2218 2218 0 0.296 2218 0 0.343 15-10-600 3290 3290 0 0.687 3290 0 0.639 15-10-800 4211 4211 0 1.312 4211 0 89.831 15-15-400 222
2223 0 1.216 2223 0 49.230 15-15-600 3356 3356 0 223.717 3356 0 298.869 15-15-800 4328 4328 0 299.571 4303 0.006 955.558 15-15-1000 5361 531
0.009 — 5325 0.007 — 15-20-600 3235 3235 0 330.303 3235 0 634.947 15-20-800 4338 4334 0.001 1027.100 4338 0 1142.160 15-20-1000 5431 239 0.956 — 208 0.962 — 20-5-400 2207 2207 0 0.141 2207 0 0.156 20-5-600 3149 3149 0 0.203 3149 0 0.203 20-5-800 3
51 3
51 0 0.358 3951 0 0.3
0 20-10-400 2208 2208 0 0.374 2208 0 0.29
20-10-600 31
5 31
5 0 0.546 31
5 0 0.531 20-10-800 4815 4815 0 1.529 4810 0 62.082 20-10-1000 5303 5303 0 3.278 52
6 0.001 14
.
08 20-15-600 3301 3301 0 4.259 3301 0 1
.71
20-15-800 4321 4321 0 235.098 401 0.007 — 20-15-1000 5355 5355 0 881.087 5355 0 1016.620 20-20-800 4498 4498 0 715.176 44
6 0.003 — 20-20-1000 5665 445 0.
21 — 365
— 20-20-1200 6767 303 0.
55 — 2
0.045 —
indicates data missing or illegible when filed
[0061] As an optional embodiment, referring to
[0062] For the case of no less than four time windows, the time windows can also be preprocessed by a forward rolling time window algorithm, which includes following steps:
[0063] S201: acquiring time node information of each implementer;
[0064] S202: accessing the time nodes on the implementer in sequence according to the time node information, updating an end time of an accessed time window in response to determining that the number of the accessed time windows is less than or equal to 3, with the updated end time not exceeding a current time node, and scheduling remaining objects to be processed;
[0065] S203: pre-scheduling the object to be processed in the accessed time window in response to determining that the object to be processed in the accessed time window can be successfully scheduled, and deleting time windows of the objects to be processed on all implementers in the accessed time windows; and
[0066] S204: pre-scheduling the object to be processed before the end time of the time window in time sequence in response to determining that the number of the accessed time windows is greater than 3, updating start time of time windows of the remaining objects to be processed in the accessed time windows after successfully pre-scheduling one object to be processed each time, and scheduling the remaining objects to be processed until a number of time windows of remaining unscheduled objects to be processed is less than or equal to 3.
[0067] In this embodiment, for one time window, there is obviously only one case. For any two time windows, there are two cases, let η.sup.k.sub.ij=p.sub.i+p.sub.j+Δ.sub.k, where p.sub.i and p.sub.j represent processing time of the object to be processed, and Δ.sub.k represents the switching time, and overlapping time windows of the objects to be processed I and j are [ws.sub.ik.sup.l.sup.
[0068] Referring to
[0069] Referring to
[0070] If we.sub.ik.sup.l.sup.
[0071] For any three time windows, for three overlapping time windows, [ws.sub.ik.sup.l.sup.
[0072] Referring to
[0073] Referring to
[0074] Referring to
[0075] Referring to
[0076] Referring to
[0077] Referring to
[0078] Referring to
[0079] Referring to
[0080] Referring to
[0081] Referring to
[0082] In this embodiment, a flow of the forward rolling time window algorithm is referenced in the following. By preprocessing for different cases for multiple time windows, the problem size can be reduced and the solving efficiency can be improved.
TABLE-US-00003 Algorithm 2: Forward-Rolling-Horizon 1 TWS ← 0 // the set of time windows in the current time interval
2 EJobs ← 0
// the set of eligible jobs that can be pre-scheduled; 3 for each time node
t ∈ TN in
ascending order do 4 | if
is the first time node of a time interval then 5 | |.sub.— TWS ← TWS ∪
.sub.ik
6 | else 7 | | if
TWS
≤ 3 then 8 | | | w
.sub.ik = min
we
.sub.ik
,
w
.sub.ik ∈ TWS; 9 | | | if we.sub.ik
− ws.sub.ik
≥ p.sub.i + Δ.sub.k,
w
.sub.ik ∈ TWS and jobs in TWS can be | | | scheduled according to the situations in subsection 4.2 then 10 | | | | Schedule both the jobs TWS and the jobs EJobs 11 | | | |.sub.— return IsReboot = 1; |.sub.— 12 | | else 13 | | | Succ − 0, beginTime ← 0
14 | | |
= min
∈ TWS: 15 | | | if Succ = 0 then 16 | | | | sort the time windows in TWS in an ascending order of the start | | | |.sub.— times; 17 | | | else 18 | | | | sort the time windows in TWS in an ascending order of the finish | | | |.sub.— times
19 | | | for each time window
of the first
TWS
− 3 time windows do 20 | | | | if
+ p.sub.i Δ.sub.k ≤
then 21 | | | | | beginTime
max
beginTime,
+ p.sub.i + Δ.sub.k
22 | | | | | EJobs ← EJobs ∪
23 | | | | | TWS ← TWS\
24 | | | | | for each time window t
.sub.jk
∈ TWS do 25 | | | | | |.sub.—
s.sub.jk
← max
s.sub.jk
,beginTime
; 26 | | | | else 27 | | | | |.sub.— break
| | | |.sub.— 28 | | | if
TWS
≤ 3 and jobs in TWS can be pre-scheduled then 29 | | | | Schedule both the jobs in TWS and the jobs in EJobs
30 | | | |.sub.— return IsReboot = 1; 31 | | | else if Succ = 0 then 32 | | |.sub.— |.sub.— Succ = 1, EJobs
0, goto line 15; 33 | | if
is the beginning time of a time window
(of job i) then 34 | | |.sub.— TWS ← TWS ∪ t
.sub.ik
35 | | else if t is the last time node of the current interval then 36 | | |.sub.— TWS ← 0, EJobs ← 0; | |.sub.— |.sub.— 37 return IsReboot = 0
indicates data missing or illegible when filed
[0083] As a specific embodiment, the performance of this preprocessing algorithm is tested by comparing with a preprocessing strategy of Chen et al. At first, “Our preprocessing I” in table 3 represents the preprocessing algorithm proposed in this embodiment, and “Our preprocessing II” represents combination of the preprocessing algorithm in this embodiment and the preprocessing algorithm of Chen et al. Table 5 lists the comparison results, where “Num” is a number of scheduled objects to be processed in preprocessing. “Objective” and “Time(s)” respectively represent the total profit of pre-scheduling the objects to be processed and the solution time of the pre-processing.
[0084] From the results in Table 3, it can be observed that the number of pre-scheduled objects to be processed in the pre-processing strategies I and II of this embodiment is always greater than or equal to the number of pre-scheduled objects to be processed by Chen et al. In addition, for most instances (34 out of 47), the number of pre-scheduled objects to be processed is larger than that of Chen et al., which is marked in bold. Therefore, compared with the algorithm of Chen et al., the algorithm in this embodiment has a great improvement in preprocessing. In addition, regarding the preprocessing strategies I and II of this embodiment, the number of objects to be processed is the same in all instances. Therefore, it is concluded that the solution time of preprocessing algorithm II in this embodiment is shorter than that of preprocessing algorithm I, which is marked in bold, and combination of the two algorithms plays an important role in improving efficiency of the preprocessing algorithm.
[0085] In some embodiments, referring to the following flow, the time window can also be preprocessed by a backward rolling time window algorithm, and steps of the backward rolling time window algorithm are similar to those of the forward rolling time window algorithm, except that an order of accessing time nodes is reversed and from back to front. Therefore, the backward rolling time window algorithm can be regarded as mirroring of the forward rolling time window algorithm, that is, the start time of the time window becomes the end time of the time window, and the end time of the time window becomes the start time of the time window.
TABLE-US-00004 Algorithm 3: Backward-Rilling-Horizon 1 TWS ← 0 // the set of time windows in the current time interval
2 EJobs ← 0
// the set of eligible jobs that can be pre-scheduled
3 for each time node
∈ TN in a descending order do 4 | if t is the last time node of a time interval then 5 | |.sub.— TWS ← TWS ∪ t
6 | else 7 | | if
TWS
≤ 3 then 8 | | |
= max
,
.sub.ik
∈ TWS 9 | | | if
−
≥ p.sub.i + Δ.sub.k,
∈ TWS and jobs in TWS can be | | | scheduled according to the situations in subsection 4.2 then 10 | | | | Schedule both the jobs in TWS and the jobs in EJobs
11 | | | |.sub.— return IsReboot = 1
| | |.sub.— 12 | | else 13 | | | Succ
0, finishTime
T
14 | | |
= max
∈ TWS; 15 | | | if Succ = 0 then 16 | | | | sort the time windows in TWS in a descending order of the finish | | | |.sub.— times
17 | | | else 18 | | | | sort the time windows in TWS in a descending order of the | | | |.sub.— beginning times; 19 | | | for each time window
of the first
TWS
− 3 time windows do 20 | | | | if
.sub.ik
− p.sub.i − Δ.sub.k ≥
.sub.ik
then 21 | | | | | finishTime ← min
finishTime,
.sub.ik
− p.sub.i − Δ.sub.k
22 | | | | | EJobs ← EJobs ∪
23 | | | | | TWS ← TWS\
.sub.ik
24 | | | | | for each time window t
.sub.jk
∈ TWS do 25 | | | | | |.sub.—
.sub.jk
← min
, finishTime
| | | | |.sub.— 26 | | | | else 27 | | | | |.sub.— break
| | | |.sub.— 28 | | | if
TWS
≤ 3 jobs in TWS can be pre-scheduled then 29 | | | | Schedule both the jobs in TWS and the jobs EJobs
30 | | | |.sub.— return IsReboot = 1; 31 | | | else if Succ = 0 then 32 | | | |.sub.— Succ = 1, EJobs ← 0, goto line 15
|.sub.— 33 | | if t is the finish time of a time window t
(of job i) then 34 | | |.sub.— TWS ← TWS ∪ t
.sub.ik
35 | | else if t is the first time node of the current interval then 36 | | |.sub.— TW S ← 0, EJobs ← 0; | |.sub.— |.sub.— 37 return IsReboot = 0
indicates data missing or illegible when filed
[0086] As an optional embodiment, for the model in the previous embodiment, the non-dominant inequality can also be obtained according to the overlapping information of all the time windows, and the non-dominant inequality can be added to the model, which includes following steps:
[0087] When the number of overlapping time windows is two, let η.sup.k.sub.ij=p.sub.i+p.sub.j+Δ.sub.k, where p.sub.i and p.sub.j represent processing time of the objects to be processed I and j, and Δ.sub.k represents the switching time, and the overlapping time windows of the objects I and j to be processed are [ws.sub.ik.sup.l.sup.
[0088] Referring to
[0089] Referring to
[0090] According to the obtained inequality, the non-dominant inequality can be obtained.
[0091] As an optional embodiment, for step S104 in the previous embodiment, the obtaining the non-dominant inequality according to the overlapping information of all the time windows further includes the following.
[0092] When the number of the overlapping time windows is three, let η.sup.k.sub.ij=p.sub.i+p.sub.j+p.sub.q+2.Math.Δ.sub.k, η.sup.k.sub.ij=p.sub.i+p.sub.j+Δ.sub.k, η.sup.k.sub.jq=p.sub.j+p.sub.q+Δ.sub.k, η.sup.k.sub.iq=p.sub.i+p.sub.q+Δ.sub.k, where p.sub.i, p.sub.j and p.sub.q represent the objects I, j and q to be processed respectively, Δ.sub.k represents the switching time, the three overlapping time windows of the objects I, j and q to be processed are: [ws.sub.ik.sup.l.sup.
[0093] Referring to
[0094] Referring to
[0095] Referring to
[0096] Referring to
[0097] Referring to
[0098] Referring to
[0099] Referring to
[0100] Referring to
[0101] Referring to
[0102] Otherwise, if we.sub.ik.sup.l.sup.
[0103] If we.sub.ik.sup.l.sup.
[0104] If we.sub.qk.sup.l.sup.
[0105] If ws.sub.ik.sup.i+p.sub.i+Δ.sub.k≥ws.sub.qk.sup.l.sup.
[0106] If we.sub.ik.sup.l.sup.
[0107] If we.sub.ik.sup.l.sup.
[0108] If we.sub.ik.sup.l.sup.
[0109] If we.sub.ik.sup.l.sup.
[0110] If ws.sub.ik.sup.l+p.sub.i+Δ.sub.k≥ws.sub.qk.sup.l.sup.
[0111] If we.sub.qk.sup.l.sup.
[0112] If ws.sub.ik.sup.l+p.sub.i+Δ.sub.k≥ws.sub.qk.sup.l.sup.
[0113] Referring to
[0114] Otherwise, if we.sub.qk.sup.l.sup.
[0115] If we.sub.ik.sup.l.sup.
[0116] If we.sub.ik.sup.l.sup.
[0117] According to the obtained inequality, the non-dominant inequality can be obtained.
[0118] As an optional embodiment, referring to
[0119] S301: accessing each time node in time sequence for each implementor.
[0120] S302: recording a start time BeginTime of the time interval and a first time window of the time interval in response to determining that the current time node t is a first start time node of a certain time interval;
[0121] S303: updating a set of accessed time windows in response to determining that the current time node is the end time node of a certain time window and obtaining an effective inequality of the object to be processed in the accessed time window in a time interval [BeginTime, t];
[0122] S304: comparing the effective inequality with inequalities in the existing inequality set, and discarding the effective inequality in response to determining that the effective inequality is a dominant inequality; and adding the effective inequality to the inequality set in response to determining that the effective inequality is a non-dominant inequality;
[0123] S305: removing the dominated inequalities from the inequality set in response to determining that there are inequalities in the inequality set that are dominated or jointly dominated by the effective inequality;
[0124] S306: in response to determining that the current time node t is an end time node of the last time window of a certain time interval, deleting the time node of the first time window tw.sup.l.sub.jk, and continuing to access remaining time nodes from the first time node in sequence;
[0125] S307: adding all of the non-dominant inequalities in the inequality set to the model.
[0126] In this embodiment, an algorithm is proposed to find and recognize the effective inequality. Similar to preprocessing algorithms, an inequality recognition and search algorithm are also based on time nodes and rolling time windows. Definition of inequality domination is as follows:
[0127] Definition 1: For two effective inequalities
when J.Math.I, b.sub.i<=b.sub.j and I=J, b.sub.i=b.sub.j are not held at the same time, the inequality
dominates the inequality
[0128] Note that if the inequality
dominates
then
[0129] Definition 2: for an inequality e:
it is jointly dominated by k inequalities (k>=2):
when
[0130] Definition 3: If an inequality e is neither dominated by another inequality nor jointly by other k (k≥2) inequalities, then the inequality e is a non-dominated inequality; otherwise, the inequality e is a dominant inequality.
[0131] In this embodiment, in order to avoid excessive constraints and a large model, only non-dominant inequalities are added.
[0132] As a specific example, referring to
[0133] A process of adding inequality is described in detail in Table 4. The inequality x1+x2+x4≤2 is jointly dominated by the existing inequality x1+x2≤1 and the implicit inequality x4≤1, so x1+x2+x4≤2 is discarded (round 0, time 14). The resulting inequality x2+x3+x4≤2 is dominated by the existing inequality x1+x2+x3+x4≤2 (round 1, time 16). Further, the inequality x1+x2+x3+x4≤2 in the inequality set is jointly dominated by the newly obtained inequality x3+x4≤1 and the existing inequality x1+x2≤1 (round 2, time 16). Therefore, the inequality x1+x2+x3+x4≤2 is removed from the inequality set. Finally, only the non-dominant inequalities x1+x2≤1 and x3+x4≤1 are added to the model.
TABLE-US-00005 TABLE 4 Inequality recognition and addition process. round time t TWS inequality e set Inequalities 0 0 ∅ / ∅ 2 ∅ / ∅ 4 ∅ / ∅ 6 ∅ / ∅ 8 x.sub.1 / ∅ 10 x.sub.1, x.sub.2 x.sub.1 + x.sub.2 ≤ 1 ∅ 14 x.sub.1, x.sub.2, x.sub.3 x.sub.1 + x.sub.2 + x.sub.4 ≤ 2 x.sub.1 + x.sub.2 ≤ 1 16 x.sub.1, x.sub.2, x.sub.3, x.sub.4 x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 x.sub.1 + x.sub.2 ≤ 1 18 x.sub.1, x.sub.2, x.sub.3, x.sub.4, x.sub.5 x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 + x.sub.5 ≤ 3 x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 1 2 ∅ / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 4 ∅ / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 6 ∅ / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 10 x.sub.2 / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 14 x.sub.2, x.sub.4 / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 16 x.sub.2, x.sub.3, x.sub.4 x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 18 x.sub.2, x.sub.3, x.sub.4, x.sub.5 x.sub.2 + x.sub.3 + x.sub.4 + x.sub.5 ≤ 3 x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 2 4 ∅ / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 6 ∅ / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 14 x.sub.4 / x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 16 x.sub.3, x.sub.4 x.sub.3 + x.sub.4 ≤ 1 x.sub.1 + x.sub.2 ≤ 1, x.sub.1 + x.sub.2 + x.sub.3 + x.sub.4 ≤ 2 18 x.sub.3, x.sub.4, x.sub.5 x.sub.3 + x.sub.4 + x.sub.5 ≤ 2 x.sub.1 + x.sub.2 ≤ 1, x.sub.3 + x.sub.4 ≤ 1 3 6 ∅ / x.sub.1 + x.sub.2 ≤ 1, x.sub.3 + x.sub.4 ≤ 1 14 x.sub.4 / x.sub.1 + x.sub.2 ≤ 1, x.sub.3 + x.sub.4 ≤ 1 16 x.sub.3, x.sub.4 x.sub.3 + x.sub.4 ≤ 1 x.sub.1 + x.sub.2 ≤ 1, x.sub.3 + x.sub.4 ≤ 1 4 6 ∅ / x.sub.1 + x.sub.2 ≤ 1, x.sub.3 + x.sub.4 ≤ 1 16 x.sub.3 / x.sub.1 + x.sub.2 ≤ 1, x.sub.3 + x.sub.4 ≤ 1
[0134] In this embodiment, by adding non-dominant inequalities, the model can be solved more easily.
[0135] In contrast, referring to Table 5, the number of the inequalities in the model in this embodiment is larger than that in Chen et al. In addition, the number of inequalities in the model is much smaller than that in the model containing all inequalities, because the dominant inequalities are ignored. According to theoretical analysis results, the number of the inequalities in the model should be almost ½ of the number of the inequalities in an original mode (n.sup.2/4 vs n(n−1)/2) However, in fact, the number of the inequalities in the model is much smaller (less than ¼ of that of the original model). As for the model in this embodiment, the combination of the model in this embodiment and Chen's model, and Chen's model, the model the inequalities of which is included in this embodiment is the best in most instances, with a shorter optimal solution distance and shorter solution time. This is because more inequalities make the model tighter and easier to be solved.
TABLE-US-00006 TABLE 5 Performance evaluation for different reinforcement strategies. Uppe Chen
strengthening [7] Model w
th all the
Model with ta
Inst
ce bound Gap Time(s) Num Gap Time(s) Num Gap Time(s) N
m 5-5-100
70 0 0.0
0 0 0.0
0 0 0.0
0 5-5-200 1012 0 0.05 0 0 0.05 0 0 0.07 0 5-10-200 1081 0 0.0
0 0 0.08 0 0 0.0
0 5-10-400 1
68 0 30.21 56 0 14.70 1002 0 11.12 275 5-15-200 1129 0 18.74
0 0 14.99 3617 0 18.47
21 5-15-400 21
0
0 0 205.47
70 0 24
.82 11
7 5-20-200 112
0 6
.94
0 0 38.17
0 79.62 1956 5-20-
00 216
0 — 60 0 1075.58 10718 0.
— 20
5-20-600 31
0.96 — 60 0.67 — 11351 0.96 — 2137 10-5-200 1103 0 0.08 0 0 0.05 0 0 0.0
0 10-5-400 2041 0 0.11 0 0 0.1
0 0 0.13 0 10-10-
00 1129 0 0.0
0 0 0.08 0 0 0.14 0 10-10-400 2237 0 0.27 0 0 0.2
0 0 0.28 0 10-10-600 3045 0 0.02 0 0 0.7
1 0 0.83 1 10-15-400 2241 0 126.
8 120 0 81.76 5992 0 59.32 21
0 10-15-
00 3205 0 24
.7
120 0 1
.2
1
26 0 1
4.41 22
10-15-800 4099 0.04 1202.40 121 0 727.47 1123
0 — 2
10-20-
00 2173 0 2
.07 121 0 101.01 10218 0 115.71 3795 10-20-600 323
0
6.
4 120 0 470.
2
20
0 5
4.07 3045 10-20-800 4
20 0.03 — 120 0.05 — 23
9 0.02 — 4
4 10-20-1000 5302 0.06 — 120 0.97 — 23262 0.97 — 4245 15-5-200 1111 0 0.0
0 0 0.0
0 0 0.08 0 15-5-
00 2172 0 0.13 0 0 0.11 0 0 0.19 0 15-5-600 3024 0 0.27 0 0 0.27 0 0 0.25 0 15-10-400 2218 0 0.27 0 0 0.30 0 0 0.41 0 15-10-600 3290 0 0.66 1 0 0.62 1 0 0.75 1 15-10-800 4211 0 1.12 0 0 1.48 0 0 1.28 0 15-10-400 22
3 0 1.31 0 0 1.
0 0 1.25 0 15-15-600 33
0 1
.26 181 0 97.1
14770 0
8
.18 3237 15-15-800 4328 0 360.08 180 0 7
4.76 1
788 0 271.09 3593 15-15-1000 53
1 0 989.84 180 0 492.49 17378 0 1200 3715 15-20-600 3235 0 745.
180 0 294.12 32083 0 63
.06 6013 15-20-800 4338 0.
— 180 0 1022.04 31
87 0 —
15-20-1000
431 0.
— 181 0.
6 —
120 0.9
— 63
1 20-5-400 2207 0 0.1
0 0 0.14 0 0 0.19 0 20-5-600 3149 0 0.22 0 0 0.19 0 0 0.3
0 20-5-
00 3
51 0 0.44 0 0 0.33 0 0 0.44 0 20-10-400 220
0 0.28 0 0 0.27 0 0 0.34 0 20-10-600 31
5 0 0.56 0 0 0.55 0 0 0.
8 0 20-10-800
15 0 1.
7 0 0 1.59 0 0 1.50 0 20-10-1000 5303 0 3.42 1 0 3.4
2 0 3.?? 2 20-15-600 3301 0
.70 0 0
.
0 0 3.50 0 20-15-800 4321 0 202.5
241 0 232.
0 152
0 0 17
.58 34
20-15-1000 53
5 0 898.60 243 0 877.01 21123 0 644.16 4
66 20-20-800 4
98 0 835.98 240 0 713.03
0 — 7580 20-20-1000 5065 0.92 — 240 0.92 — 42
0.92 — 8023 20-20-1200 0707 0.95 — 240 0.95 — 45730 0.95 —
indicates data missing or illegible when filed
[0136] It should be noted that the method of the embodiment of the present disclosure can be performed by a single device, such as a computer or a server. The method of this embodiment can also be applied to distributed scenarios, which is completed by cooperation of multiple devices. In this distributed scenario, one of the devices can only perform one or more of the steps in the method of the embodiment of the disclosure, and the devices can interact with each other to complete the method.
[0137] It should be noted that some embodiments of the present disclosure have been described above. Other embodiments are within the scope of the appended claims. In some cases, actions or steps recited in the claims may be performed in a different order from that in the above embodiments and still achieve the desired results. In addition, the processes depicted in the drawings do not necessarily require the specific or sequential order shown to achieve the desired results. In some embodiments, multitasking and parallel processing are also possible or may be advantageous.
[0138] On a basis of the same concept, corresponding to the method of any of the above embodiments, a scheduling device for an unrelated parallel machine is also provide in this disclosure.
[0139] Referring to
[0140] a first processing module configured to process an object to be processed within a corresponding time window in response to determining that a first variable is 1, and take a second variable to be 0 in response to determining that the first variable is 0; and schedule the object to be processed according to the first variable and the second variable, wherein the first variable indicates whether the object to be processed is scheduled to a time window corresponding to an implementer, if the object to be processed is scheduled to the time window corresponding to the implementer, the first variable is 1, otherwise, the first variable is 0; and the second variable indicates a start time when the object to be processed are allocated to the time window, and each object to be processed is processed at most once;
[0141] a second processing module configured to process the second object to be processed before the first object to be processed in response to determining that a latest end time of the first object to be processed is less than a sum of an earliest start time of the second object to be processed and switching time of the implementer; and process the second object to be processed after the first object to be processed in response to determining that the latest end time of the first object to be processed is greater than the sum of the earliest start time of the second object to be processed and the switching time of the implementer;
[0142] a third processing module configured to process the first object to be processed before the second object to be processed in response to determining that the third variable is 1; and process the first object to be processed after the second object to be processed in response to determining that the fourth variable is 1; wherein the third variable and the fourth variable respectively indicate scheduling orders of the first object to be processed and the second object to be processed, and the third variable and the fourth variable satisfy switching time constraint, consistency constraint and the domain constraint; and
[0143] a scheduling module configured to establish a mixed integer linear programming model according to above conditions, solving it to obtain a scheduling scheme for scheduling the object to be processed with a maximum total revenue, and schedule the object according to the scheduling scheme.
[0144] For convenience of description, when the above devices are described, it is made for various modules in terms of functions. Of course, when this disclosure is implemented, the functions of each module can be implemented in one or more pieces of software and/or hardware.
[0145] The device in the above embodiments is used to implement the corresponding scheduling method for the unrelated parallel machine in any of the above embodiments, and present beneficial effects of the corresponding method embodiments, which will not be described in detail here.
[0146] On a basis of the same concept, corresponding to the method of any of the above embodiments, an electronic device is also provided in this disclosure, which includes a memory, a processor and a computer program stored on the memory and operable on the processor, and the processor implements the scheduling method for the unrelated parallel machine described in any one of the above embodiments when executing the program.
[0147]
[0148] The processor 1010 can be implemented by a general-purpose CPU (Central Processing Unit), a microprocessor, an application specific integrated circuit (ASIC), or one or more integrated circuits, etc., and is used for executing relevant programs to realize technical schemes provided in the embodiments of this specification.
[0149] The memory 1020 can be implemented in a form of ROM (Read Only Memory), RAM (Random Access Memory), static storage device, dynamic storage device, or the like. The memory 1020 can store the operating system and other application programs. When the technical schemes provided in the embodiments of this specification is implemented by software or firmware, relevant program codes are stored in the memory 1020 and called and executed by the processor 1010.
[0150] The input/output interface 1030 is used to connect the input/output module to realize information input and output. The input/output module can be configured as a component in the device (not shown in the figure), or it can be externally connected to the device to provide corresponding functions. An input device can include a keyboard, a mouse, a touch screen, a microphone and various sensors, and an output device can include a display, a speaker, a vibrator and an indicator.
[0151] The communication interface 1040 is used to connect with a communication module (not shown in the figure) to realize communication interaction between the device and other devices. The communication module can communicate by wired means (such as USB, network cable, etc.) or by wireless means (such as mobile network, WIFI, Bluetooth, etc.).
[0152] The bus 1050 includes a path for transmitting information among various components of the device, such as the processor 1010, the memory 1020, the input/output interface 1030 and the communication interface 1040.
[0153] It should be noted that although the above device only shows the processor 1010, the memory 1020, the input/output interface 1030, the communication interface 1040 and the bus 1050, in the specific implementation process, the device may also include other components necessary for normal operation. In addition, it can be understood by those skilled in the art that the above-mentioned device may only contain the components necessary for implementing the embodiments of this specification, and need not contain all the components shown in the drawings.
[0154] Referring to
[0155] First Processing Module 950 may be configured to process first object to be processed 990 within a corresponding time window in response to determining that first variable 970 is 1, and take second variable 975 to be 0 in response to determining that first variable 970 is 0; and schedule first object to be processed 990 according to first variable 970 and second variable 975, wherein first variable 970 indicates whether first object to be processed 990 is scheduled to a time window corresponding to implementer 997, if first object to be processed 990 is scheduled to the time window corresponding to implementer 997, first variable 970 is 1, otherwise, first variable 970 is 0; and second variable 975 indicates a start time when first object to be processed 990 is allocated to the time window, and each object to be processed (e.g., first object to be processed 990 and second object to be processed 995) is processed at most once.
[0156] Second Processing Module 955 may be configured to process second object to be processed 995 before first object to be processed 990 in response to determining that a latest end time of first object to be processed 990 is less than a sum of an earliest start time of second object to be processed 995 and switching time of implementer 997; and process second object to be processed 995 after first object to be processed 990 in response to determining that the latest end time of first object to be processed 990 is greater than the sum of the earliest start time of second object to be processed 995 and the switching time of implementer 997.
[0157] Third Processing Module 960 may be configured to process first object to be processed 990 before second object to be processed 995 in response to determining that third variable 980 is 1; and process first object to be processed 990 after second object to be processed 995 in response to determining that fourth variable 985 is 1; wherein third variable 980 and fourth variable 985 respectively indicate scheduling orders of first object to be processed 990 and second object to be processed 995, and third variable 980 and fourth variable 985 satisfy the switching time constraint, consistency constraint and the domain constraint.
[0158] Scheduling Module 965 may be configured to establish a mixed integer linear programming model according to above conditions, solving the mixed linear programming model to obtain a scheduling scheme for scheduling first object to be processed 990 with a maximum total revenue, and schedule the object according to the scheduling scheme.
[0159] These program modules may be stored on mass storage device 920 of one or more computers devices, and may be executed by one or more processors, such as processor 915. Each of the operating modules may comprise elements of programming and data management software.
[0160] The variables of the present embodiment (e.g. first variable 970, second variable 975, third variable 980, and fourth variable 985) may be used separately or in combination in the system and method of the present disclosure. The variables may be stored, for example, without limitation, on system memory 940.
[0161] The components of the one or more computers may comprise, but are not limited to, one or more processors or processing units, such as processor 915, system memory 940, mass storage device 920, Input/Output Interface 930, display adapter 925, network adaptor 935, and a system bus that couples various system components. The one or more computers and implementer 997 may be implemented over a wired or wireless network connection at physically separate locations, implementing a fully distributed system. Additionally, implementer 997 may include the one or more computers such that implementer 997 and the one or more computers may be implemented in a same physical location. By way of example, without limitation, the one or more computers may be a personal computer, a portable computer, a smart device, a network computer, a peer device, or other common network node, and so on. Logical connections between one or more computers and implementer 997 may be made via network 945, such as a local area network (LAN) and/or a general wide area network (WAN).
[0162] Implementer 997 may be, for example, without limitation, a satellite configured to process first object to be processed 990, second object to be processed 995, etc. First object to be processed 990, second object to be processed 995, etc. may be objects to be observed via implementer 997. For example, without limitation, the objects to be processed may be geographical locations, vehicles, buildings, etc. Additionally, the objects to be processed may not be on the surface of the Earth, and may be, for example, without limitation, satellites, spacecraft, asteroids, etc. Additionally, implementer 997 and objects to be processed may be different depending on the environment. For example, without limitation, in a scenario of machining mechanical parts, the object to be processed may be a part to be machined, and the implementer may be a lathe. In a vehicle routing problem, the object to be processed can be a path of the vehicle, and the implementer can be the vehicle itself; and in a scenario of satellite scheduling, the object to be processed can be a task of the satellite, and the implementer can be the satellite itself.
[0163]
[0164] The apparatus may include additional components that perform each of the blocks of the algorithm in the aforementioned flowcharts of
[0165]
[0166] The processing system 1114 may be coupled to a transceiver 1110. The transceiver 1110 is coupled to one or more antennas 1120. The transceiver 1110 provides a means for communicating with various other apparatus over a transmission medium. The transceiver 1110 receives a signal from the one or more antennas 1120, extracts information from the received signal, and provides the extracted information to the processing system 1114, specifically the reception component 1004. In addition, the transceiver 1110 receives information from the processing system 1114, specifically the transmission component 1010, and based on the received information, generates a signal to be applied to the one or more antennas 1120. The processing system 1114 includes a processor 1104 coupled to a computer-readable medium/memory 1106. The processor 1104 is responsible for general processing, including the execution of software stored on the computer-readable medium/memory 1106. The software, when executed by the processor 1104, causes the processing system 1114 to perform the various functions described supra for any particular apparatus. The computer-readable medium/memory 1106 may also be used for storing data that is manipulated by the processor 1104 when executing software. The processing system 1114 further includes at least one of the components 1004, 1006, 1008, 1012, 1014, and 1016. The components may be software components running in the processor 1104, resident/stored in the computer readable medium/memory 1106, one or more hardware components coupled to the processor 1104, or some combination thereof.
[0167] In one configuration, the apparatus 1002 includes means for acquiring time node information of each implementer, means for accessing the time nodes on the implementer in sequence according to the time node information, updating an end time of an accessed time window in response to determining that the number of the accessed time windows is less than or equal to 3, with the updated end time not exceeding a current time node, and scheduling remaining objects to be processed, means for pre-scheduling the object to be processed in the accessed time window in response to determining that the object to be processed in the accessed time window can be successfully scheduled, and deleting time windows of the objects to be processed on all implementers in the accessed time windows, and means for pre-scheduling the object to be processed before the end time of the time window in time sequence in response to determining that the number of the accessed time windows is greater than 3, updating start time of time windows of the remaining objects to be processed in the accessed time windows after successfully pre-scheduling one object to be processed each time, and scheduling the remaining objects to be processed until a number of time windows of remaining unscheduled objects to be processed is less than or equal to 3. Additionally, apparatus 1002 includes means for processing a first object to be processed, via an implementer, within a corresponding time window in response to determining that a first variable is 1, and taking a second variable to be 0 in response to determining that the first variable is 0; and scheduling the first object to be processed according to the first variable and the second variable, wherein the first variable indicates whether the first object to be processed is scheduled to a time window corresponding to the implementer, if the first object to be processed is scheduled to the time window corresponding to the implementer, the first variable is 1, otherwise, the first variable is 0; and the second variable indicates a start time when the first object to be processed are allocated to the time window, and each object to be processed is processed at most once, means for processing a second object to be processed, via the implementer, before the first object to be processed in response to determining that a latest end time of the first object to be processed is less than a sum of an earliest start time of the second object to be processed and a switching time of the implementer; and processing the second object to be processed after the first object to be processed in response to determining that the latest end time of the first object to be processed is greater than the sum of the earliest start time of the second object to be processed and the switching time of the implementer, means for processing the first object to be processed before the second object to be processed, via the implementer, in response to determining that a third variable is 1; and processing the first object to be processed after the second object to be processed in response to determining that a fourth variable is 1; wherein the third variable and the fourth variable respectively indicate scheduling orders of the first object to be processed and the second object to be processed, and the third variable and the fourth variable satisfy a switching time constraint, a consistency constraint and a domain constraint, and means for establishing a mixed integer linear programming model according to above conditions via the implementer, solving the mixed integer linear programming model to obtain a scheduling scheme for scheduling an object to be processed with a maximum total revenue, and scheduling each object to be processed according to the scheduling scheme, thus obtaining an improved upper bound for a linear relaxation of the mixed integer linear programming model. The aforementioned means may be one or more of the aforementioned components of the apparatus 1002 and/or the processing system 1114 of the apparatus 1002 configured to perform the functions recited by the aforementioned means.
[0168] The electronic devices in the above embodiments are used to implement the corresponding scheduling method for the unrelated parallel machine in any of the above embodiments, and present beneficial effects of the corresponding method embodiments, which will not be described in detail here.
[0169] It should be understood by those of ordinary skill in the art that discussion of any of the above embodiments is only exemplary, and is not intended to imply that the scope of the disclosure (including the claims) is limited to these examples; under the idea of this disclosure, the technical features in the above embodiments or different embodiments can also be combined, and the steps can be realized in any order; and there are many other changes in different aspects of the embodiments of this disclosure as described above, which are not provided in details for brevity.
[0170] In addition, in order to simplify the description and discussion, and in order not to make the embodiments of the present disclosure difficult to understand, well-known power/ground connections with integrated circuit (IC) chips and other components may or may not be shown in the provided drawings. In addition, the devices can be shown in the form of block diagrams in order to avoid making the embodiments of the present disclosure difficult to understand, and this also takes into account the fact that the details about the implementation of these devices in block diagram are highly dependent on a platform on which the embodiments of the present disclosure will be implemented (i.e., these details should be completely within an understanding range of those skilled in the art). While specific details (e.g., circuits) have been set forth to describe exemplary embodiments of the present disclosure, it will be apparent to those skilled in the art that the embodiments of the present disclosure may be practiced without these specific details or with variations in these specific details. Therefore, these descriptions should be regarded as illustrative rather than restrictive.
[0171] Although the present disclosure has been described in conjunction with specific embodiments thereof, many alternatives, modifications and variations of these embodiments will be apparent to those of ordinary skill in the art based on the foregoing description.
[0172] The embodiments of the present disclosure are intended to cover all such alternatives, modifications and variations that fall within the broad scope of the append claims. Therefore, any omissions, modifications, equivalent substitutions, improvements, etc. made within the spirit and principles of the embodiments of this disclosure shall be encompassed within the protection scope of this disclosure.