[go: up one dir, main page]

CN110969308A - A heuristic resource-constrained project scheduling optimization method based on dynamic critical tasks - Google Patents

A heuristic resource-constrained project scheduling optimization method based on dynamic critical tasks Download PDF

Info

Publication number
CN110969308A
CN110969308A CN201911261526.4A CN201911261526A CN110969308A CN 110969308 A CN110969308 A CN 110969308A CN 201911261526 A CN201911261526 A CN 201911261526A CN 110969308 A CN110969308 A CN 110969308A
Authority
CN
China
Prior art keywords
task
time
resource
resources
rank
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
CN201911261526.4A
Other languages
Chinese (zh)
Inventor
李研彪
纪仁全
单晓杭
叶必卿
张利
计时鸣
谢毅
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Zhejiang University of Technology ZJUT
Original Assignee
Zhejiang University of Technology ZJUT
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Zhejiang University of Technology ZJUT filed Critical Zhejiang University of Technology ZJUT
Priority to CN201911261526.4A priority Critical patent/CN110969308A/en
Publication of CN110969308A publication Critical patent/CN110969308A/en
Withdrawn legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06312—Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06313—Resource planning in a project environment
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06316—Sequencing of tasks or work
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/04—Manufacturing
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
    • Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
    • Y02P90/30—Computing systems specially adapted for manufacturing

Landscapes

  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Engineering & Computer Science (AREA)
  • Economics (AREA)
  • Strategic Management (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Tourism & Hospitality (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Marketing (AREA)
  • General Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • Quality & Reliability (AREA)
  • Development Economics (AREA)
  • Game Theory and Decision Science (AREA)
  • Operations Research (AREA)
  • Educational Administration (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Biodiversity & Conservation Biology (AREA)
  • Manufacturing & Machinery (AREA)
  • Health & Medical Sciences (AREA)
  • General Health & Medical Sciences (AREA)
  • Primary Health Care (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

The invention discloses a heuristic resource-limited project scheduling optimization method based on dynamic key tasks, which comprises the following steps: s1, acquiring information required by scheduling optimization; s2, calculating the task ranking value rank; s3 initializing the system state; s4 extracting a key task j from the RT; s5 calculating the completion time f of task jj(ii) a S6 if
Figure DDA0002311727520000011
F is F ∪ { F ═ FjIs increased by fjThe remaining available amount of resources at the moment; s7 update [ fj‑dj,fj) The remaining available amount of resources in the time period; s8 at all
Figure DDA0002311727520000012
Deletion of tjIn UT
Figure DDA0002311727520000013
Is/are as follows
Figure DDA0002311727520000014
Moving to RT; s9 go to S10 if RT is null, otherwise go to S4; s10 outputs the schedule optimization scheme. The task priority adopted by the invention is dynamically changed, and the urgency degree of the current unscheduled task can be better reflected, so that a better scheduling scheme can be found, and the method can be used for online real-time scheduling optimization.

Description

Heuristic resource-limited project scheduling optimization method based on dynamic key tasks
Technical Field
The invention relates to the field of computer technology, information technology and system engineering, in particular to a resource-constrained project scheduling optimization method, and more particularly relates to a heuristic resource-constrained project scheduling optimization method based on dynamic key tasks.
Background
The Resource-Constrained Project scheduling problem RCPSP (Resource-Constrained Project scheduling Project) refers to how to scientifically and reasonably allocate resources and arrange the execution sequence of tasks to determine the start and completion time thereof under the constraint of satisfying the Resource and task timing relationship, so as to achieve the given objectives, such as: optimization of construction period, cost, etc. With the adoption of project-oriented organizational structures and management modes by more and more modern enterprises, the RCPSP is widely applied to enterprises in single-piece or small-batch production modes such as building engineering, software development, airplane and ship manufacturing and has a strong engineering application background.
The method for solving the RCPSP at the present stage mainly comprises the following steps: 1) the precise algorithm, such as: 0-1 integer programming and branch-and-bound; 2) heuristic algorithms, such as: heuristic algorithm, separation arc method and local search calculation based on priority rule; 3) intelligent algorithms, such as: genetic algorithm, particle swarm optimization algorithm, ant colony algorithm and the like. Although the accurate algorithm can obtain the optimal solution in theory, the calculation time is generally unacceptable and is generally only suitable for small-scale problems, the heuristic algorithm can quickly obtain the solution of the problem based on a certain heuristic rule but generally cannot ensure the quality of the solution, the intelligent algorithm is based on the calculation intelligence, the near-optimal solution or the satisfactory solution is found in reasonable time by adopting an improved heuristic rule and a search mode, and the efficiency generally depends on the design of the algorithm and the type of the problem.
Disclosure of Invention
In order to overcome the defects that an accurate algorithm cannot be suitable for large-scale problems and the task priority of the traditional heuristic scheduling method cannot dynamically reflect the emergency degree of the current unscheduled task and the like, the invention provides a heuristic resource-limited project scheduling optimization method based on dynamic key tasks, which improves the time efficiency and the resolution quality of solving and can be used for online real-time scheduling optimization of large-scale problems.
The technical scheme adopted by the invention for solving the technical problems is as follows: a heuristic resource-limited project scheduling optimization method based on dynamic key tasks comprises the following steps:
step 1: formalizing a resource-limited project scheduling problem and acquiring information required by scheduling optimization;
acquiring a project task set T ═ T0,t1,...,tJ,tJ+1}; wherein t isjIndicating task j, i.e. task numbered j, t0And tJ+1The method is a virtual task which is artificially increased, namely, the project construction period and the resource are not occupied, and J is the actual task quantity to be scheduled;
obtaining the time sequence relation between tasks, namely a parent task set PR of the task jjAnd a set of subtasks SCjTask j belongs to PR at its parent task j ∈jCannot be started until all the completion, J is 0,1, …, J +1, t0Without a parent task, i.e.
Figure BDA0002311727500000021
tJ+1Without subtasks, i.e.
Figure BDA0002311727500000022
Obtaining the available quantity R of the resource k at any timekK is 1, …, K is the number of resource types;
acquiring the time needed by the execution of the task j, namely the construction period djAnd the number r of occupied resources kj,k，rj,k≤Rk，j＝1,…,J，k＝1,…,K；
Step 2: calculating the rank value rank of the tasks;
for the end task J +1 with no subtasks:
rankJ+1＝0 (1)
the rank values rank of the other tasks are calculated using the following recursive formula:
Figure BDA0002311727500000023
and step 3: initializing a system state;
step 3.1: order completion time f of task 000, and F is the task completion time set0Lf }; wherein:
Figure BDA0002311727500000024
is the latest completion time of the project, the elements in F are arranged from small to large;
step 3.2: corresponding to the remaining available amount of each completion time resource in F:
Figure BDA0002311727500000025
Figure BDA0002311727500000026
step 3.3: order ready task set
Figure BDA0002311727500000027
Let the task set UT to be scheduled be t1,t2,…,tJ}; let the task set P (t) of the parent task to be scheduled not to complete scheduling yetj)＝PRj-{t0}，j＝1,…,J；
Step 3.4: in UT
Figure BDA0002311727500000028
Is/are as follows
Figure BDA0002311727500000029
Moving to RT;
wherein: f. ofjIndicating the time of completion of the task j,
Figure BDA00023117275000000210
representing the remaining available amount of resource k at time τ;
and 4, step 4: the critical task, i.e. the task with the largest sum of the task ready time and rank, is taken out of the RT, and is not set to tj；
The task ready time is calculated as follows:
Figure BDA00023117275000000211
and 5: calculating tjCompletion time of (d):
Figure BDA00023117275000000212
step 6: if f isjAbsent in F, then F-F ∪ { FjIs increased by fjRemaining available amount of resources at the time:
Figure BDA0002311727500000031
wherein: f. ofj″Is fjThe previous time of day;
and 7: update [ fj-dj,fj) Remaining available amount of resources in the time period:
Figure BDA0002311727500000033
Figure BDA0002311727500000034
and 8: in all of
Figure BDA0002311727500000035
Deletion of tj，
Figure BDA0002311727500000036
In UT
Figure BDA0002311727500000037
Is/are as follows
Figure BDA0002311727500000038
Moving to RT;
and step 9: if the RT is not empty, turning to the step 4, otherwise, turning to the step 10;
step 10: outputting optimized scheduling scheme, and project execution time
Figure BDA0002311727500000039
Further, t is calculated in the step 5jThe completion time comprises the following specific steps:
step 5.1: let tjIs its ready time, i.e. sj＝rtjLet flag value flag be 1;
step 5.2: finding rt or more in FjAnd form a set TF, i.e., TF ═ { F ∈ F | F ≧ rtj}；
Step 5.3: take the element with the smallest value from TF, do not set to fj′；
Step 5.4: if flag is 1 and fj′-sj≥djThen go to step 5.7; otherwise go to step 5.5;
step 5.5: if flag is equal to 0, let sj＝fj′，flag＝1；
Step 5.6: judgment of fj′Whether the residual available quantity of all resources at the moment satisfies tjIf the flag is not satisfied, the flag is made to be 0, and the step 5.3 is switched to;
step 5.7: let fj＝sj+djAnd the calculation is finished.
The invention has the beneficial effects that:
1. compared with the traditional heuristic scheduling method, the task priority adopted by the design of the invention can be continuously adjusted along with the progress of scheduling, and the urgency degree of the current unscheduled task can be better reflected, so that a better scheduling scheme is usually found.
2. Compared with the traditional intelligent calculation methods such as genetic algorithm, ant colony algorithm, particle swarm optimization algorithm and the like, the method has the advantages of simple algorithm and high efficiency, and can be used for online real-time scheduling optimization.
Drawings
Fig. 1 is a flowchart illustrating a heuristic resource-constrained project scheduling optimization method based on dynamic key tasks according to the present invention.
FIG. 2 is a timing diagram of tasks according to an embodiment of the present invention.
Detailed Description
The present invention will be described in further detail with reference to fig. 1 and 2 and examples, but the present invention is not limited to the examples.
A project consists of 20 tasks numbered from 0 to 19, the time sequence relationship among the tasks is shown in FIG. 2, wherein the task 0 and the task 19 are artificially increased virtual tasks, namely, the project period is not occupied, and the resources are not occupied, the time required for executing the tasks 1 to 18 and the quantity of occupied resources are shown in Table 1, the available quantity of the resource 1 at any time in the project is 12, and the available quantity of the resource 2 at any time is 13.
Task numbering Execution time Demand for resource 1 Demand for resource 2 Task numbering Execution time Demand for resource 1 Demand for resource 2
1 3 9 8 10 2 7 7
2 8 5 7 11 8 3 5
3 9 4 3 12 9 3 1
4 2 8 8 13 6 4 5
5 4 6 9 14 5 7 4
6 3 7 8 15 3 6 8
7 9 4 2 16 4 7 5
8 8 5 3 17 8 4 5
9 4 1 9 18 4 5 6
TABLE 1
For the above case, as shown in fig. 1, a heuristic resource-constrained project scheduling optimization method based on dynamic key tasks includes the following implementation steps:
executing the step 1: formalizing a resource-limited project scheduling problem and acquiring information required by scheduling optimization;
acquiring task set T ═ T of project0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18,t19Where task 0 and task 19, i.e. t0And t19Are virtual tasks, task 1 through task 18, i.e., t1,…,t18Is a task that actually needs to be scheduled;
obtaining the time sequence relation between tasks, namely a parent task set PR of the task jjAnd a set of subtasks SCj：
Figure BDA0002311727500000041
SC0＝{t1,t2,t3}；PR1＝{t0}，SC1＝{t4,t6,t14}；PR2＝{t0}，SC2＝{t8}；PR3＝{t0}，SC3＝{t4,t5,t6}；PR4＝{t1,t3}，SC4＝{t10,t11,t13}；PR5＝{t3}，SC5＝{t7,t12,t13}；PR6＝{t1,t3}，SC6＝{t10,t18}；PR7＝{t5}，SC7＝{t8}；PR8＝{t2,t7}，SC8＝{t9,t14,t15}；PR9＝{t8}，SC9＝{t11,t16}；PR10＝{t4,t6}，SC10＝{t12,t16}；PR11＝{t4,t9}，SC11＝{t18}；PR12＝{t5,t10}，SC12＝{t17}；PR13＝{t4,t5}，SC13＝{t15,t17}；PR14＝{t1,t8}，SC14＝{t17}；PR15＝{t8,t13}，SC15＝{t16,t18}；PR16＝{t9,t10,t15}，SC16＝{t19}；PR17＝{t12,t13,t14}，SC17＝{t19}；PR18＝{t6,t11,t15}，SC18＝{t19}；PR19＝{t16,t17,t18}，
Figure BDA0002311727500000042
Acquiring the available quantity R of the resource k in the project at any timek：R1＝12，R2＝13；
Get task j execution timeRequired time djAnd the number r of occupied resources kj,k：d1＝3，r1,1＝9，r1,2＝8；d2＝8，r2,1＝5，r2,2＝7；d3＝9，r3,1＝4，r3,2＝3；d4＝2，r4,1＝8，r4,2＝8；……；d18＝4，r18,1＝5，r18,2＝6。
And (3) executing the step 2: calculating the rank value rank of the tasks;
for the end task 19 without subtasks: rank19＝0；
The rank values rank of the other tasks are calculated as follows:
Figure BDA0002311727500000051
Figure BDA0002311727500000052
rank can be obtained by the same method16,…,rank1The results are shown in table 2:
rank1 rank2 rank3 rank4 rank5 rank6 rank7 rank8 rank9 rank10 rank11 rank12 rank13 rank14 rank15 rank16 rank17 rank18
25 32 46 21 37 22 33 24 16 19 12 17 14 13 7 4 8 4
TABLE 2
And (3) executing the step: initializing a system state;
step 3.1 is executed: let f0＝0，
Figure BDA0002311727500000053
Task completion time set F ═ F0,lf}＝{0,99}；
Step 3.2 is executed: the remaining available amount of resources corresponding to each completion time in F is:
Figure BDA0002311727500000054
Figure BDA0002311727500000055
step 3.3 is executed:
Figure BDA0002311727500000056
the same can be obtained:
Figure BDA0002311727500000057
P(t4)＝{t1,t3}，P(t5)＝{t3}，P(t6)＝{t1,t3}，P(t7)＝{t5}，P(t8)＝{t2,t7}，P(t9)＝{t8}，P(t10)＝{t4,t6}，P(t11)＝{t4,t9}，P(t12)＝{t5,t10}，P(t13)＝{t4,t5}，P(t14)＝{t1,t8}，P(t15)＝{t8,t13}，P(t16)＝{t9,t10,t15}，P(t17)＝{t12,t13,t14}，P(t18)＝{t6,t11,t15}；
Figure BDA0002311727500000058
UT＝{t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18}；
step 3.4 is executed: in UT
Figure BDA0002311727500000059
Task of (1), i.e. t1，t2And t3Moving to RT, RT ═ t1,t2,t3}，UT＝{t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18}。
And (4) executing: taking out a key task from the RT, namely the task with the largest sum of the task ready time and rank;
due to the fact that
Figure BDA0002311727500000068
Same principle, rt2+rank2＝32，rt3+rank346, so in task set RT ═ t1,t2,t3Task 3 is a key task, and task 3 is taken out, wherein RT is { t ═ t }1,t2}。
And 5, executing the step: calculating tjCompletion time of (d):
Figure BDA0002311727500000061
i.e. the completion time of calculation task 3:
and step 5.1 is executed: let start time of task 3:
Figure BDA0002311727500000062
let flag be 1;
and step 5.2 is executed: where F is ═ F0If is equal to rt, find {0,99}30, the composition set TF ═ { F ∈ F | F ≧ rt3＝0}＝{f0,lf}＝{0,99}；
And step 5.3 is executed: from TF ═ f0The element with the smallest value is taken from {0,99}, which is f0＝0；
And step 5.4 is executed: due to f0-s3＝0-0＝0＜d3Turning to step 5.5 when the result is 9;
and 5.5, executing: since flag is 1 at this time, go directly to step 5.6;
and step 5.6 is executed: due to the fact that
Figure BDA0002311727500000063
f0When 0, the remaining available amount of all resources meets the requirement of task 3, so the process directly goes to step 5.3;
and step 5.3 is executed: taking an element with the smallest value from TF { lf } {99}, wherein lf is 99;
and step 5.4 is executed: since flag is 1 and lf-s3＝99-0＝99＞d3Turning to step 5.7 when the result is 9;
step 5.7 is executed: f. of3＝s3+d3＝0+9＝9。
And 6, executing the step: if f isjAbsent in F, then F-F ∪ { FjIs increased by fjRemaining available amount of resources at the time:
Figure BDA0002311727500000064
wherein: f. ofj″Is fjThe previous time of day;
due to the fact that
Figure BDA0002311727500000066
F is F ∪ { F ═ F3}＝{f0,lf}∪f3＝{f0,f3If is {0,9,99}, and f is increased3Remaining available amount of resources at time 9:
Figure BDA0002311727500000067
Figure BDA0002311727500000071
and 7, executing the step: update [ fj-dj,fj) Remaining available amount of resources in the time period:
Figure BDA0002311727500000072
update [ f3-d3,f3) 1, [0,9) remaining available amount of resources in the time period:
Figure BDA0002311727500000073
Figure BDA0002311727500000074
and step 8 is executed: in all of
Figure BDA0002311727500000075
Deletion of tj，
Figure BDA0002311727500000076
In UT
Figure BDA0002311727500000077
Is/are as follows
Figure BDA0002311727500000078
Moving to RT;
due to SC3＝{t4,t5,t6Thus at P (t)4)，P(t5)，P(t6) Deletion of t3Then P (t)4)＝{t1}，
Figure BDA0002311727500000079
P(t6)＝{t1F. therefore, t in UT5Moving to RT, RT ═ t1,t2,t5}，
UT＝{t4,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18}。
And step 9 is executed: if the RT is not empty, turning to the step 4, otherwise, turning to the step 10;
since RT ═ t1,t2,t5If not, go to step 4.
And (4) executing: taking out a key task from the RT, namely the task with the largest sum of the task ready time and rank;
due to the fact that
Figure BDA00023117275000000710
rt1+rank1＝25，rt2+rank232, therefore, in the task set RT, t1,t2,t5In the method, the task 5 is a key task, and the task 5 is taken out.
And 5, executing the step: calculating tjCompletion time of (d):
Figure BDA00023117275000000711
i.e. the completion time of calculation task 5:
and step 5.1 is executed: let start time of task 5: s5＝rt5＝f39, let flag 1;
and step 5.2 is executed: where F is ═ F0,f3If is equal to rt, find out {0,9,99}39, the composition set TF ═ {9,99 };
and step 5.3 is executed: taking the element with the smallest value from TF {9,99}, wherein the element is 9;
and step 5.4 is executed: due to 9-s5＝0＜d54, go to step 5.5;
and 5.5, executing: since flag is 1 at this time, go directly to step 5.6;
and step 5.6 is executed: due to the fact that
Figure BDA0002311727500000081
At time 9, the remaining available amount of all resources meets the requirement of task 5, so the process directly goes to step 5.3;
and step 5.3 is executed: taking the element with the smallest value from TF {99}, wherein the element is 99;
and step 5.4 is executed: since flag is 1 and 99-s5＝90＞d5Go to step 5.7 as 4;
step 5.7 is executed: f. of5＝s5+d5＝9+4＝13。
And 6, executing the step: if f isjAbsent in F, then F-F ∪ { FjIs increased by fjRemaining available amount of resources at the time:
Figure BDA0002311727500000082
wherein: f. ofj″Is fjThe previous time of day;
due to the fact that
Figure BDA0002311727500000083
Then F ═ F0,f3,f5If is {0,9,13,99}, and f is increased5Remaining available amount of resources at time 13:
Figure BDA0002311727500000084
and 7, executing the step: update [ fj-dj,fj) Remaining available amount of resources in the time period:
Figure BDA0002311727500000085
update [ f5-d5,f5) Remaining available amount of resources in [9,13) time period：
Figure BDA0002311727500000086
Figure BDA0002311727500000087
And step 8 is executed: in all of
Figure BDA0002311727500000088
Deletion of tjIn UT
Figure BDA0002311727500000089
Is/are as follows
Figure BDA00023117275000000810
Moving to RT;
due to SC5＝{t7,t12,t13Thus at P (t)7)，P(t12)，P(t13) Deletion of t5Then, then
Figure BDA00023117275000000811
P(t12)＝{t10}，P(t13)＝{t4H, t in UT7Moving to RT, RT ═ t1,t2,t7}，
UT＝{t4,t6,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18}。
And step 9 is executed: if the RT is not empty, turning to the step 4, otherwise, turning to the step 10;
since RT ═ t1,t2,t7If not, go to step 4.
And (4) executing: taking out a key task from the RT, namely the task with the largest sum of the task ready time and rank;
due to the fact that
Figure BDA00023117275000000812
rt1+rank1＝25，rt2+rank232, therefore, in the task set RT, t1,t2,t7In the method, the task 7 is a key task, and the task 7 is taken out.
And 5, executing the step: calculating tjCompletion time of (d):
Figure BDA0002311727500000091
i.e. the completion time of the calculation task 7:
and step 5.1 is executed: let start time s of task 77＝rt7＝f513, let flag 1;
and step 5.2 is executed: where F is ═ F0,f3,f5If is equal to or greater than rt, find {0,9,13,99}513, the composition set TF ═ {13,99 };
and step 5.3 is executed: taking the element with the smallest value from TF {13,99}, wherein the element is 13;
and step 5.4 is executed: due to 13-s7＝0＜d7Turning to step 5.5 when the result is 9;
and 5.5, executing: since flag is 1 at this time, go directly to step 5.6;
and step 5.6 is executed: due to the fact that
Figure BDA0002311727500000092
The remaining available amount of all resources at time 13 meets the requirements of task 7, so go directly to step 5.3;
and step 5.3 is executed: taking the element with the smallest value from TF {99}, wherein the element is 99;
and step 5.4 is executed: since flag is 1 and 99-s7＝86＞d7Turning to step 5.7 when the result is 9;
step 5.7 is executed: f. of7＝s7+d7＝13+9＝22。
And 6, executing the step: if f isjAbsent in F, then F-F ∪ { FjIs increased by fjRemaining available amount of resources at the time:
Figure BDA0002311727500000093
wherein: f. ofj″Is fjThe previous time of day;
due to the fact that
Figure BDA0002311727500000098
Then F ═ F0,f3,f5,f7And if is {0,9,13,22,99}, and f is increased7Remaining available amount of resources at time 22:
Figure BDA0002311727500000094
and 7, executing the step: update [ fj-dj,fj) Remaining available amount of resources in the time period:
Figure BDA0002311727500000095
update [ ff-d7,f7) Remaining available amount of resources in period [13, 22):
Figure BDA0002311727500000096
Figure BDA0002311727500000097
and step 8 is executed: in all of
Figure BDA0002311727500000101
Deletion of tjIn UT
Figure BDA0002311727500000102
Is/are as follows
Figure BDA0002311727500000103
Moving to RT;
due to SC7＝{t8At P (t)8) Deletion of t7Then P (t)8)＝{t2Due to absence in UT
Figure BDA0002311727500000104
If the task of (1), both UT and RT are unchanged.
And step 9 is executed: if the RT is not empty, turning to the step 4, otherwise, turning to the step 10;
since RT ═ t1,t2If not, go to step 4.
And (4) executing: taking out a key task from the RT, namely the task with the largest sum of the task ready time and rank;
due to rt1+rank1＝f0+rank1＝25，rt2+rank2＝f0+rank232, therefore, in the task set RT, t1,t2And taking out the task 2, wherein the task 2 is a key task.
And 5, executing the step: calculating tjCompletion time of (d):
Figure BDA0002311727500000105
i.e. the completion time of computing task 2:
and step 5.1 is executed: let start time s of task 22＝rt2＝f00,1 is given as flag;
and step 5.2 is executed: where F is ═ F0,f3,f5,f7If is equal to or greater than rt, find {0,9,13,22,99}20, the composition set TF ═ {0,9,13,22,99 };
and step 5.3 is executed: taking an element with the smallest value from TF {0,9,13,22,99}, wherein the element is 0;
and step 5.4 is executed: due to 0-s2＝0＜d2Go to step 5.5, No. 8;
and 5.5, executing: since flag is 1 at this time, go directly to step 5.6;
and step 5.6 is executed: due to the fact that
Figure BDA0002311727500000106
At time 0, the remaining available amount of all resources meets the requirement of task 2, so the process directly goes to step 5.3;
and step 5.3 is executed: taking an element with the smallest value from TF {9,13,22,99}, wherein the element is 9;
and step 5.4 is executed: since flag is 1 and 9-s2＝9＞d2Go to step 5.7 as 8;
step 5.7 is executed: f. of2＝s2+d2＝0+8＝8。
And 6, executing the step: if f isjAbsent in F, then F-F ∪ { FjIs increased by fjRemaining available amount of resources at the time:
Figure BDA0002311727500000107
wherein: f. ofj″Is fjThe previous time of day;
due to the fact that
Figure BDA0002311727500000111
Then
F＝F∪f1＝{f0,f1,f3,f5,f7And if is {0,8,9,13,22,99}, and f is increased1Remaining available amount of resources at time 8:
Figure BDA0002311727500000112
and 7, executing the step: update [ fj-dj,fj) Remaining available amount of resources in the time period:
Figure BDA0002311727500000113
update [ f2-d2,f2) ═ 0,8) remaining available amount of resources in the time period:
Figure BDA0002311727500000114
Figure BDA0002311727500000115
and step 8 is executed: in all of
Figure BDA0002311727500000116
Deletion of tjIn UT
Figure BDA0002311727500000117
Is/are as follows
Figure BDA0002311727500000118
Moving to RT;
due to SC2＝{t8At P (t)8) Deletion of t2Then, then
Figure BDA0002311727500000119
Let t in UT8Moving to RT, RT ═ t1,t8}，UT＝{t4,t6,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18}。
And step 9 is executed: if the RT is not empty, turning to the step 4, otherwise, turning to the step 10;
since RT ═ t1,t8If not, go to step 4.
……
So that the steps 4 to 9 are continuously and repeatedly executed until
Figure BDA00023117275000001110
Go to step 10.
Executing the step 10: outputting optimized scheduling scheme, and project execution time
Figure BDA00023117275000001111
The project execution time is
Figure BDA00023117275000001112
The optimized scheduling scheme is shown in table 3.
Figure BDA00023117275000001113
Figure BDA0002311727500000121
TABLE 3
The above embodiments are only preferred embodiments of the present invention, and are not intended to limit the technical solutions of the present invention, so long as the technical solutions can be realized on the basis of the above embodiments without creative efforts, which should be considered to fall within the protection scope of the patent of the present invention.

Claims (2)

1.一种基于动态关键任务的启发式资源受限项目调度优化方法，其特征在于：包括以下步骤：1. a heuristic resource-constrained project scheduling optimization method based on dynamic key tasks, is characterized in that: comprise the following steps: 步骤1：形式化资源受限项目调度问题，获取调度优化所需的信息；Step 1: Formalize the resource-constrained project scheduling problem and obtain the information required for scheduling optimization; 获取项目任务集T＝{t0,t1,…,tJ,tJ+1}；其中tj表示任务j，即编号为j的任务，t0与tJ+1是人为增加的虚拟任务，即不占用项目工期也不占用资源，J是需要调度的实际任务数量；Obtain the project task set T={t 0 , t 1 ,...,t J ,t J+1 }; where t j represents task j, that is, the task numbered j, and t 0 and t J+1 are artificially increased virtual Task, which does not occupy the project duration or resources, J is the actual number of tasks that need to be scheduled; 获取任务间的时序关系，即任务j的父任务集PRj和子任务集SCj，任务j在其父任务j-∈PRj全部完工之前不能开始执行，j＝0,1,…,J+1，t0没有父任务即
Figure FDA0002311727490000011
tJ+1没有子任务即
Figure FDA0002311727490000012
Obtain the temporal relationship between tasks, that is, task j's parent task set PR j and child task set SC j , task j cannot start executing until its parent task j - ∈ PR j is all completed, j=0,1,...,J+ 1, t 0 has no parent task i.e.
Figure FDA0002311727490000011
t J+1 has no subtasks i.e.
Figure FDA0002311727490000012
 获取资源k在任意时刻的可使用量Rk，k＝1,…,K，K是资源种类数量；Obtain the usable amount R k of resource k at any time, k=1,...,K, where K is the number of resource types; 获取任务j执行时需要的时间即工期dj和占用资源k的数量rj,k，rj,k≤Rk，j＝1,…,J，k＝1,…,K；Obtain the time required for the execution of task j, namely the construction period d j and the number of occupied resources k r j,k , r j,k ≤R k , j=1,...,J, k=1,...,K; 步骤2：计算任务的排序值rank；Step 2: Calculate the ranking value rank of the task; 对于没有子任务的结束任务J+1：For end task J+1 without subtasks: rankJ+1＝0 (1)rank J+1 = 0 (1) 其它任务的排序值rank采用如下递归公式进行计算：The ranking value rank of other tasks is calculated using the following recursive formula:
Figure FDA0002311727490000013
Figure FDA0002311727490000013
 步骤3：系统状态初始化；Step 3: System state initialization; 步骤3.1：令任务0的完成时间f0＝0，任务完成时间集F＝{f0,lf}；其中：
Figure FDA0002311727490000014
是项目的最晚完成时间，F中的元素从小到大排列；Step 3.1: Let the completion time of task 0 f 0 =0, and the task completion time set F={f 0 ,lf}; where:
Figure FDA0002311727490000014
is the latest completion time of the project, and the elements in F are arranged from small to large; 步骤3.2：对应于F中各完成时间资源的剩余可用量：
Figure FDA0002311727490000015
k＝1,…,K；Step 3.2: Corresponding to the remaining available amount of each completion time resource in F:
Figure FDA0002311727490000015
k=1,...,K; 步骤3.3：令就绪任务集
Figure FDA0002311727490000016
令要调度的任务集UT＝{t1,t2,…,tJ}；令要调度任务的父任务中还没有完成调度的任务集P(tj)＝PRj-{t0}，j＝1,…,J；Step 3.3: Make the set of ready tasks
Figure FDA0002311727490000016
Let the task set to be scheduled UT={t 1 ,t 2 ,...,t J }; let the task set P(t j )=PR j -{t 0 } that has not been scheduled in the parent task of the task to be scheduled, j=1,...,J; 步骤3.4：把UT中
Figure FDA0002311727490000017
的
Figure FDA0002311727490000018
移到RT中；Step 3.4: Put the UT in
Figure FDA0002311727490000017
of
Figure FDA0002311727490000018
Move to RT; 其中：fj表示任务j的完成时间，
Figure FDA0002311727490000019
表示τ时刻资源k的剩余可用量；where: f j represents the completion time of task j,
Figure FDA0002311727490000019
Represents the remaining available amount of resource k at time τ; 步骤4：从RT中取出关键任务，即任务就绪时间与rank之和最大的任务，不妨设为tj；Step 4: Take out the key task from RT, that is, the task with the largest sum of task ready time and rank, which may be set as t j ; 所述任务就绪时间计算如下：
Figure FDA0002311727490000021
The task ready time is calculated as follows:
Figure FDA0002311727490000021
 步骤5：计算tj的完成时间：Step 5: Calculate the completion time of t j :
Figure FDA0002311727490000022
Figure FDA0002311727490000022
 步骤6：如果fj在F中不存在，那么F＝F∪{fj}，增加fj时刻资源的剩余可用量：Step 6: If f j does not exist in F, then F=F∪{f j }, increase the remaining available amount of resources at time f j :
Figure FDA0002311727490000023
其中：fj″是fj的前一个时刻；
Figure FDA0002311727490000023
Where: f j" is the previous moment of f j ; 步骤7：更新[fj-dj,fj)时段内资源的剩余可用量：
Figure FDA0002311727490000024
Figure FDA0002311727490000025
Step 7: Update the remaining available amount of resources in the [f j -d j ,f j ) period:
Figure FDA0002311727490000024
Figure FDA0002311727490000025
 步骤8：在所有
Figure FDA0002311727490000026
中删除tj，
Figure FDA0002311727490000027
把UT中
Figure FDA0002311727490000028
的
Figure FDA0002311727490000029
移到RT中；Step 8: After all
Figure FDA0002311727490000026
delete t j from ,
Figure FDA0002311727490000027
put UT in
Figure FDA0002311727490000028
of
Figure FDA0002311727490000029
Move to RT; 步骤9：如果RT不为空则转到步骤4，否则转到步骤10；Step 9: If RT is not empty then go to step 4, otherwise go to step 10; 步骤10：输出优化的调度方案，及项目执行时间
Figure FDA00023117274900000210
Step 10: Output the optimized scheduling plan and project execution time
Figure FDA00023117274900000210
 2.根据权利要求1所述的一种基于动态关键任务的启发式资源受限项目调度优化方法，其特征在于：所述步骤5中计算tj的完成时间包括如下具体步骤：2. a kind of heuristic resource-constrained project scheduling optimization method based on dynamic key tasks according to claim 1, is characterized in that: in described step 5, the completion time of calculating t j comprises following concrete steps: 步骤5.1：令tj的开始时间为其就绪时间，即sj＝rtj，令标记值flag＝1；Step 5.1: Let the start time of t j be its ready time, that is, s j =rt j , and let the flag value flag=1; 步骤5.2：在F中找出大于等于rtj的元素，并组成集合TF，即TF＝{f∈F|f≥rtj}；Step 5.2: Find elements greater than or equal to rt j in F, and form a set TF, that is, TF = {f∈F|f≥rt j }; 步骤5.3：从TF中取出一个值最小的元素，不妨设为fj′；Step 5.3: Take an element with the smallest value from TF, which may be set as f j′ ; 步骤5.4：如果flag＝1并且fj′-sj≥dj，那么转到步骤5.7；否则转到步骤5.5；Step 5.4: If flag=1 and f j′ -s j ≥ d j , then go to step 5.7; otherwise, go to step 5.5; 步骤5.5：如果flag＝0，那么令sj＝fj′，flag＝1；Step 5.5: If flag=0, then let s j =f j' , flag=1; 步骤5.6：判断fj′时刻所有资源的剩余可用量是否满足tj的需求，如果不满足则令flag＝0，转到步骤5.3；Step 5.6: Determine whether the remaining available amount of all resources at time f j' meets the requirements of t j , if not, set flag=0, and go to step 5.3; 步骤5.7：令fj＝sj+dj，计算结束。Step 5.7: Let f j =s j +d j , the calculation ends.
CN201911261526.4A 2019-12-10 2019-12-10 A heuristic resource-constrained project scheduling optimization method based on dynamic critical tasks Withdrawn CN110969308A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201911261526.4A CN110969308A (en) 2019-12-10 2019-12-10 A heuristic resource-constrained project scheduling optimization method based on dynamic critical tasks

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201911261526.4A CN110969308A (en) 2019-12-10 2019-12-10 A heuristic resource-constrained project scheduling optimization method based on dynamic critical tasks

Publications (1)

Publication Number Publication Date
CN110969308A true CN110969308A (en) 2020-04-07

Family

ID=70033629

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201911261526.4A Withdrawn CN110969308A (en) 2019-12-10 2019-12-10 A heuristic resource-constrained project scheduling optimization method based on dynamic critical tasks

Country Status (1)

Country Link
CN (1) CN110969308A (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111882145A (en) * 2020-06-10 2020-11-03 中国人民解放军海军航空大学 Airplane service support serial scheduling method considering resource transfer time

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5671361A (en) * 1995-09-28 1997-09-23 University Of Central Florida Priority rule search technique for resource constrained project scheduling
US9135581B1 (en) * 2011-08-31 2015-09-15 Amazon Technologies, Inc. Resource constrained task scheduling
CN108681783A (en) * 2018-04-04 2018-10-19 河海大学 A kind of scheduling of reservoir real-time multi-target random optimization and methods of risk assessment
CN109190857A (en) * 2018-10-30 2019-01-11 武汉大学 A kind of optimization algorithm based on multiple target Resource-constrained Project Scheduling Problem model

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5671361A (en) * 1995-09-28 1997-09-23 University Of Central Florida Priority rule search technique for resource constrained project scheduling
US9135581B1 (en) * 2011-08-31 2015-09-15 Amazon Technologies, Inc. Resource constrained task scheduling
CN108681783A (en) * 2018-04-04 2018-10-19 河海大学 A kind of scheduling of reservoir real-time multi-target random optimization and methods of risk assessment
CN109190857A (en) * 2018-10-30 2019-01-11 武汉大学 A kind of optimization algorithm based on multiple target Resource-constrained Project Scheduling Problem model

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
刘金定等: "基于拓扑排序资源约束下多项目调度优化算法", 《西华大学学报(自然科学版)》 *
尚志等: "基于最早开始时间的项目进度关键链搜索算法", 《中国制造业信息化》 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111882145A (en) * 2020-06-10 2020-11-03 中国人民解放军海军航空大学 Airplane service support serial scheduling method considering resource transfer time
CN111882145B (en) * 2020-06-10 2022-03-11 中国人民解放军海军航空大学 A Serial Scheduling Method for Aircraft Maintenance Support Considering Resource Transfer Time

Similar Documents

Publication Publication Date Title
Xiao et al. A cooperative coevolution hyper-heuristic framework for workflow scheduling problem
CN105959401B (en) A kind of manufacturing service supply-demand mode and dynamic dispatching method based on super-network
CN103729246B (en) Method and device for dispatching tasks
CN107656799B (en) A Workflow Scheduling Method Considering Communication and Computing Costs in a Multi-Cloud Environment
CN108985709A (en) Workflow management method towards more satellite data centers collaboration Remote Sensing Products production
CN107168770B (en) Low-energy-consumption cloud data center workflow scheduling and resource supply method
CN105068863A (en) Cost-driven scheduling method for workflow with deadline constraints in cloudy environment
CN105260818A (en) Online optimized scheduling method for workflow groups with deadline constraint in mixed cloud environment
CN113918288B (en) Task processing method, device, server and storage medium
CN102508639A (en) Distributed parallel processing method based on satellite remote sensing data characteristics
CN106934539B (en) A Workflow Scheduling Method with Term and Cost Constraints
CN106371924A (en) Task scheduling method for maximizing MapReduce cluster energy consumption
CN115983429A (en) BIM model-based construction strategy optimization method, system, terminal and medium
CN110969308A (en) A heuristic resource-constrained project scheduling optimization method based on dynamic critical tasks
CN102253837A (en) Object tree-based software framework designing technology
CN109886574B (en) Multi-robot task allocation method based on improved threshold method
CN113010296B (en) Method and system for task analysis and resource allocation based on formal model
CN119902852A (en) Container task scheduling method, system and storage medium based on reinforcement learning technology
Alidaee et al. A unified view of parallel machine scheduling with interdependent processing rates
CN113961439A (en) DAG task WCRT calculation method based on SMT method
CN111290868B (en) Task processing method, device and system and flow engine
CN111061552A (en) Heuristic Cloud Workflow Scheduling Optimization Method Based on Dynamic Critical Task Prioritization
CN117519927A (en) A hybrid workflow scheduling method, system and medium in a cloud computing environment
CN116402193A (en) Multi-procedure flow optimization method and system for wind power generation engineering construction
CN116993027B (en) An improved joint dispatching optimization method for water projects

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
WW01 Invention patent application withdrawn after publication

Application publication date: 20200407

WW01 Invention patent application withdrawn after publication