WO2023051505A1 - 一种任务求解方法及其装置 - Google Patents

一种任务求解方法及其装置 Download PDF

Info

Publication number
WO2023051505A1
WO2023051505A1 PCT/CN2022/121620 CN2022121620W WO2023051505A1 WO 2023051505 A1 WO2023051505 A1 WO 2023051505A1 CN 2022121620 W CN2022121620 W CN 2022121620W WO 2023051505 A1 WO2023051505 A1 WO 2023051505A1
Authority
WO
WIPO (PCT)
Prior art keywords
linear programming
solution
task
constraints
importance
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.)
Ceased
Application number
PCT/CN2022/121620
Other languages
English (en)
French (fr)
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.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
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 Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Priority to EP22874890.1A priority Critical patent/EP4394595A4/en
Publication of WO2023051505A1 publication Critical patent/WO2023051505A1/zh
Priority to US18/619,068 priority patent/US20240242137A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
    • G06F17/12—Simultaneous equations, e.g. systems of linear equations
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
    • G06F9/5038—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration
    • 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
    • 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
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2209/00—Indexing scheme relating to G06F9/00
    • G06F2209/50—Indexing scheme relating to G06F9/50
    • G06F2209/5017—Task decomposition

Definitions

  • the scheduling problem is one of the most common problems in large-scale manufacturing, logistics, production and other links.
  • scheduling always has different meanings.
  • logistics scheduling mainly refers to the logistics company's reasonable arrangement and scheduling of vehicles and personnel according to the weight, whereabouts, specifications, and urgency of the goods to be delivered during the logistics process; while scheduling in the production environment is
  • the sequencing of tasks and the matching between tasks and machines are completed in several tasks (jobs);
  • scheduling of workers/flight attendants in large manufacturing plants/airports (timetabling) is also a kind of scheduling problem, because the goal of this type of problem is also to complete the optimal match in different time periods according to the work characteristics of workers/flight attendants and scenarios. Therefore, the core is sorting and optimal allocation, not limited to whether the tasks are people or goods.
  • the goal of scheduling problems is to obtain the order corresponding to the minimum total man-hour (makespan) under the premise of a given number of
  • linear programming linear programming, LP
  • the linear programming model may include an objective function and constraint conditions, wherein the objective function refers to a function designed according to the objective to be optimized and the variables affecting the objective.
  • the goal of the entire production scheduling is usually to find a best processing plan under the condition of satisfying all resource constraints, so that the satisfaction rate of the demand is the highest, and the overall cost is the smallest (for example, the cost can include But not limited to processing cost, inventory cost, transshipment cost), at this time, the objective function may be a function representing the maximization of satisfaction rate and the minimization of cost.
  • the constraints refer to other constraints to be satisfied in the process of solving the objective function.
  • the present application provides a task solving method, the method comprising:
  • the terminal device may transmit the first linear programming task as a model to be solved to the server, and then the server may acquire the first linear programming task.
  • the terminal device may use the first linear programming task as prior information used to solve the model to be solved, that is, transmit at least one historical model including the first linear programming task to the server, and then the server may obtain at least one history model including a first linear programming task;
  • the solution time required to solve the linear programming task is very long, so some constraints in the linear programming task can be selected first, and the solution is based on the selected partial constraints, and the solution
  • the result (the state of the solution variable in the selected partial constraint) is assigned to the linear programming task, which is equivalent to using the solution result as the initial value of the linear programming task and solving the linear programming task.
  • the solution result of the selected partial constraint is the same as the linear programming task
  • the solution results after the task are basically the same (or described as relatively close, the solution results here are basically the same can be understood as the parameter values of the solution variables in the same constraints are basically the same)
  • the number of iterations required to solve the linear programming task is less , that is, it can improve the solution speed of the linear programming task.
  • the importance is used as a basis for selecting partial constraints from multiple first programming constraints, where the importance may indicate a degree of contribution to reducing the solution time of the first linear programming task.
  • the so-called indicating the degree of contribution to reducing the solution time of the first linear programming task can be understood as, when constructing the submodel of the model to be solved (that is, selecting a part of the constraints in the model to be solved to construct the submodel ), when the result of solving the submodel is used as the initial value of the model to be solved, the submodel includes the degree of contribution of the first linear programming task to reducing the solution time for solving the model to be solved.
  • the importance can be used as a sampling probability to sample a plurality of first planning constraints to obtain a subtask (second planning task), and the planning constraint in this subtask is to reduce the solution of the first linear programming task Therefore, the solution result obtained after solving the second planning task is basically the same as the solution result obtained after solving the second planning task (or described as relatively close, the solution result here is basically the same can be It is understood that the parameter values of the solution variables in the same constraint are basically the same).
  • the importance can be obtained based on prior information, where the prior information can be one or more models of the same type as the model to be solved (the first linear programming task), the so-called same type, can be understood
  • the types and quantities of constraints included in the linear programming task are consistent or basically the same, that is to say, the type and quantity of constraints included in the first linear programming task and one or more models in the prior information are consistent or basically the same.
  • each linear programming task in the prior information can be directly solved to obtain the solution time of each linear programming task (if the linear programming task has been solved, the solution time can also be obtained directly) , and then extract and solve sub-models for one or more linear programming models in the prior information, and initialize the linear programming model based on the solution results, and then solve the linear programming model to obtain another solution time, by Comparing the solution time of directly solving each linear programming task with the solution time of the linear programming task initialized based on the submodel solution results, we can know the contribution of the constraints in the submodel to reduce the solution time of the linear programming task.
  • each constraint of the model to be solved can be given a probability (the probability can be the quantification of the above-mentioned importance), and based on the probability, the model to be solved is sampled to construct a sub-model, and based on the comparison directly
  • the solution time for solving each linear programming task, and the solution time for the linear programming task after initialization based on the sub-model solution results are used to update the probability and iterate a certain number of times to obtain the exact description constraints for reducing the linear programming task. Importance information of time is resolved (how the importance is updated will be described in an alternate embodiment).
  • the first solution result may include a parameter value (or parameter state) of at least one solution variable in a subset of multiple first planning constraints;
  • An embodiment of the present application provides a method for solving a task, the method comprising: acquiring a first linear programming task, the first linear programming task including multiple first programming constraints; The importance of a first planning constraint, the importance represents the contribution of the first planning constraint to reducing the solution time of the first linear programming task; Sampling to obtain the subsets of the plurality of first planning constraints obtained, wherein the importance is used to determine the sampling probability of the first planning constraints; constructing the second subset according to the plurality of first planning constraints Two linear programming tasks: using the first solution result as an initial value of the first linear programming task, and solving the initialized first linear programming task to obtain a second solution result.
  • the key constraints in the first linear programming task are selected to construct a sub-model (second linear programming task), and then the solution of the sub-model is used for the first linear programming task to speed up the solution process.
  • the first linear programming task is sampled based on the importance, since the importance indicates the degree of contribution of the first planning constraint to reducing the solution time of the first linear programming task, so that the sampled The solution of the submodel is close to the optimal solution, thus speeding up the solution process of the first linear programming task.
  • the first solution time for solving the second linear programming task and the second solution time for solving the initialized first linear programming task may be obtained, the first solution time and the The sum of the third solution time can be used as the solution time of the linear programming task initialized based on the sub-model solution results, and the first linear programming task is solved to obtain the third linear programming task for solving the first linear programming task.
  • Solution time wherein, the third solution time can be considered as the solution time for directly solving the first linear programming task, according to the sum of the first solution time and the third solution time, relative to the first solution time
  • the importance of each first planning constraint may be updated, wherein the updated importance is positively correlated with the reduction degree.
  • the time required for the process of obtaining the second linear programming task by sampling can also be used as part of the solution time of the linear programming task after initialization based on the solution result of the sub-model, that is, the multiple first linear programming tasks can be obtained.
  • Planning a sampling time for sampling with constraints, and updating each of the first solving time according to the sum of the first solving time, the third solving time and the sampling time, relative to the reduction degree of the first solving time The importance of planning constraints.
  • the using the first solution result as the initial value of the first linear programming task includes:
  • a new constraint (such as a second planning constraint) may be added, and the second planning constraint may be obtained, and the second planning constraint includes slack variables and the An upper bound of a slack variable, adding the second programming constraint to the first linear programming task to obtain an updated first linear programming task, and solving the updated first linear programming task.
  • it can be to set a reasonable bound (value range) for the new variable (slack variable) involved in the newly added constraint according to its actual meaning, and modify the initial state value of these variables, and change the state to its set bound , so that the initial solution is feasible for the newly added constraints, thereby speeding up the solution of linear programming.
  • the application can pre-set the variable upper bound and initial state for the newly added slack variable, thereby accelerating the continuous solution.
  • the embodiment of the present application also provides a system, wherein the system may include a terminal device and a server, wherein the terminal device may send the model to be solved (the first linear programming task) and prior information including multiple historical models to the server,
  • the server can calculate the importance of convergence based on prior information including multiple historical models, and sample the first linear programming task according to the importance, and execute the steps from step 301 to step 303 in the above embodiment to obtain the second
  • the solution result is obtained, and the second solution result is sent back to the terminal device.
  • the terminal device can send the model to be solved and the prior information including multiple historical models (including the first linear programming task) to the server, and the server can calculate the important parameters of convergence based on the prior information including multiple historical models.
  • the server can calculate the important parameters of convergence based on the prior information including multiple historical models.
  • the present application provides a task solving device, the device comprising:
  • a sampling module configured to sample the plurality of first planning constraints according to the importance, so as to obtain a subset of the obtained plurality of first planning constraints, wherein the importance is used to determine the first The sampling probability of a planning constraint;
  • a solving module configured to solve the second linear programming task to obtain a first solution result
  • the first solution result is used as an initial value of the first linear programming task, and the initialized first linear programming task is solved to obtain a second solution result.
  • both the first linear programming task and the second linear programming task include planning objectives.
  • the acquisition module is also used to:
  • the solving module is further configured to solve the first linear programming task, and obtain a third solving time for solving the first linear programming task;
  • the device also includes:
  • the acquisition module is also used to:
  • the importance updating module is specifically used for:
  • the importance of each first planning constraint is updated according to the sum of the first solution time, the third solution time, and the sampling time relative to the degree of reduction of the first solution time.
  • the acquisition module is also used to:
  • the sampling module is also used for:
  • the second linear programming task includes M solution variables, and the first solution result includes parameter values of each solution variable;
  • the solving module is specifically used for:
  • the acquisition module is also used to:
  • a second programming constraint is obtained, and the second programming constraint includes a slack variable and an upper bound of the slack variable;
  • the embodiment of the present application provides a device, including a memory, a processor, and a bus system, wherein the memory is used to store programs, and the processor is used to execute the programs in the memory, so as to perform the above-mentioned first aspect and first Aspect any optional method.
  • the embodiment of the present invention also provides a system, the system includes at least one processor, at least one memory, and at least one communication interface; the processor, memory, and communication interface are connected through a communication bus and complete mutual communication;
  • the memory is used to store the application program codes for executing the above solution, and the execution is controlled by the processor.
  • the processor is configured to execute the application program code stored in the memory to obtain a task scheduling result; wherein the code stored in the memory can execute a task solving method provided above.
  • the communication interface is used for communicating with other devices or communication networks, so as to send the task solution results to the devices or communication networks.
  • the embodiment of the present application provides a computer-readable storage medium, where a computer program is stored in the computer-readable storage medium, and when it is run on a computer, the computer executes the above-mentioned first aspect and any one thereof. optional method.
  • the embodiment of the present application provides a computer-readable storage medium, the computer storage medium stores one or more instructions, and when the instructions are executed by one or more computers, the one or more A computer implementing the second aspect above and any optional system therefor.
  • the embodiment of the present application provides a computer program, which, when running on a computer, causes the computer to execute the above-mentioned first aspect and any optional method thereof.
  • the present application provides a chip system, which includes a processor, configured to support a terminal device or a server to implement the functions involved in the above aspect, for example, send or process the data involved in the above method; or ,information.
  • the chip system further includes a memory, and the memory is used for saving necessary program instructions and data of the terminal device or the server.
  • the system-on-a-chip may consist of chips, or may include chips and other discrete devices.
  • the key constraints in the first linear programming task are selected to construct a sub-model (second linear programming task), and then the solution of the sub-model is used for the first linear programming task to speed up the solution process.
  • the first linear programming task is sampled based on the importance, since the importance indicates the degree of contribution of the first planning constraint to reducing the solution time of the first linear programming task, so that the sampled The solution of the submodel is close to the optimal solution, thus speeding up the solution process of the first linear programming task.
  • FIG. 1 provides a schematic diagram of an application architecture according to an embodiment of the present application
  • FIG. 2 is a schematic structural diagram of a server provided by an embodiment of the present application.
  • FIG. 3 is a schematic flow chart of a task solving method provided in an embodiment of the present application.
  • FIG. 6 is a schematic structural diagram of a task solving device provided in this embodiment.
  • FIG. 7 is a schematic structural diagram of a terminal device provided in an embodiment of the present application.
  • FIG. 8 is a schematic structural diagram of a server provided by an embodiment of the present application.
  • the embodiments of the present application can be applied to solving linear programming optimization problems in various scenarios (such as supply chain, cloud computing, scheduling, storage optimization, etc.), to accelerate the efficiency of linear programming solvers in solving these problems.
  • users can build models to be solved according to their own business scenarios. When solving, they can pass some models of similar problems in history to the server, and the server can call the solver to quickly output the optimal solution of the user input model. According to this solution, users can use the functions provided by the platform to generate data reports or process it by themselves to get the desired results.
  • Server 200 can also include one or more power supplies 222, one or more wired or wireless network interfaces 250, one or more input and output interfaces 258; or, one or more operating systems 241, such as Windows ServerTM, Mac OS XTM, UnixTM, LinuxTM, FreeBSDTM, etc.
  • operating systems 241 such as Windows ServerTM, Mac OS XTM, UnixTM, LinuxTM, FreeBSDTM, etc.
  • the central processing unit 22 is configured to execute the task solving method described in the embodiment of the present application.
  • task solving method provided in the embodiment of the present application may also be deployed as a solver on an end-side terminal device, which is not limited here.
  • the model to be solved in the embodiment of the present application can be used to solve the scheduling problem.
  • Scheduling is one of the most common problems in large-scale manufacturing/logistics/production, and scheduling always has different meanings in different scenarios.
  • logistics scheduling mainly refers to the reasonable arrangement and scheduling of vehicles and personnel by logistics companies according to the weight, whereabouts, specifications, and urgency of the goods to be shipped during the logistics process.
  • the scheduling in the production environment is to complete the sequencing of tasks and the matching between tasks and production equipment in several tasks (jobs) according to the capacity and production requirements of different machines in different production lines. That is, multiple tasks are assigned to the production equipment in each production line.
  • n workpieces are processed on m machines, each workpiece has a specific processing technology, and the processing order of each workpiece and the time spent in each process are given , to arrange the processing order of the workpieces on each machine so that a certain index is optimal.
  • every artifact executes on every machine.
  • this type of scheduling problem requires that each task must be executed to each stage in turn, and does not involve the matching of tasks and stages, but mainly determines the execution order of tasks. Prevent the overall completion time from being too long due to the long waiting time in the middle.
  • Resources can refer to virtual computing resources, such as threads, processes, or data streams; they can also refer to hardware resources, such as processors, network connections, or expansion cards.
  • the program that does the scheduling work is called a scheduler. Schedulers are usually implemented so that all computing resources are kept busy (in load balancing), allowing multiple users to efficiently share system resources simultaneously, or to achieve a specified quality of service.
  • linear programming linear programming, LP
  • simplex method is currently the most widely used algorithm, and it is also a type of algorithm that is optimized by various linear programming solvers.
  • the algorithm For the simplex algorithm, usually, the algorithm first selects an initial feasible base solution, then checks whether the solution has reached the optimal solution, and then performs LU decomposition on the base matrix to calculate the inverse of the base matrix; It will be done once, and the rest of the iterations will use the incremental method to update the update of the L matrix and the U matrix. Then, the algorithm will select the basic variable and the basic variable according to the heuristic rules to update the basic variable. This loop is executed continuously until the optimal solution is found, or the problem state is found to be abnormal, and the entire algorithm exits.
  • Standard solution means that the solver performs a complete solution without any a priori, and will go through the steps of pre-solve, solve, and post-processing respectively.
  • the standard process is to add a pre-solve module and post-processing before and after the Simplex algorithm. module.
  • the pre-solver module will simplify the model.
  • the degree of simplification is also different.
  • the model size number of variables, number of constraints
  • the post-processing module maps the solution of the simple model generated by the pre-solver back to the original problem, and finally obtains the solution of the original model.
  • Continuous solution means that the model has been solved once to obtain the optimal solution, and then the model is partially modified, such as adding some variable constraints or modifying the upper and lower bounds of existing variables, and solving again. This process of re-solving based on the last optimal solution is called continuous solving.
  • the existing standard solution process described above does not use any prior knowledge to construct an initial feasible basis, so the constructed initial feasible basis is relatively simple, and the number of iterations required for the simplex algorithm iteration starting from the simple feasible basis is too much, and the time too long.
  • the adjustment of the initial variable state is too straightforward during the continuous solution, so that it takes a long time to find the initial feasible basic solution during the continuous solution.
  • the task solving method provided in the embodiment of the present application can construct an initial feasible basis based on prior knowledge, which can reduce the solution time.
  • Linear Programming It is an important branch of operations research with earlier research, faster development, wider application and more mature methods. It is a mathematical method to assist people in scientific management. Mathematical theories and methods for studying the extremum problems of linear objective functions under linear constraints.
  • Constraints are constraints in mathematical programming problems, that is, numerical requirements for decision variables.
  • Basic Solution Basic Solution, find a basis in the coefficient matrix of the constraint equation system, set the non-basic variables of this basis to zero, and then solve the m-element linear equation system to obtain a unique solution. This solution is called linear programming. Basic solution.
  • Basic feasible solution Basic Feasible Solution, the abbreviation of basic feasible solution, is the basic concept of linear programming.
  • the basic solution that satisfies the non-negative condition is called the basic feasible solution.
  • Simplex the simplex method is one of the most commonly used and effective algorithms for solving linear programming problems.
  • the basic idea of the simplex method is: first find a vertex in the feasible region, and judge whether it is optimal according to certain rules; if not, switch to another vertex adjacent to it, and make the objective function value better; continue until an optimal solution is found.
  • Fig. 3 is a task solving method provided by the embodiment of the present application, the method includes:
  • the execution subject of step 301 may be a server, for example, the terminal device may transmit the first linear programming task as a model to be solved to the server, and then the server may obtain the first linear programming task.
  • the terminal device may use the first linear programming task as prior information used to solve the model to be solved, that is, transmit at least one historical model including the first linear programming task to the server, and then the server may obtain At least one history model including the first linear programming task.
  • a linear programming model may include an objective function and constraint conditions, wherein the objective function refers to a function designed according to an objective to be optimized and variables affecting the objective.
  • the objective function refers to a function designed according to an objective to be optimized and variables affecting the objective.
  • the goal of the entire production scheduling is usually to find a best processing plan under the condition of satisfying all resource constraints, so that the satisfaction rate of the demand is the highest, and the overall cost is the smallest (for example, the cost can include But not limited to processing cost, inventory cost, transshipment cost), at this time, the objective function may be a function representing the maximization of satisfaction rate and the minimization of cost.
  • the constraints refer to other constraints to be satisfied in the process of solving the objective function.
  • the first linear programming task is used to allocate scheduling resources for at least one task to be scheduled
  • the first planning constraint is a constraint satisfied by scheduling resources
  • the scheduling resources are production lines, production equipment or Manufacturer.
  • the task to be scheduled may be the product to be produced; in the scenario of personnel scheduling, the task to be scheduled may be the person to be produced, etc., which is not limited in this embodiment.
  • each of the multiple schedulable resource groups can be a production line.
  • each of the multiple schedulable resource groups can be a A production line of mobile phone components, such as battery production line, shell production line, chip production line, etc.
  • each schedulable resource group can include multiple schedulable resources, and each of the multiple schedulable resources can be The scheduling resource is the production equipment in the production line.
  • the battery production line may include multiple battery production equipment
  • the casing production line may include multiple casing production equipment, which are not limited here.
  • each schedulable resource group in multiple schedulable resource groups can be a time period, for example, in the scenario of personnel scheduling, each schedulable resource group in multiple schedulable resource groups can be One day, for example, can be Monday, Tuesday, Wednesday, or a certain day in some months, etc.
  • each schedulable resource group can include multiple schedulable resources, and each schedulable resource in the multiple schedulable resources is A sub-time period in a time period, for example, a certain day may include multiple hours, multiple minutes or other multiple sub-time periods, which are not limited here.
  • the first planning constraints may include solution variables and constraints that each solution variable needs to satisfy.
  • the first linear programming task can be used as a model to be solved.
  • the importance of each first programming constraint may be acquired first, and the importance indicates the degree of contribution of the first planning constraint to reducing the solution time of the first linear programming task.
  • the solution time required to solve the linear programming task is very long, so some constraints in the linear programming task can be selected first, and the solution is based on the selected partial constraints, and the solution
  • the result (the state of the solution variable in the selected partial constraint) is assigned to the linear programming task, which is equivalent to using the solution result as the initial value of the linear programming task and solving the linear programming task.
  • the solution result of the selected partial constraint is the same as the linear programming task
  • the solution results after the task are basically the same (or described as relatively close, the solution results here are basically the same can be understood as the parameter values of the solution variables in the same constraints are basically the same)
  • the number of iterations required to solve the linear programming task is less , that is, it can improve the solution speed of the linear programming task.
  • the importance is used as a basis for selecting partial constraints from multiple first programming constraints, where the importance may indicate the degree of contribution to reducing the solution time of the first linear programming task.
  • the so-called indicating the degree of contribution to reducing the solution time of the first linear programming task can be understood as, when constructing the submodel of the model to be solved (that is, selecting a part of the constraints in the model to be solved to construct the submodel ), when the result of solving the submodel is used as the initial value of the model to be solved, the submodel includes the degree of contribution of the first linear programming task to reducing the solution time for solving the model to be solved.
  • the importance can be used as a sampling probability to sample a plurality of first planning constraints to obtain a subtask (second planning task), and the planning constraint in this subtask is to reduce the solution of the first linear programming task Therefore, the solution result obtained after solving the second planning task is basically the same as the solution result obtained after solving the second planning task (or described as relatively close, the solution result here is basically the same can be It is understood that the parameter values of the solution variables in the same constraint are basically the same).
  • the importance can be obtained based on prior information, where the prior information can be one or more models of the same type as the model to be solved (the first linear programming task), the so-called same type, can be understood
  • the types and quantities of constraints included in the linear programming task are consistent or basically the same, that is to say, the type and quantity of constraints included in the first linear programming task and one or more models in the prior information are consistent or basically the same.
  • each linear programming task in the prior information can be directly solved to obtain the solution time of each linear programming task (if the linear programming task has been solved, the solution time can also be obtained directly) , and then extract and solve sub-models for one or more linear programming models in the prior information, and initialize the linear programming model based on the solution results, and then solve the linear programming model to obtain another solution time, by Comparing the solution time of directly solving each linear programming task with the solution time of the linear programming task initialized based on the submodel solution results, we can know the contribution of the constraints in the submodel to reduce the solution time of the linear programming task.
  • each constraint of the model to be solved can be given a probability (the probability can be the quantification of the above-mentioned importance), and based on the probability, the model to be solved is sampled to construct a sub-model, and Based on the comparison of the solution time of directly solving each linear programming task, and the solution time of the linear programming task after initializing the solution results based on the sub-model, to update the probability, and iterate a certain number of times, it can be used to accurately describe the constraints.
  • the importance information of the solution time of the linear programming task (the way of updating the importance will be described in an alternative embodiment).
  • Each planning constraint in the sub-model (such as the second linear programming task in the embodiment of the present application) obtained based on the above-mentioned importance sampling contributes a lot to reducing the solution time of the linear programming task. Therefore, based on the second linear programming task The time of the solution process of the first linear programming model after initialization of the solution result can be greatly shortened.
  • the first linear programming model in the embodiment of the present application may be the prior information used when calculating the importance of each first programming constraint.
  • the multiple first programming obtained in step 302 The importance of each first planning constraint in the constraints may be the importance of initialization, or the importance of the iterative process (not yet converged to meet the requirements).
  • the prior information used when calculating the importance of each first programming constraint may include multiple models, the first linear programming task may be one of the multiple models, and the first linear programming task may be obtained from multiple models randomly selected from.
  • N historically homogeneous models P can be obtained, such as the same type of optimization problems at different time points in the past.
  • ⁇ is the step size
  • g( ) is the probability update function
  • the corresponding importance of each first linear programming task in the first linear programming task can be obtained.
  • the second linear programming task may include Part of the first planning constraint.
  • the first linear programming model is the model to be solved or the prior information used to update the importance
  • the importance of convergence can be used as the sampling probability of each constraint
  • multiple first programming The constraints are sampled to obtain the second linear programming task, and the contribution of each planning constraint in the submodel (such as the second linear programming task in the embodiment of the present application) obtained based on the above importance sampling to reduce the solution time of the linear programming task Therefore, the time of the solution process of the first linear programming model initialized based on the solution result of the second linear programming task can be greatly shortened.
  • the second linear programming task includes M solution variables
  • the first solution result may include parameter values of each solution variable, where the parameter value here may be the value of the optimal solution or Solve for the state of the variable.
  • the parameter values of each solution variable in the first solution result may be used as the M solution values in the first linear programming task
  • the parameter value of the variable that is, the parameter values of the solution variables in the first solution result are assigned to the first linear programming task, and the initial values of the first programming constraints in the first linear programming task except the planning constraints included in the second linear programming task can be given by Solver specified, not limited here.
  • the solver can read the first solution result into the first linear programming task, and then assign the initial state of the solution variable v i in the first linear programming task to s i , and set all initialized Solve the above-mentioned first linear programming task to obtain the second solution result.
  • the first linear programming model may be the model to be solved
  • the second solution result may be the solution result of the model to be solved. After the server obtains the second solution result, it may return the second solution result to the to the terminal device.
  • a new constraint (such as a second programming constraint) may be added, and the second programming constraint may be obtained, and the second programming constraint includes the target solution variable and the slack variable, adding the second programming constraint to the first linear programming task to obtain an updated first linear programming task, and solving the updated first linear programming task. That is, you can set a reasonable bound (value range) for the new variables involved in the newly added constraints according to their actual meaning, and modify the initial state values of these variables, and change the state to the bound set in step 1, so that the initial The solution is feasible for the newly added constraints, thereby speeding up the solution of the linear program.
  • a reasonable bound value range
  • the application can pre-set the variable upper bound and initial state for the newly added slack variable, thereby accelerating the continuous solution.
  • the first linear programming model can be the prior information used to update the importance.
  • the solution time of each linear programming task can be directly solved based on the comparison, and based on The solution time of the linear programming task after the submodel solution result is initialized is used to update the probability, and a certain number of iterations can be used to accurately describe the importance of constraints for reducing the solution time of the linear programming task.
  • the first solution time for solving the second linear programming task and the second solution time for solving the initialized first linear programming task may be obtained, the first solution time and the The sum of the third solution time can be used as the solution time of the linear programming task initialized based on the sub-model solution results, and the first linear programming task is solved to obtain the third linear programming task for solving the first linear programming task.
  • Solution time wherein, the third solution time can be considered as the solution time for directly solving the first linear programming task, according to the sum of the first solution time and the third solution time, relative to the first solution time
  • the importance of each first planning constraint may be updated, wherein the updated importance is positively correlated with the reduction degree.
  • the time required for the process of obtaining the second linear programming task by sampling can also be used as part of the solution time of the linear programming task after initialization based on the solution result of the sub-model, that is, the multiple first linear programming tasks can be obtained.
  • Planning a sampling time for sampling with constraints, and updating each of the first solving time according to the sum of the first solving time, the third solving time and the sampling time, relative to the reduction degree of the first solving time The importance of planning constraints.
  • the time spent constructing a submodel is denoted as T a .
  • the linear programming solver to solve this sub-model (including c j1 ,...,c jK , a total of K types of constraints).
  • the optimal solution S of the sub-model obtained by solving the solution is recorded as T b .
  • the solution of the sub-model is brought into the original model P i as the initial solution, and P i is solved again.
  • the time spent in this step is T c .
  • ⁇ can be a preset hyperparameter.
  • updating the importance of each first planning constraint can be the importance of
  • the importance can be updated based on other prior information or the above iterative process is performed on the first linear programming model multiple times, so as to obtain the converged importance.
  • the server can solve the model to be solved based on the importance after convergence.
  • the programming constraints in the target linear programming task can be sampled based on the importance after convergence to obtain a sub-model, and the sub-model is solved, and then the solution result is used as the target
  • the initial value of the linear programming task, and then solve the target linear programming task to obtain the final solution result, and the server can feed back the final solution result obtained above to the terminal device.
  • the third linear programming task may be obtained, and the third linear programming task includes the multiple second programming constraints, the multiple second programming constraints and the multiple The constraint type of the first planning constraint is the same;
  • the third solution result is used as an initial value of the third linear programming task, and the initialized third linear programming task is solved to obtain a fourth solution result.
  • Figure 5 shows a production scheduling example, assuming that the customer places an order for 2,000 PCs, 1,000 hosts, and 800 notebooks. Then there are two factories that can process these three types of products (up to 1000 products per day). To process a PC, you must first have a host, and assembling it into a PC can only be done in the first factory.
  • the figure has shown an optimal production scheduling plan, that is, on the first day, each of the two factories will process 1,000 hosts, and the hosts from the second factory will be shipped to the first factory; on the second day, the hosts will be shipped to the first factory
  • the hosts processed on the first day were assembled into PCs, and then 1,000 hosts were processed in the second factory; on the third day, the hosts shipped from the second factory on the first day were used in the first factory to assemble 1,000 PCs.
  • 800 notebooks were processed in the second factory. In this way, all requirements can be met, and the total cost is the lowest.
  • the essence of multi-factory scheduling is an integer programming problem. However, due to the high complexity of solving integer programming, it is difficult to find the optimal solution within a specified time for such a large-scale model. Therefore, the usual practice is to relax the problem into a linear program, and then use some approximate methods to adjust the real number solution obtained by solving the linear program into an integer solution.
  • constraints including inventory constraints, capacity constraints, pairing constraints, special control constraints, SR constraints, order demand delay constraints, forecast demand delay constraints, and maximum substitution constraints.
  • T c T a +T b +T c .
  • T j T a +T b +T c .
  • the daily processing volume is either equal to 0, or greater than or equal to a certain constant C. Since this constraint cannot be considered when building a linear programming model, the continuous solution method can be used here to add a constraint in the following style to the model that has been solved: x i +s j ⁇ C; where x i is obtained by the previous standard solution A variable greater than 0, s j is the newly added slack variable. At the same time, s j is added to the objective function. At this time, solve the constrained model again, and the effect achieved is that xi can be greater than or equal to C as much as possible.
  • Table 1 shows the improvement effect of the solution of the embodiment of the present application. Compared with the direct solution, the efficiency of the solution method of the embodiment of the present application is improved by about 20% on average.
  • An embodiment of the present application provides a method for solving a task, the method comprising: acquiring a first linear programming task, the first linear programming task including multiple first programming constraints; The importance of a first planning constraint, the importance represents the contribution of the first planning constraint to reducing the solution time of the first linear programming task; Sampling to obtain the subsets of the plurality of first planning constraints obtained, wherein the importance is used to determine the sampling probability of the first planning constraints; constructing the second subset according to the plurality of first planning constraints Two linear programming tasks: using the first solution result as an initial value of the first linear programming task, and solving the initialized first linear programming task to obtain a second solution result.
  • the key constraints in the first linear programming task are selected to construct a sub-model (second linear programming task), and then the solution of the sub-model is used for the first linear programming task to speed up the solution process.
  • the first linear programming task is sampled based on the importance, since the importance indicates the degree of contribution of the first planning constraint to reducing the solution time of the first linear programming task, so that the sampled The solution of the submodel is close to the optimal solution, thus speeding up the solution process of the first linear programming task.
  • the embodiment of the present application also provides a system, wherein the system may include a terminal device and a server, wherein the terminal device may send the model to be solved (the first linear programming task) and prior information including multiple historical models to the server,
  • the server can calculate the importance of convergence based on prior information including multiple historical models, and sample the first linear programming task according to the importance, and execute the steps from step 301 to step 303 in the above embodiment to obtain the second
  • the solution result is obtained, and the second solution result is sent back to the terminal device.
  • the terminal device can send the model to be solved and the prior information including multiple historical models (including the first linear programming task) to the server, and the server can calculate the important parameters of convergence based on the prior information including multiple historical models.
  • the server can calculate the important parameters of convergence based on the prior information including multiple historical models.
  • FIG. 6 is a schematic structural diagram of a task solving device provided in an embodiment of the present application.
  • the device 600 may include:
  • An obtaining module 601 configured to obtain a first linear programming task, where the first linear programming task includes a plurality of first planning constraints;
  • a sampling module 602 configured to sample the plurality of first planning constraints according to the importance, so as to obtain a subset of the obtained plurality of first planning constraints, wherein the importance is used to determine The sampling probability of the first planning constraint;
  • sampling module 602 for the specific description of the sampling module 602, reference may be made to the description of step 303 and step 304 in the above-mentioned embodiment, and details are not repeated here.
  • a solving module 603, configured to solve the second linear programming task to obtain a first solution result
  • both the first linear programming task and the second linear programming task include planning objectives.
  • the acquisition module is also used to:
  • the solving module is further configured to solve the first linear programming task, and obtain a third solving time for solving the first linear programming task;
  • the device also includes:
  • an importance updating module configured to update the importance of each of the first planning constraints according to the sum of the first solution time and the third solution time, relative to the degree of reduction of the first solution time, Wherein, the updated importance is positively correlated with the reduction degree.
  • the acquisition module is also used to:
  • the importance updating module is specifically used for:
  • the importance of each first planning constraint is updated according to the sum of the first solution time, the third solution time, and the sampling time relative to the degree of reduction of the first solution time.
  • the acquisition module is also used to:
  • the third linear programming task includes the plurality of second programming constraints, and the plurality of second programming constraints are of the same constraint type as the plurality of first programming constraints;
  • the sampling module is also used for:
  • the solving module is also used for:
  • the second linear programming task includes M solution variables, and the first solution result includes parameter values of each solution variable;
  • the solving module is specifically used for:
  • the first linear programming task is used to allocate scheduling resources for at least one task to be scheduled
  • the first planning constraint is a constraint satisfied by scheduling resources
  • the scheduling resources are production lines, production equipment or Manufacturer.
  • the acquisition module is also used to:
  • a second programming constraint is obtained, and the second programming constraint includes a target solution variable and a slack variable;
  • the solving module is further configured to add the second programming constraint to the first linear programming task to obtain an updated first linear programming task, and solve the updated first linear programming task .
  • the task solving apparatus described in the embodiment corresponding to FIG. 6 may be deployed on the terminal device 700 to realize the function of solving the task in the embodiment corresponding to FIG. 6 .
  • the terminal device 700 includes: a receiver 701, a transmitter 702, a processor 703, and a memory 704 (the number of processors 703 in the terminal device 700 may be one or more, and one processor is taken as an example in FIG. 7 ) , where the processor 703 may include an application processor 7031 and a communication processor 7032 .
  • the receiver 701 , the transmitter 702 , the processor 703 and the memory 704 may be connected through a bus or in other ways.
  • the memory 704 may include read-only memory and random-access memory, and provides instructions and data to the processor 703 .
  • a part of the memory 704 may also include a non-volatile random access memory (non-volatile random access memory, NVRAM).
  • NVRAM non-volatile random access memory
  • the memory 704 stores processors and operating instructions, executable modules or data structures, or their subsets, or their extended sets, wherein the operating instructions may include various operating instructions for implementing various operations.
  • the processor 703 controls the operation of the terminal device.
  • various components of the terminal device are coupled together through a bus system, where the bus system may include a power bus, a control bus, and a status signal bus in addition to a data bus.
  • the various buses are referred to as bus systems in the figures.
  • the methods disclosed in the foregoing embodiments of the present application may be applied to the processor 703 or implemented by the processor 703 .
  • the processor 703 may be an integrated circuit chip, which has a signal processing capability. In the implementation process, each step of the above method may be completed by an integrated logic circuit of hardware in the processor 703 or instructions in the form of software.
  • the above-mentioned processor 703 can be a general-purpose processor, a digital signal processor (digital signal processing, DSP), a microprocessor or a microcontroller, and can further include an application-specific integrated circuit (application specific integrated circuit, ASIC), field programmable Field-programmable gate array (FPGA) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components.
  • DSP digital signal processing
  • ASIC application specific integrated circuit
  • FPGA field programmable Field-programmable gate array
  • the processor 703 may implement or execute various methods, steps, and logic block diagrams disclosed in the embodiments of the present application.
  • a general-purpose processor may be a microprocessor, or the processor may be any conventional processor, or the like.
  • the steps of the method disclosed in connection with the embodiments of the present application may be directly implemented by a hardware decoding processor, or implemented by a combination of hardware and software modules in the decoding processor.
  • the software module can be located in a mature storage medium in the field such as random access memory, flash memory, read-only memory, programmable read-only memory or electrically erasable programmable memory, register.
  • the storage medium is located in the memory 704, and the processor 703 reads the information in the memory 704, and completes the steps related to the terminal device in the above method in combination with its hardware.
  • the receiver 701 can be used to receive input digital or character information, and generate signal input related to related settings and function control of the terminal device.
  • the transmitter 702 can be used to output digital or character information through the first interface; the transmitter 702 can also be used to send instructions to the disk group through the first interface to modify the data in the disk group; the transmitter 702 can also include display devices such as display screens .
  • the processor 703 is configured to execute the steps performed by the terminal device in the foregoing embodiments.
  • FIG. 8 There are relatively large differences due to different performances, and may include one or more central processing units (central processing units, CPU) 88 (for example, one or more processors) and memory 832, one or more storage application programs 842 or data 844 storage medium 830 (for example, one or more mass storage devices).
  • the memory 832 and the storage medium 830 may be temporary storage or persistent storage.
  • the program stored in the storage medium 830 may include one or more modules (not shown in the figure), and each module may include a series of instruction operations on the server.
  • the central processing unit 88 may be configured to communicate with the storage medium 830 , and execute a series of instruction operations in the storage medium 830 on the server 800 .
  • the server 800 can also include one or more power supplies 826, one or more wired or wireless network interfaces 850, one or more input and output interfaces 858; or, one or more operating systems 841, such as Windows ServerTM, Mac OS XTM, UnixTM, LinuxTM, FreeBSDTM, etc.
  • the central processing unit 88 is configured to execute steps related to the task solving method of the above embodiment.
  • the embodiment of the present application also provides a computer program product, which, when running on a computer, causes the computer to perform the steps performed by the aforementioned terminal device, or causes the computer to perform the steps performed by the aforementioned server.
  • An embodiment of the present application also provides a computer-readable storage medium, the computer-readable storage medium stores a program for signal processing, and when it is run on a computer, the computer executes the steps performed by the aforementioned terminal device , or make the computer perform the steps performed by the aforementioned server.
  • the terminal device, server, or terminal device provided in the embodiment of the present application may specifically be a chip.
  • the chip includes: a processing unit and a communication unit.
  • the processing unit may be, for example, a processor, and the communication unit may be, for example, an input/output interface, a pipe pins or circuits etc.
  • the processing unit may execute the computer-executed instructions stored in the storage unit, so that the chip in the terminal device executes the data processing method described in the above embodiment, or the chip in the server executes the data processing method described in the above embodiment.
  • the storage unit is a storage unit in the chip, such as a register, a cache, etc.
  • the storage unit may also be a storage unit located outside the chip in the wireless access device, such as only Read-only memory (ROM) or other types of static storage devices that can store static information and instructions, random access memory (random access memory, RAM), etc.
  • ROM Read-only memory
  • RAM random access memory
  • FIG. 9 is a schematic structural diagram of a chip provided by the embodiment of the present application.
  • the chip can be represented as a neural network processor NPU 900, and the NPU 900 is mounted to the main CPU (Host CPU) as a coprocessor. CPU), the tasks are assigned by the Host CPU.
  • the core part of the NPU is the operation circuit 903, and the operation circuit 903 is controlled by the controller 904 to extract matrix data in the memory and perform multiplication operations.
  • the operation circuit 903 includes multiple processing units (Process Engine, PE).
  • arithmetic circuit 903 is a two-dimensional systolic array.
  • the arithmetic circuit 903 may also be a one-dimensional systolic array or other electronic circuits capable of performing mathematical operations such as multiplication and addition.
  • arithmetic circuit 903 is a general-purpose matrix processor.
  • the operation circuit fetches the data corresponding to the matrix B from the weight memory 902, and caches it in each PE in the operation circuit.
  • the operation circuit takes the data of matrix A from the input memory 901 and performs matrix operation with matrix B, and the obtained partial results or final results of the matrix are stored in the accumulator (accumulator) 908 .
  • the unified memory 906 is used to store input data and output data.
  • the weight data directly accesses the controller (Direct Memory Access Controller, DMAC) 905 through the storage unit, and the DMAC is transferred to the weight storage 902.
  • the input data is also transferred to the unified memory 906 through the DMAC.
  • DMAC Direct Memory Access Controller
  • the BIU is the Bus Interface Unit, that is, the bus interface unit 910, which is used for the interaction between the AXI bus and the DMAC and the instruction fetch buffer (Instruction Fetch Buffer, IFB) 909.
  • IFB Instruction Fetch Buffer
  • the bus interface unit 910 (Bus Interface Unit, BIU for short) is used for the instruction fetch memory 909 to obtain instructions from the external memory, and for the storage unit access controller 905 to obtain the original data of the input matrix A or the weight matrix B from the external memory.
  • the DMAC is mainly used to move the input data in the external memory DDR to the unified memory 906 , to move the weight data to the weight memory 902 , or to move the input data to the input memory 901 .
  • the vector calculation unit 907 includes a plurality of calculation processing units, and further processes the output of the calculation circuit 903, such as vector multiplication, vector addition, exponential operation, logarithmic operation, size comparison, etc., if necessary. It is mainly used for non-convolutional/fully connected layer network calculations in neural networks, such as Batch Normalization (batch normalization), pixel-level summation, and upsampling of feature planes.
  • vector computation unit 907 can store the vector of the processed output to unified memory 906 .
  • the vector calculation unit 907 can apply a linear function; or, a nonlinear function to the output of the operation circuit 903, such as performing linear interpolation on the feature plane extracted by the convolution layer, and then for example, a vector of accumulated values to generate an activation value.
  • the vector computation unit 907 generates normalized values, pixel-level summed values, or both.
  • the vector of processed outputs can be used as an activation input to arithmetic circuitry 903, eg, for use in subsequent layers in a neural network.
  • An instruction fetch buffer (instruction fetch buffer) 909 connected to the controller 904 is used to store instructions used by the controller 904;
  • the unified memory 906, the input memory 901, the weight memory 902 and the fetch memory 909 are all On-Chip memories. External memory is private to the NPU hardware architecture.
  • the processor mentioned above can be a general-purpose central processing unit, microprocessor, ASIC, or one or more integrated circuits for controlling the execution of the above-mentioned programs.
  • the device embodiments described above are only illustrative, and the units described as separate components may or may not be physically separated, and the components shown as units may or may not be A physical unit can be located in one place, or it can be distributed to multiple network units. Part or all of the modules can be selected according to actual needs to realize the purpose of the solution of this embodiment.
  • the connection relationship between the modules indicates that they have communication connections, which can be specifically implemented as one or more communication buses or signal lines.
  • the essence of the technical solution of this application or the part that contributes to the prior art can be embodied in the form of a software product, and the computer software product is stored in a readable storage medium, such as a floppy disk of a computer , U disk, mobile hard disk, ROM, RAM, magnetic disk or optical disk, etc., including several instructions to make a computer device (which can be a personal computer, a server, or a network device, etc.) execute the method described in each embodiment of the present application .
  • a computer device which can be a personal computer, a server, or a network device, etc.
  • all or part of them may be implemented by software, hardware, firmware or any combination thereof.
  • software When implemented using software, it may be implemented in whole or in part in the form of a computer program product.
  • the computer program product includes one or more computer instructions.
  • the computer can be a general purpose computer, a special purpose computer, a computer network, or other programmable devices.
  • the computer instructions may be stored in or transmitted from one computer-readable storage medium to another computer-readable storage medium, for example, the computer instructions may be transmitted from a website, computer, server, or data center Transmission to another website site, computer, server, or data center by wired (eg, coaxial cable, optical fiber, digital subscriber line (DSL)) or wireless (eg, infrared, wireless, microwave, etc.).
  • wired eg, coaxial cable, optical fiber, digital subscriber line (DSL)
  • wireless eg, infrared, wireless, microwave, etc.
  • the computer-readable storage medium may be any available medium that can be stored by a computer, or a data storage device such as a server or a data center integrated with one or more available media.
  • the available medium may be a magnetic medium (such as a floppy disk, a hard disk, or a magnetic tape), an optical medium (such as a DVD), or a semiconductor medium (such as a solid state disk (Solid State Disk, SSD)), etc.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Human Resources & Organizations (AREA)
  • Strategic Management (AREA)
  • Economics (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Operations Research (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Mathematical Analysis (AREA)
  • Tourism & Hospitality (AREA)
  • General Business, Economics & Management (AREA)
  • Marketing (AREA)
  • Entrepreneurship & Innovation (AREA)
  • General Engineering & Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Quality & Reliability (AREA)
  • Development Economics (AREA)
  • Game Theory and Decision Science (AREA)
  • Databases & Information Systems (AREA)
  • Algebra (AREA)
  • Educational Administration (AREA)
  • Primary Health Care (AREA)
  • General Health & Medical Sciences (AREA)
  • Health & Medical Sciences (AREA)
  • Manufacturing & Machinery (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

一种任务求解方法，方法包括：获取第一线性规划任务中多个第一规划约束中每个第一规划约束的重要性，重要性表示第一规划约束对于降低第一线性规划任务的求解时间的贡献程度；根据所述重要性，对多个第一规划约束进行采样，以得到获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；根据所述多个第一规划约束的子集构建第二线性规划任务；将第一求解结果作为第一线性规划任务的初始值，并对初始化后的第一线性规划任务进行求解。由于重要性表示第一规划约束对于降低第一线性规划任务的求解时间的贡献程度，可以使采样得到的子模型的解接近于最优解，从而加速第一线性规划任务的求解过程。

Description

一种任务求解方法及其装置
本申请要求于2021年9月30日提交中国专利局、申请号为202111166727.3、发明名称为“一种任务求解方法及其装置”的中国专利申请的优先权，其全部内容通过引用结合在本申请中。
技术领域
本申请涉及调度领域，尤其涉及一种任务求解方法及其装置。
背景技术
调度问题是大型制造、物流、生产等环节中最常见的问题之一，在不同的场景下，调度总是有不同的意义。例如：物流调度主要是指在物流过程中，物流公司根据待发货物的重量、去向、规格、加急程度等对所属的车辆和人员进行合理的安排和调度；而生产环境中的调度是根据不同产线中不同机器的产能以及生产需求，在若干任务(job)中完成对任务的排序以及任务和机器(可调度资源)之间的匹配；大型制造工厂/机场的工人/空乘排班(timetabling)也是调度问题的一种，这是由于这类问题的目标也是依照工人/空乘的工作特点以及场景需要在不同的时间段内完成最优匹配。因此，核心是排序以及最优分配，而不局限任务是人还是货物。一般来讲，调度问题的目标是在给定任务数的前提下得到最小总工时(makespan)所对应的排序。
很多的调度问题(如排产、线体调度、加工网络布局等)都可以建模成一个数学问题来求解，线性规划(linear programming，LP)是其中使用最广的一类建模方法。线性规划模型可以包括目标函数和约束条件，其中，目标函数是指根据待优化的目标和影响该目标的变量所设计的函数。例如，在排产问题中，整个排产的目标通常是在满足所有资源约束的情况下，找出一个最好的加工计划，使得需求的满足率最高，同时整体的成本最小(例如成本可以包括但不限于加工成本、库存成本、转运成本)，此时，该目标函数可以是用于表示满足率最大化以及成本最小化的函数。另外，约束条件是指在求解目标函数的过程中所要满足的其他限制条件。
然而，随着场景复杂性的提升，线性规划任务中规划约束的数量通常较多，求解线性规划任务所需的求解时间很长。
发明内容
第一方面，本申请提供了一种任务求解方法，所述方法包括：
获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束；
在一种可能的实现中，终端设备可以将第一线性规划任务作为待求解模型传递至服务器，进而服务器可以获取第一线性规划任务。又例如，终端设备可以将第一线性规划任务作为求解待求解模型时所使用的的先验信息，也就是将包括第一线性规划任务在内的至少一个历史模型传递至服务器，进而服务器可以获取包括第一线性规划任务在内的至少一个 历史模型；
通常情况下，线性规划任务中约束的数量较多时，求解线性规划任务所需的求解时间很长，因此可以首先选择线性规划任务中的部分约束，并基于选择的部分约束进行求解，并将求解结果(选择的部分约束中求解变量的状态)赋予线性规划任务，相当于将求解结果作为线性规划任务的初始值，并对线性规划任务进行求解，如果选择的部分约束的求解结果与求解线性规划任务后的求解结果基本一致(或者描述为较为接近，这里的求解结果基本一致可以理解为相同的约束中的求解变量的参数值基本一致)，则求解线性规划任务时所需的迭代次数较少，也就是可以提高线性规划任务的求解速度。
因此，在求解第一线性规划任务之前，需要选择一部分约束进行求解，且得到的求解结果与第一线性规划任务的求解结果较为接近。
本申请实施例中，基于重要性来作为从多个第一规划约束中选择部分约束的依据，其中重要性可以指示对于降低所述第一线性规划任务的求解时间的贡献程度。其中，所谓指示对于降低所述第一线性规划任务的求解时间的贡献程度，可以理解为，在构建待求解模型的子模型时(也就是从待求解模型中的约束中选择一部分来构建子模型)，在将子模型求解的结果作为待求解模型的初始值的情况下，子模型包括该第一线性规划任务对于降低求解待求解模型的求解时间的贡献程度。
具体的，可以将重要性作为采样概率对多个第一规划约束进行采样可以得到一个子任务(第二规划任务)，该子任务中的规划约束为对于降低所述第一线性规划任务的求解时间的贡献程度较高的约束，因此，对第二规划任务求解后得到的求解结果与对第二规划任务求解后得到的求解结果基本一致(或者描述为较为接近，这里的求解结果基本一致可以理解为相同的约束中的求解变量的参数值基本一致)。
在一种可能的实现中，该重要性可以基于先验信息得到，其中先验信息可以为多个和待求解模型(第一线性规划任务)同类的一个或多个模型，所谓同类，可以理解为线性规划任务包括的约束类型、数量一致或者基本一致，也就是说第一线性规划任务和先验信息中的一个或多个模型包括的约束类型、数量一致或者基本一致。
在确定各个约束的重要性时，可以直接对先验信息中各个线性规划任务进行求解，得到求解各个线性规划任务的求解时间(若线性规划任务已经被求解过，也可以直接获取到求解时间)，然后对先验信息中的一个或多个线性规划模型进行子模型的提取、求解，并基于求解结果对线性规划模型进行初始化，然后对线性规划模型进行求解，以得到另一个求解时间，通过比对直接求解各个线性规划任务的求解时间，和对基于子模型求解结果进行初始化后的线性规划任务的求解时间，就可以知晓子模型中的约束对于降低线性规划任务的求解时间的贡献程度。
其中，为了能够量化上述重要性，可以对待求解模型的各个约束赋予一个概率(该概率可以为上述重要性的量化)，并基于概率对待求解模型进行采样，以构建子模型，并基于比对直接求解各个线性规划任务的求解时间，和对基于子模型求解结果进行初始化后的线性规划任务的求解时间，来更新概率，迭代一定的次数，就可以得到用于准确描述约束对于降低线性规划任务的求解时间的重要性信息(关于重要性的更新方式将在候选实施例中 描述)。
基于上述重要性采样得到的子模型(例如本申请实施例中的第二线性规划任务)中的各个规划约束对降低线性规划任务的求解时间的贡献程度很高，因此，基于第二线性规划任务的求解结果初始化后的第一线性规划模型的求解过程的时间可以被大大缩短；
根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；
根据所述多个第一规划约束的子集构建第二线性规划任务；
对所述第二线性规划任务进行求解，得到第一求解结果；将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。
可选的，第一求解结果可以包括多个第一规划约束的子集中的至少一个求解变量的参数值(或者参数状态)；
本申请实施例提供了一种任务求解方法，所述方法包括：获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束；获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度；根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；根据所述多个第一规划约束的子集构建第二线性规划任务；将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。通过上述方式，一方面选取第一线性规划任务中的关键约束构建子模型(第二线性规划任务)，然后利用子模型的解来第一线性规划任务从而加速求解过程。另一方面，在构建子模型时，基于重要性对第一线性规划任务进行采样，由于重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度，使采样得到的子模型的解接近于最优解，从而加速第一线性规划任务的求解过程。
在一种可能的实现中，第一线性规划模型可以为用于更新重要性所使用的先验信息，在这种情况下，可以基于比对直接求解各个线性规划任务的求解时间，和对基于子模型求解结果进行初始化后的线性规划任务的求解时间，来更新概率，迭代一定的次数，就可以得到用于准确描述约束对于降低线性规划任务的求解时间的重要性信息。
具体的，可以获取对所述第二线性规划任务进行求解的第一求解时间、以及对初始化后的所述第一线性规划任务进行求解的第二求解时间，所述第一求解时间和所述第三求解时间的加和可以作为上述基于子模型求解结果进行初始化后的线性规划任务的求解时间，并对所述第一线性规划任务进行求解，得到求解所述第一线性规划任务的第三求解时间，其中，第三求解时间可以认为是直接求解第一线性规划任务的求解时间，根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，就可以更新所述每个第一规划约束的重要性，其中，更新后的所述重要性与所述减少程度正相关。
应理解，还可以将采样得到第二线性规划任务的过程所需的时间也作为基于子模型求 解结果进行初始化后的线性规划任务的求解时间的一部分，也就是可以获取对所述多个第一规划约束进行采样的采样时间，并根据所述第一求解时间、所述第三求解时间以及所述采样时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性。
在一种可能的实现中，所述方法还包括：获取第三线性规划任务，所述第三线性规划任务包括所述多个第二规划约束，所述多个第二规划约束和所述多个第一规划约束的约束类型相同；获取所述多个第二规划约束中每个第二规划约束的重要性，其中更新后的每个第一规划约束的重要性用于作为约束类型相同的第二规划约束的重要性；根据所述每个第二规划约束的重要性，对所述多个第二规划约束进行采样，以获取第四线性规划任务，其中，所述每个第二规划约束的重要性用于确定第二规划约束的采样概率，所述第四线性规划任务包括所述多个第二规划约束中的部分第二规划约束；对所述第四线性规划任务进行求解，得到第三求解结果；将所述第三求解结果作为所述第三线性规划任务的初始值，并对初始化后的所述第三线性规划任务进行求解，得到第四求解结果。
在一种可能的实现中，所述第二线性规划任务包括M个求解变量，所述第一求解结果包括各个求解变量的参数值；
所述将所述第一求解结果作为所述第一线性规划任务的初始值，包括：
将所述第一求解结果中各个求解变量的参数值作为所述第一线性规划任务中的M个求解变量的参数值。
在一种可能的实现中，所述第一线性规划任务用于为至少一个待调度任务分配调度资源，所述第一规划约束为调度资源满足的约束，所述调度资源为生产线、生产设备或生产厂家。
在一种可能的实现中，所述得到第二求解结果之后，可能还会新加约束(例如第二规划约束)，可以获取第二规划约束，所述第二规划约束包括松弛变量以及所述松弛变量的上界，将所述第二规划约束增加至所述第一线性规划任务，以得到更新后的所述第一线性规划任务，并求解所述更新后的第一线性规划任务。具体可以是给新添加的约束中涉及到的新变量(松弛变量)根据其实际含义设置一个合理的bound(数值范围)，并修改这些变量的初始状态值，将状态改到其设置的bound上，使得初始解对于新添加的约束是可行的，进而加速线性规划的求解。
本申请可以在连续求解场景中针对新添加的松弛变量，预先设置变量上界和初始状态，从而加速连续求解。
本申请实施例还提供一个系统，其中，系统可以包括终端设备以及服务器，其中，终端设备可以发送待求解模型(第一线性规划任务)以及包括多个历史模型在内的先验信息至服务器，服务器可以基于包括多个历史模型在内的先验信息计算得到收敛的重要性，并 根据重要性采样第一线性规划任务，并执行上述实施例中步骤301至步骤303的步骤，以得到第二求解结果，并将第二求解结果回传至终端设备。
此外终端设备可以发送待求解模型以及包括多个历史模型(包括第一线性规划任务)在内的先验信息至服务器，服务器可以基于包括多个历史模型在内的先验信息计算得到收敛的重要性(计算过程可以参照上述实施例中关于更新重要性相关的描述)，并根据重要性采样待求解模型，以及求解待求解模型。
第二方面，本申请提供了一种任务求解装置，所述装置包括：
获取模块，用于获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束；
获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度；
采样模块，用于根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；
根据所述多个第一规划约束的子集构建第二线性规划任务；
求解模块，用于对所述第二线性规划任务进行求解，得到第一求解结果；
将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。
在一种可能的实现中，所述第一线性规划任务和所述第二线性规划任务均包括规划目标。
在一种可能的实现中，所述获取模块，还用于：
获取对所述第二线性规划任务进行求解的第一求解时间、以及对初始化后的所述第一线性规划任务进行求解的第二求解时间；
所述求解模块，还用于对所述第一线性规划任务进行求解，得到求解所述第一线性规划任务的第三求解时间；
所述装置还包括：
重要性更新模块，用于根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性，其中，更新后的所述重要性与所述减少程度正相关。
在一种可能的实现中，所述获取模块，还用于：
获取对所述多个第一规划约束进行采样的采样时间；
所述重要性更新模块，具体用于：
根据所述第一求解时间、所述第三求解时间以及所述采样时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性。
在一种可能的实现中，所述获取模块，还用于：
获取第三线性规划任务，所述第三线性规划任务包括所述多个第二规划约束，所述多个第二规划约束和所述多个第一规划约束的约束类型相同；
获取所述多个第二规划约束中每个第二规划约束的重要性，其中更新后的每个第一规划约束的重要性用于作为约束类型相同的第二规划约束的重要性；
所述采样模块，还用于：
根据所述每个第二规划约束的重要性，对所述多个第二规划约束进行采样，以获取第四线性规划任务，其中，所述每个第二规划约束的重要性用于确定第二规划约束的采样概率，所述第四线性规划任务包括所述多个第二规划约束中的部分第二规划约束；
所述求解模块，还用于：
对所述第四线性规划任务进行求解，得到第三求解结果；
将所述第三求解结果作为所述第三线性规划任务的初始值，并对初始化后的所述第三线性规划任务进行求解，得到第四求解结果。
在一种可能的实现中，所述第二线性规划任务包括M个求解变量，所述第一求解结果包括各个求解变量的参数值；
所述求解模块，具体用于：
将所述第一求解结果中各个求解变量的参数值作为所述第一线性规划任务中的M个求解变量的参数值。
在一种可能的实现中，所述第一线性规划任务用于为至少一个待调度任务分配调度资源，所述第一规划约束为调度资源满足的约束，所述调度资源为生产线、生产设备或生产厂家。
在一种可能的实现中，所述获取模块，还用于：
在所述得到第二求解结果之后，获取第二规划约束，所述第二规划约束包括松弛变量以及所述松弛变量的上界；
所述求解模块，还用于将所述第二规划约束增加至所述第一线性规划任务，以得到更新后的所述第一线性规划任务，并求解所述更新后的第一线性规划任务。
第三方面，本申请实施例提供了一种装置，包括存储器、处理器以及总线系统，其中，存储器用于存储程序，处理器用于执行存储器中的程序，以执行如上述第一方面及第一方面任一可选的方法。
第四方面，本发明实施例还提供一种系统，该系统包括至少一个处理器，至少一个存储器以及至少一个通信接口；处理器、存储器和通信接口通过通信总线连接并完成相互间的通信；
存储器用于存储执行以上方案的应用程序代码，并由处理器来控制执行。所述处理器用于执行所述存储器中存储的应用程序代码，以得到任务调度结果；其中存储器存储的代码可执行以上提供的一种任务求解方法。
通信接口，用于与其他设备或通信网络通信，以将所述任务求解结果发送至所述设备或通信网络。
第五方面，本申请实施例提供了一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，当其在计算机上运行时，使得计算机执行上述第一方面及其任一可选的方法。
第六方面，本申请实施例提供了一种计算机可读存储介质，所述计算机存储介质存储有一个或多个指令，所述指令在由一个或多个计算机执行时使得所述一个或多个计算机实施上述第二方面及其任一可选的系统。
第七方面，本申请实施例提供了一种计算机程序，当其在计算机上运行时，使得计算机执行上述第一方面及其任一可选的方法。
第八方面，本申请提供了一种芯片系统，该芯片系统包括处理器，用于支持终端设备或服务器实现上述方面中所涉及的功能，例如，发送或处理上述方法中所涉及的数据；或，信息。在一种可能的设计中，所述芯片系统还包括存储器，所述存储器，用于保存终端设备或服务器必要的程序指令和数据。该芯片系统，可以由芯片构成，也可以包括芯片和其他分立器件。
本申请实施例提供了一种任务求解方法，所述方法包括：获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束；获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度；根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；根据所述多个第一规划约束的子集构建第二线性规划任务；将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。通过上述方式，一方面选取第一线性规划任务中的关键约束构建子模型(第二线性规划任务)，然后利用子模型的解来第一线性规划任务从而加速求解过程。另一方面，在构建子模型时，基于重要性对第一线性规划任务进行采样，由于重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度，使采样得到的子模型的解接近于最优解，从而加速第一线性规划任务的求解过程。
附图说明
图1为本申请实施例提供一种应用架构示意图；
图2为本申请实施例提供的一种服务器的架构示意图；
图3为本申请实施例提供的一种任务求解方法的流程示意图；
图4为本申请实施例提供的一种任务求解方法的流程示意图；
图5为本申请实施例提供的一种排产任务示意图；
图6为本实施例提供的一种任务求解装置的结构示意；
图7为本申请实施例提供的终端设备的一种结构示意图；
图8为本申请实施例提供的服务器一种结构示意图；
图9为本申请实施例提供的芯片的一种结构示意图。
具体实施方式
下面结合本发明实施例中的附图对本发明实施例进行描述。本发明的实施方式部分使用的术语仅用于对本发明的具体实施例进行解释，而非旨在限定本发明。
下面结合附图，对本申请的实施例进行描述。本领域普通技术人员可知，随着技术的发展和新场景的出现，本申请实施例提供的技术方案对于类似的技术问题，同样适用。
本申请的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的术语在适当情况下可以互换，这仅仅是描述本申请的实施例中对相同属性的对象在描述时所采用的区分方式。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，以便包含一系列单元的过程、方法、系统、产品或设备不必限于那些单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它单元。
本申请实施例可以应用于多种场景(比如供应链、云计算、调度、存储优化等)的线性规划优化问题的求解中，加速线性规划求解器求解这些问题的效率。
参照图1，图1为本申请实施例提供的应用结构示意，本申请提供的任务求解方法可以作为求解器部署在云侧的服务器，终端设备可以将待求解模型(例如线性规划任务)传递至云侧的服务器，云侧的服务器可以基于自身部署的求解器对待求解模型进行求解，并将求解结果传递至终端设备。
比如用户可以根据自己的业务场景构建待求解模型，在求解时候，可以将一部分历史上同类问题的模型传递至服务器，服务器可以调用求解器较快的输出用户输入模型的最优解。用户可以根据这个解去使用平台提供的功能生成数据报表或者自己对它进行处理得到想要的结果。
参照图2，图2为本申请实施例提供的服务器的架构示意。具体的，服务器200由一个或多个服务器实现，服务器200可因配置或性能不同而产生比较大的差异，可以包括一个或一个以上中央处理器(central processing units，CPU)22(例如，一个或一个以上处理器)和存储器232，一个或一个以上存储应用程序242或数据244的存储介质230(例如一个或一个以上海量存储设备)。其中，存储器232和存储介质230可以是短暂存储或持久存储。存储在存储介质230的程序可以包括一个或一个以上模块(图示没标出)，每个模块可以包括对服务器中的一系列指令操作。更进一步地，中央处理器22可以设置为与存储介质230通信，在服务器200上执行存储介质230中的一系列指令操作。
服务器200还可以包括一个或一个以上电源222，一个或一个以上有线或无线网络接口250，一个或一个以上输入输出接口258；或，一个或一个以上操作系统241，例如Windows  ServerTM，Mac OS XTM，UnixTM,LinuxTM，FreeBSDTM等等。
本申请实施例中，中央处理器22，用于执行本申请实施例中描述的任务求解方法。
应理解，本申请实施例提供的任务求解方法也可以作为求解器部署在端侧的终端设备上，这里并不限定。
本申请实施例中待求解模型可以用于解决调度问题。调度问题是大型制造/物流/生产等环节中最常见的问题之一，并且在不同的场景下，调度总是有不同的意义。例如：物流调度主要是指在物流过程中，物流公司根据待发货物的重量、去向、规格、加急程度等对所属的车辆和人员进行合理的安排和调度。
而生产环境中的调度是根据不同产线中不同机器的产能以及生产需求，在若干任务(job)中完成对任务的排序以及任务和生产设备之间的匹配。即将多个任务分配至各条生产线中的生产设备。
例如，在作业车间调度(job-shop scheduling)的场景中，n个工件在m台机器上加工，每个工件有特定的加工工艺，每个工件加工的顺序及每道工序所花时间给定，安排工件在每台机器上工件的加工顺序，使得某种指标最优。这里不要求每个工件都在每个机器上执行。
例如，在流水车间调度(flow-shop scheduling)的场景中，该类调度问题要求每个任务必须依次执行到每个阶段，不涉及任务和阶段的匹配，而主要是决定任务的执行顺序。防止由于中间等待时间过长，而造成整体的完成时间时长。
与一般的货物调度略有不同的是，机场/大型制造工厂的工人/空姐排班(timetabling)也是调度问题的一种，这是由于这类问题的目标也是依照工人/空姐的工作特点以及场景需要在不同的时间段内完成最优匹配。因此，核心是排序以及最有分配，而不局限“任务”是人还是货物。一般来讲，调度问题的目标是在给定任务数的前提下得到最小总工时(makespan)所对应的排序。
同时，调度问题在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源，如线程、进程或数据流；也可以指硬件资源，如处理器、网络连接或扩展卡。进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态(在负载均衡中)，允许多位用户有效地同时共享系统资源，或达到指定的服务质量。
很多的调度问题(如排产、线体调度、加工网络布局等)都可以建模成一个数学问题来求解，线性规划(linear programming，LP)是其中使用最广的一类建模方法。目前，线性规划求解器底层依赖的算法中，单纯型法是目前使用最为广泛的算法，并且也是各个线性规划求解器优化的比较多的一类算法。
对于单纯型算法，通常，算法先选择一个初始可行基解，然后检查这个解是否已经达到了最优解，随后会对基矩阵做LU分解来计算基矩阵的逆；LU分解每K次迭代才会做一次，其余的迭代都会用增量的方法来更新L矩阵和U矩阵的更新。然后，算法会根据启发式的规则选择入基变量和出基变量来更新基变量。不停执行这样的循环，直到找到最优解，或者发现问题状态异常，整个算法退出。
从求解器的使用来分，可以分成两种：标准求解和连续求解。标准求解指求解器在没 有任何先验的情况下进行一次完整的求解，会分别经过预求解，求解，后处理等步骤，标准流程是在Simplex算法的前后分别增加了一个预求解模块和后处理模块。预求解模块会对模型进行化简，根据模型结构不同，化简的程度也不同，通常能将模型规模(变量数量、约束数量)减少30％～70％，这样Simplex可以求解一个相对简单的模型，从而加速求解。后处理模块把预求解生成的简单模型的解映射回原问题，最终得到原模型的解。
连续求解指前面已经对模型经过一次求解得到了最优解，随后对模型进行部分修改，比如增加一些变量约束或者修改已有变量的上下界，再次求解。这样基于上次最优解进行重求解的过程称为连续求解。
然而，上述描述的现有的标准求解流程没有利用任何先验知识来构造初始可行基，因此构造的初始可行基比较简单，从简单可行基出发进行单纯型算法迭代需要的迭代数过多，时间过长。且连续求解时候对于初始变量状态的调整方面做的过于直接，使得连续求解时找到初始的可行基解花费很长的时间。本申请实施例提供的任务求解方法可以基于先验知识来构造初始可行基，可以降低求解时间。
为了使得本申请更加的清楚，首先对本申请提到的部分概念和处理流程作简单介绍。
线性规划(Linear Programming，LP)：是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。
约束：Constraints，是数学规划问题中的约束，即对决策变量的数值要求。
基解：Basic Solution，在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解，这个解称之为线性规划的基本解。
基可行解：Basic Feasible Solution，基可行解即基本可行解的简称，是处理线性规划的基本概念。满足非负条件的基本解称为基可行解。
单纯行法：Simplex，单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法的基本思路是：先找出可行域的一个顶点，根据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止。
下面结合本申请实施例中的附图对本申请实施例进行描述。本申请的实施方式部分使用的术语仅用于对本申请的具体实施例进行解释，而非旨在限定本申请。参见图3，图3为本申请实施例提供的一种任务求解方法，所述方法包括：
301、获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束。
在一种可能的实现中，步骤301的执行主体可以为服务器，例如终端设备可以将第一线性规划任务作为待求解模型传递至服务器，进而服务器可以获取第一线性规划任务。又例如，终端设备可以将第一线性规划任务作为求解待求解模型时所使用的的先验信息，也就是将包括第一线性规划任务在内的至少一个历史模型传递至服务器，进而服务器可以获取包括第一线性规划任务在内的至少一个历史模型。
通常，线性规划模型可以包括目标函数和约束条件，其中，目标函数是指根据待优化的目标和影响该目标的变量所设计的函数。例如，在排产问题中，整个排产的目标通常是 在满足所有资源约束的情况下，找出一个最好的加工计划，使得需求的满足率最高，同时整体的成本最小(例如成本可以包括但不限于加工成本、库存成本、转运成本)，此时，该目标函数可以是用于表示满足率最大化以及成本最小化的函数。另外，约束条件是指在求解目标函数的过程中所要满足的其他限制条件。
在一种可能的实现中，所述第一线性规划任务用于为至少一个待调度任务分配调度资源，所述第一规划约束为调度资源满足的约束，所述调度资源为生产线、生产设备或生产厂家。
例如，在产品生产的场景中，待调度任务可以是待生产的产品，在人员调度的场景中，待调度任务可以是待生产的人等等，本申请实施例并不限定。
在产品生产的场景中，多个可调度资源组中的每个可调度资源组可以为生产线，例如在手机的生产场景中，多个可调度资源组中的每个可调度资源组可以为一种手机组件的生产线，例如可以是电池的生产线、外壳的生产线、芯片的生产线等等，相应的，每个可调度资源组可以包括多个可调度资源，多个可调度资源中的每个可调度资源为所述生产线中的生产设备，例如，电池生产线可以包括多个电池生产设备，外壳生产线可以包括多个外壳生产设备，这里并不限定。
在人员调度的场景中，多个可调度资源组中的每个可调度资源组可以为时间段，例如在人员调度的场景中，多个可调度资源组中的每个可调度资源组可以为一天，例如可以是周一、周二、周三或者是一些月份的某一天等等，相应的，每个可调度资源组可以包括多个可调度资源，多个可调度资源中的每个可调度资源为时间段中的子时间段，例如，某一天可以包括多个小时、多个分钟或者其他多个子时间段，这里并不限定。
其中，第一规划约束可以包括求解变量，以及各个求解变量需要满足的约束。
302、获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度。
在一种可能的实现中，第一线性规划任务可以作为待求解模型。在求解第一线性规划任务时，可以首先获取各个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度。
通常情况下，线性规划任务中约束的数量较多时，求解线性规划任务所需的求解时间很长，因此可以首先选择线性规划任务中的部分约束，并基于选择的部分约束进行求解，并将求解结果(选择的部分约束中求解变量的状态)赋予线性规划任务，相当于将求解结果作为线性规划任务的初始值，并对线性规划任务进行求解，如果选择的部分约束的求解结果与求解线性规划任务后的求解结果基本一致(或者描述为较为接近，这里的求解结果基本一致可以理解为相同的约束中的求解变量的参数值基本一致)，则求解线性规划任务时所需的迭代次数较少，也就是可以提高线性规划任务的求解速度。
因此，在求解第一线性规划任务之前，需要选择一部分约束进行求解，且得到的求解结果与第一线性规划任务的求解结果较为接近。
本申请实施例中，基于重要性来作为从多个第一规划约束中选择部分约束的依据，其 中重要性可以指示对于降低所述第一线性规划任务的求解时间的贡献程度。其中，所谓指示对于降低所述第一线性规划任务的求解时间的贡献程度，可以理解为，在构建待求解模型的子模型时(也就是从待求解模型中的约束中选择一部分来构建子模型)，在将子模型求解的结果作为待求解模型的初始值的情况下，子模型包括该第一线性规划任务对于降低求解待求解模型的求解时间的贡献程度。
具体的，可以将重要性作为采样概率对多个第一规划约束进行采样可以得到一个子任务(第二规划任务)，该子任务中的规划约束为对于降低所述第一线性规划任务的求解时间的贡献程度较高的约束，因此，对第二规划任务求解后得到的求解结果与对第二规划任务求解后得到的求解结果基本一致(或者描述为较为接近，这里的求解结果基本一致可以理解为相同的约束中的求解变量的参数值基本一致)。
在一种可能的实现中，该重要性可以基于先验信息得到，其中先验信息可以为多个和待求解模型(第一线性规划任务)同类的一个或多个模型，所谓同类，可以理解为线性规划任务包括的约束类型、数量一致或者基本一致，也就是说第一线性规划任务和先验信息中的一个或多个模型包括的约束类型、数量一致或者基本一致。
在确定各个约束的重要性时，可以直接对先验信息中各个线性规划任务进行求解，得到求解各个线性规划任务的求解时间(若线性规划任务已经被求解过，也可以直接获取到求解时间)，然后对先验信息中的一个或多个线性规划模型进行子模型的提取、求解，并基于求解结果对线性规划模型进行初始化，然后对线性规划模型进行求解，以得到另一个求解时间，通过比对直接求解各个线性规划任务的求解时间，和对基于子模型求解结果进行初始化后的线性规划任务的求解时间，就可以知晓子模型中的约束对于降低线性规划任务的求解时间的贡献程度。
其中，参阅图4，为了能够量化上述重要性，可以对待求解模型的各个约束赋予一个概率(该概率可以为上述重要性的量化)，并基于概率对待求解模型进行采样，以构建子模型，并基于比对直接求解各个线性规划任务的求解时间，和对基于子模型求解结果进行初始化后的线性规划任务的求解时间，来更新概率，迭代一定的次数，就可以得到用于准确描述约束对于降低线性规划任务的求解时间的重要性信息(关于重要性的更新方式将在候选实施例中描述)。
基于上述重要性采样得到的子模型(例如本申请实施例中的第二线性规划任务)中的各个规划约束对降低线性规划任务的求解时间的贡献程度很高，因此，基于第二线性规划任务的求解结果初始化后的第一线性规划模型的求解过程的时间可以被大大缩短。
应理解，本申请实施例中的第一线性规划模型可以为计算各个第一规划约束的重要性时采用的先验信息，在这种情况下，步骤302所获取的所述多个第一规划约束中每个第一规划约束的重要性可以为初始化的重要性，或者是迭代过程中的重要性(还未收敛到满足要求)。
应理解，计算各个第一规划约束的重要性时采用的先验信息可以包括多个模型，第一线性规划任务可以为多个模型中的一个，且第一线性规划任务可以是从多个模型中随机选择的。
示例性的，可以获取N个历史上跟待求解模型同质的模型P，比如在过去不同时间点的 同一类优化问题。并且N个模型一共有C类约束，每一类约束用c i表示；预先求解每个问题P i,i＝1,2,…,N，得到它们直接求解的时间为
Figure PCTCN2022121620-appb-000001
设每类约束的重要性为
Figure PCTCN2022121620-appb-000002
i＝1,2,…,C，并且它们的初始值为
Figure PCTCN2022121620-appb-000003
(或者设定为其他初始值)；选择一个模型P i，并根据α的概率采样出子模型
Figure PCTCN2022121620-appb-000004
(包含了约束
Figure PCTCN2022121620-appb-000005
)，求解这个子模型，然后把子模型解作为原问题的初始值求解原问题，记录下总的时间(包含求解子模型的时间)T j；更新
Figure PCTCN2022121620-appb-000006
示例性的，可以基于如下公式更新：
Figure PCTCN2022121620-appb-000007
其中ρ为步长，g(·)为概率更新函数，重复上述步骤，直到重要性收敛。
在得到各个规划约束的重要性后，在对第一线性规划任务进行求解前，可以获取到第一线性规划任务中各个第一线性规划任务对应的重要性。
303、根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；
304、根据所述多个第一规划约束的子集构建第二线性规划任务；
在一种可能的实现中，重要性越高的第一规划约束，越大概率被采样作为第二线性规划任务的一部分，因此，第二线性规划任务可以包括所述多个第一规划约束中的部分第一规划约束。
在一种可能的实现中，第一线性规划模型为待求解模型或者用于更新重要性所使用的先验信息，可以将收敛的重要性作为各个约束的采样概率，并对多个第一规划约束进行采样，以获取第二线性规划任务，基于上述重要性采样得到的子模型(例如本申请实施例中的第二线性规划任务)中的各个规划约束对降低线性规划任务的求解时间的贡献程度很高，因此，基于第二线性规划任务的求解结果初始化后的第一线性规划模型的求解过程的时间可以被大大缩短。
305、对所述第二线性规划任务进行求解，得到第一求解结果。
在一种可能的实现中，所述第二线性规划任务包括M个求解变量，所述第一求解结果可以包括各个求解变量的参数值，其中这里的参数值可以为最优解的数值或者是求解变量的状态。在将所述第一求解结果作为所述第一线性规划任务的初始值时，具体可以将所述第一求解结果中各个求解变量的参数值作为所述第一线性规划任务中的M个求解变量的参数值。也就是将第一求解结果中求解变量的参数值赋予第一线性规划任务，而第一线性规划任务中除了第二线性规划任务中包括的规划约束之外的第一规划约束的初始值可以由求解器指定，这里并不限定。
306、将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。
在一种可能的实现中，求解器可以将第一求解结果读入第一线性规划任务，随后第一线性规划任务中的求解变量v i的初始状态赋为s i，并对初始化后的所述第一线性规划任务进行求解，以得到第二求解结果。
在一种可能的实现中，第一线性规划模型可以为待求解模型，此时第二求解结果可以为待求解模型的求解结果，服务器在得到第二求解结果之后，可以将第二求解结果回传至终端设备。
在一种可能的实现中，所述得到第二求解结果之后，可能还会新加约束(例如第二规划约束)，可以获取第二规划约束，所述第二规划约束包括目标求解变量以及松弛变量，将所述第二规划约束增加至所述第一线性规划任务，以得到更新后的所述第一线性规划任务，并求解所述更新后的第一线性规划任务。也就是可以给新添加的约束中涉及到的新变量根据其实际含义设置一个合理的bound(数值范围)，并修改这些变量的初始状态值，将状态改到步骤一设置的bound上，使得初始解对于新添加的约束是可行的，进而加速线性规划的求解。
本申请可以在连续求解场景中针对新添加的松弛变量，预先设置变量上界和初始状态，从而加速连续求解。
在一种可能的实现中，第一线性规划模型可以为用于更新重要性所使用的先验信息，在这种情况下，可以基于比对直接求解各个线性规划任务的求解时间，和对基于子模型求解结果进行初始化后的线性规划任务的求解时间，来更新概率，迭代一定的次数，就可以得到用于准确描述约束对于降低线性规划任务的求解时间的重要性信息。
具体的，可以获取对所述第二线性规划任务进行求解的第一求解时间、以及对初始化后的所述第一线性规划任务进行求解的第二求解时间，所述第一求解时间和所述第三求解时间的加和可以作为上述基于子模型求解结果进行初始化后的线性规划任务的求解时间，并对所述第一线性规划任务进行求解，得到求解所述第一线性规划任务的第三求解时间，其中，第三求解时间可以认为是直接求解第一线性规划任务的求解时间，根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，就可以更新所述每个第一规划约束的重要性，其中，更新后的所述重要性与所述减少程度正相关。
应理解，还可以将采样得到第二线性规划任务的过程所需的时间也作为基于子模型求解结果进行初始化后的线性规划任务的求解时间的一部分，也就是可以获取对所述多个第一规划约束进行采样的采样时间，并根据所述第一求解时间、所述第三求解时间以及所述采样时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性。
例如，构造子模型花费的时间记为T a。对这个子模型(包含c j1,…,c jK一共K类约束)调用线性规划求解器进行求解，求解得到的子模型的最优解S，求解花费时间记为T b。最后将子模型的解作为初始解带入原模型P i中，再求解一次P i，这个步骤花费的时间为T c。最后将这次重要性采样求解得到的总时间记为T j＝T a+T b+T c。
示例性的，可以对于每一类约束c j1，可以执行下面的公式来进行更新：
Figure PCTCN2022121620-appb-000008
Figure PCTCN2022121620-appb-000009
其中，ρ可以为预先设置的超参。
上述基于根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性可以为对重要性的一次迭代过程，可以基于其他先验信息或者对第一线性规划模型多次执行上述迭代过程来更新重要性，以得到收敛的重要性。
服务器可以基于收敛后的重要性，对待求解模型进行求解。
例如，若待求解模型为目标线性规划任务，可以基于收敛后的重要性，对目标线性规划任务中的规划约束进行采样，以得到子模型，并对子模型进行求解，之后将求解结果作为目标线性规划任务的初始值，再对目标线性规划任务进行求解，以得到最终的求解结果，服务器可以将上述得到的最终求解结果反馈至终端设备。
以待求解模型为第三线性规划任务为例，可以获取第三线性规划任务，所述第三线性规划任务包括所述多个第二规划约束，所述多个第二规划约束和所述多个第一规划约束的约束类型相同；
获取所述多个第二规划约束中每个第二规划约束的重要性，其中更新后的每个第一规划约束的重要性用于作为约束类型相同的第二规划约束的重要性；
根据所述每个第二规划约束的重要性，对所述多个第二规划约束进行采样，以获取第四线性规划任务，其中，所述每个第二规划约束的重要性用于确定第二规划约束的采样概率，所述第四线性规划任务包括所述多个第二规划约束中的部分第二规划约束；对所述第四线性规划任务进行求解，得到第三求解结果；将所述第三求解结果作为所述第三线性规划任务的初始值，并对初始化后的所述第三线性规划任务进行求解，得到第四求解结果。
示例性的，以多工厂排产问题为例，整个排产的目标通常是在满足所有资源约束的情况下，找出一个最好的加工计划，使得需求的满足率最高，同时整体的成本最小(加工成本、库存成本、转运成本)。图5展示了一个排产样例，假设客户下单了2000台PC，1000台主机，800台笔记本。然后有两家工厂可以加工这三类产品(每天最多加工1000件产品)。加工1台PC必须要先有一台主机，并且组装成PC只能在第一家工厂做。图中已经展示了一个最优的排产方案，即第一天在两家工厂各加工1000台主机，并且将第二家工厂的主机运往第一家工厂；第二天在第一家工厂把第一天加工完的主机组装成PC，然后再第二家工厂再加工1000台主机；第三天在第一家工厂使用第一天从第二家工厂运出的主机组装成1000台PC，最后在第二家工厂加工800台笔记本。这样，所有的需求都能满足，并且总的成本最低。多工厂排产本质是一个整数规划的问题，但是由于整数规划的求解复杂度过高，对于这样超大规模的模型，很难在规定的时间内求得最优解。所以通常的做法是将问题松弛成线性规划，然后再通过一些近似的方法，把线性规划求解得到的实数解调整成整数解。
首先收集历史三个月的排产模型，构成90个模型左右的训练数据集。同时对于排产问题主要库存约束、产能约束、配对约束、特控约束、SR约束、订单需求延期约束、预测需求延期约束、最大替代约束等18类约束。
对这90个模型先用线性规划求解器求解一次，记录求解的时间
Figure PCTCN2022121620-appb-000010
初始化 约束的重要性概率
Figure PCTCN2022121620-appb-000011
选择一个模型P i，然后根据当前的α采样出一个子模型
Figure PCTCN2022121620-appb-000012
采样的方法为对于每类约束，随机生成一个随机数r，如果
Figure PCTCN2022121620-appb-000013
那么这类约束和它对应的变量都被纳入子模型中，构造子模型花费的时间记为T a。对这个子模型(包含
Figure PCTCN2022121620-appb-000014
一共K类约束)调用线性规划求解器进行求解，求解得到的子模型的最优解S，求解花费时间记为T b。最后将子模型的解作为初始解带入原模型P i中，再求解一次P i，这个步骤花费的时间为T c。最后将这次重要性采样求解得到的总时间记为T j＝T a+T b+T c。中记录的T j更新重要性概率α。对于子模型中的每一类约束c j1，执行下面的更新公式：
Figure PCTCN2022121620-appb-000015
Figure PCTCN2022121620-appb-000016
继续选择模型进行更新操作，直到更新一定次数为止，得到训练好的α；拿到一个当前最新时刻的排产模型，根据历史数据中训练好的α，先采样一个子模型，随后求解这个子模型得到子模型的解S，把S作为初始值带入到原模型中，求解原模型得到这个排产问题的一个实数解。
针对排产问题中的最小批量约束，也就是每天的加工量要么等于0，要么大于等于某个常数C。由于建立线性规划模型时候无法考虑这个约束，因此这里可以使用连续求解的方法，对已经求解完的模型添加形如下面样式的约束：x i+s j≥C；其中x i是前面标准求解得到的某个大于0的变量，s j是新添加的松弛变量。同时将s j加入目标函数中。此时再求解一次加了约束的模型，达到的效果是x i能够尽量大于等于C。中新增的松弛变量s j，设置变量的UpperBound
Figure PCTCN2022121620-appb-000017
同时在求解前设置status(s j)＝atUpperBound。求解修改过松弛变量初始状态的模型，得到解。经过的步骤，就可以完成排产问题模型的求解。
表1展示了本申请实施例的求解提升效果，相比直接求解，利用本申请实施例的求解方法效率提升平均有20％左右。
表1
Figure PCTCN2022121620-appb-000018
本申请实施例提供了一种任务求解方法，所述方法包括：获取第一线性规划任务，所 述第一线性规划任务包括多个第一规划约束；获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度；根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；根据所述多个第一规划约束的子集构建第二线性规划任务；将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。通过上述方式，一方面选取第一线性规划任务中的关键约束构建子模型(第二线性规划任务)，然后利用子模型的解来第一线性规划任务从而加速求解过程。另一方面，在构建子模型时，基于重要性对第一线性规划任务进行采样，由于重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度，使采样得到的子模型的解接近于最优解，从而加速第一线性规划任务的求解过程。
本申请实施例还提供一个系统，其中，系统可以包括终端设备以及服务器，其中，终端设备可以发送待求解模型(第一线性规划任务)以及包括多个历史模型在内的先验信息至服务器，服务器可以基于包括多个历史模型在内的先验信息计算得到收敛的重要性，并根据重要性采样第一线性规划任务，并执行上述实施例中步骤301至步骤303的步骤，以得到第二求解结果，并将第二求解结果回传至终端设备。
此外终端设备可以发送待求解模型以及包括多个历史模型(包括第一线性规划任务)在内的先验信息至服务器，服务器可以基于包括多个历史模型在内的先验信息计算得到收敛的重要性(计算过程可以参照上述实施例中关于更新重要性相关的描述)，并根据重要性采样待求解模型，以及求解待求解模型。
参照图6，图6为本申请实施例提供的一种任务求解装置的结构示意，如图6所示，所述装置600可以包括：
获取模块601，用于获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束；
获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度；
其中，关于获取模块601的具体描述可以参照上述实施例中步骤301和302的描述，这里不再赘述。
采样模块602，用于根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；
根据所述多个第一规划约束的子集构建第二线性规划任务；
其中，关于采样模块602的具体描述可以参照上述实施例中步骤303和步骤304的描述，这里不再赘述。
求解模块603，用于对所述第二线性规划任务进行求解，得到第一求解结果；
将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一 线性规划任务进行求解，得到第二求解结果。
其中，关于求解模块603的具体描述可以参照上述实施例中步骤305和306的描述，这里不再赘述。
在一种可能的实现中，所述第一线性规划任务和所述第二线性规划任务均包括规划目标。
在一种可能的实现中，所述获取模块，还用于：
获取对所述第二线性规划任务进行求解的第一求解时间、以及对初始化后的所述第一线性规划任务进行求解的第二求解时间；
所述求解模块，还用于对所述第一线性规划任务进行求解，得到求解所述第一线性规划任务的第三求解时间；
所述装置还包括：
重要性更新模块，用于根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性，其中，更新后的所述重要性与所述减少程度正相关。
在一种可能的实现中，所述获取模块，还用于：
获取对所述多个第一规划约束进行采样的采样时间；
所述重要性更新模块，具体用于：
根据所述第一求解时间、所述第三求解时间以及所述采样时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性。
在一种可能的实现中，所述获取模块，还用于：
获取第三线性规划任务，所述第三线性规划任务包括所述多个第二规划约束，所述多个第二规划约束和所述多个第一规划约束的约束类型相同；
获取所述多个第二规划约束中每个第二规划约束的重要性，其中更新后的每个第一规划约束的重要性用于作为约束类型相同的第二规划约束的重要性；
所述采样模块，还用于：
根据所述每个第二规划约束的重要性，对所述多个第二规划约束进行采样，以获取第四线性规划任务，其中，所述每个第二规划约束的重要性用于确定第二规划约束的采样概率，所述第四线性规划任务包括所述多个第二规划约束中的部分第二规划约束；
所述求解模块，还用于：
对所述第四线性规划任务进行求解，得到第三求解结果；
将所述第三求解结果作为所述第三线性规划任务的初始值，并对初始化后的所述第三线性规划任务进行求解，得到第四求解结果。
在一种可能的实现中，所述第二线性规划任务包括M个求解变量，所述第一求解结果包括各个求解变量的参数值；
所述求解模块，具体用于：
将所述第一求解结果中各个求解变量的参数值作为所述第一线性规划任务中的M个求解变量的参数值。
在一种可能的实现中，所述第一线性规划任务用于为至少一个待调度任务分配调度资源，所述第一规划约束为调度资源满足的约束，所述调度资源为生产线、生产设备或生产厂家。
在一种可能的实现中，所述获取模块，还用于：
在所述得到第二求解结果之后，获取第二规划约束，所述第二规划约束包括目标求解变量以及松弛变量；
所述求解模块，还用于将所述第二规划约束增加至所述第一线性规划任务，以得到更新后的所述第一线性规划任务，并求解所述更新后的第一线性规划任务。
接下来介绍本申请实施例提供的一种终端设备，请参阅图7，图7为本申请实施例提供的终端设备的一种结构示意图，终端设备700具体可以表现为手机、平板、笔记本电脑、智能穿戴设备、服务器等，此处不做限定。其中，终端设备700上可以部署有图6对应实施例中所描述的任务求解装置，用于实现图6对应实施例中任务求解的功能。具体的，终端设备700包括：接收器701、发射器702、处理器703和存储器704(其中终端设备700中的处理器703的数量可以一个或多个，图7中以一个处理器为例)，其中，处理器703可以包括应用处理器7031和通信处理器7032。在本申请的一些实施例中，接收器701、发射器702、处理器703和存储器704可通过总线或其它方式连接。
存储器704可以包括只读存储器和随机存取存储器，并向处理器703提供指令和数据。存储器704的一部分还可以包括非易失性随机存取存储器(non-volatile random access memory，NVRAM)。存储器704存储有处理器和操作指令、可执行模块或者数据结构，或者它们的子集，或者它们的扩展集，其中，操作指令可包括各种操作指令，用于实现各种操作。
处理器703控制终端设备的操作。具体的应用中，终端设备的各个组件通过总线系统耦合在一起，其中总线系统除包括数据总线之外，还可以包括电源总线、控制总线和状态信号总线等。但是为了清楚说明起见，在图中将各种总线都称为总线系统。
上述本申请实施例揭示的方法可以应用于处理器703中，或者由处理器703实现。处理器703可以是一种集成电路芯片，具有信号的处理能力。在实现过程中，上述方法的各步骤可以通过处理器703中的硬件的集成逻辑电路或者软件形式的指令完成。上述的处理器703可以是通用处理器、数字信号处理器(digital signal processing，DSP)、微处理器或微控制器，还可进一步包括专用集成电路(application specific integrated circuit，ASIC)、现场可编程门阵列(field-programmable gate array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。该处理器703可以实现或者执行本申请实施例中的公开的各方法、步骤及逻辑框图。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。结合本申请实施例所公开的方法的步骤可以直接体现为硬件译码处理器执行完成，或者用译码处理器中的硬件及软件模块组合执行完成。软件模块可以位于随机存储器，闪存、只读存储器，可编程只读存储器或者电可擦写可编程存储器、寄存器等本领域成熟的存储介质中。该存储介质位于存储器704，处理器703读取存储器704中的 信息，结合其硬件完成上述方法中关于终端设备的步骤。
接收器701可用于接收输入的数字或字符信息，以及产生与终端设备的相关设置以及功能控制有关的信号输入。发射器702可用于通过第一接口输出数字或字符信息；发射器702还可用于通过第一接口向磁盘组发送指令，以修改磁盘组中的数据；发射器702还可以包括显示屏等显示设备。
本申请实施例中，在一种情况下，处理器703，用于执行上述实施例中的终端设备执行的步骤。
本申请实施例还提供了一种服务器，请参阅图8，图8是本申请实施例提供的服务器一种结构示意图，具体的，服务器800由一个或多个服务器实现，服务器800可因配置或性能不同而产生比较大的差异，可以包括一个或一个以上中央处理器(central processing units，CPU)88(例如，一个或一个以上处理器)和存储器832，一个或一个以上存储应用程序842或数据844的存储介质830(例如一个或一个以上海量存储设备)。其中，存储器832和存储介质830可以是短暂存储或持久存储。存储在存储介质830的程序可以包括一个或一个以上模块(图示没标出)，每个模块可以包括对服务器中的一系列指令操作。更进一步地，中央处理器88可以设置为与存储介质830通信，在服务器800上执行存储介质830中的一系列指令操作。
服务器800还可以包括一个或一个以上电源826，一个或一个以上有线或无线网络接口850，一个或一个以上输入输出接口858；或，一个或一个以上操作系统841，例如Windows ServerTM，Mac OS XTM，UnixTM,LinuxTM，FreeBSDTM等等。
本申请实施例中，中央处理器88，用于执行上述实施例任务求解方法相关的步骤。
本申请实施例中还提供一种包括计算机程序产品，当其在计算机上运行时，使得计算机执行如前述终端设备所执行的步骤，或者，使得计算机执行如前述服务器所执行的步骤。
本申请实施例中还提供一种计算机可读存储介质，该计算机可读存储介质中存储有用于进行信号处理的程序，当其在计算机上运行时，使得计算机执行如前述终端设备所执行的步骤，或者，使得计算机执行如前述服务器所执行的步骤。
本申请实施例提供的终端设备、服务器或终端设备具体可以为芯片，芯片包括：处理单元和通信单元，所述处理单元例如可以是处理器，所述通信单元例如可以是输入/输出接口、管脚或电路等。该处理单元可执行存储单元存储的计算机执行指令，以使终端设备内的芯片执行上述实施例描述的数据处理方法，或者，以使服务器内的芯片执行上述实施例描述的数据处理方法。可选地，所述存储单元为所述芯片内的存储单元，如寄存器、缓存等，所述存储单元还可以是所述无线接入设备端内的位于所述芯片外部的存储单元，如只读存储器(read-only memory，ROM)或可存储静态信息和指令的其他类型的静态存储设备，随机存取存储器(random access memory，RAM)等。
具体的，请参阅图9，图9为本申请实施例提供的芯片的一种结构示意图，所述芯片可以表现为神经网络处理器NPU 900，NPU 900作为协处理器挂载到主CPU(Host CPU)上，由Host CPU分配任务。NPU的核心部分为运算电路903，通过控制器904控制运算电路903提取存储器中的矩阵数据并进行乘法运算。
在一些实现中，运算电路903内部包括多个处理单元(Process Engine,PE)。在一些实现中，运算电路903是二维脉动阵列。运算电路903还可以是一维脉动阵列或者能够执行例如乘法和加法这样的数学运算的其它电子线路。在一些实现中，运算电路903是通用的矩阵处理器。
举例来说，假设有输入矩阵A，权重矩阵B，输出矩阵C。运算电路从权重存储器902中取矩阵B相应的数据，并缓存在运算电路中每一个PE上。运算电路从输入存储器901中取矩阵A数据与矩阵B进行矩阵运算，得到的矩阵的部分结果或最终结果，保存在累加器(accumulator)908中。
统一存储器906用于存放输入数据以及输出数据。权重数据直接通过存储单元访问控制器(Direct Memory Access Controller，DMAC)905，DMAC被搬运到权重存储器902中。输入数据也通过DMAC被搬运到统一存储器906中。
BIU为Bus Interface Unit即，总线接口单元910，用于AXI总线与DMAC和取指存储器(Instruction Fetch Buffer，IFB)909的交互。
总线接口单元910(Bus Interface Unit，简称BIU)，用于取指存储器909从外部存储器获取指令，还用于存储单元访问控制器905从外部存储器获取输入矩阵A或者权重矩阵B的原数据。
DMAC主要用于将外部存储器DDR中的输入数据搬运到统一存储器906或将权重数据搬运到权重存储器902中或将输入数据数据搬运到输入存储器901中。
向量计算单元907包括多个运算处理单元，在需要的情况下，对运算电路903的输出做进一步处理，如向量乘，向量加，指数运算，对数运算，大小比较等等。主要用于神经网络中非卷积/全连接层网络计算，如Batch Normalization(批归一化)，像素级求和，对特征平面进行上采样等。
在一些实现中，向量计算单元907能将经处理的输出的向量存储到统一存储器906。例如，向量计算单元907可以将线性函数；或，非线性函数应用到运算电路903的输出，例如对卷积层提取的特征平面进行线性插值，再例如累加值的向量，用以生成激活值。在一些实现中，向量计算单元907生成归一化的值、像素级求和的值，或二者均有。在一些实现中，处理过的输出的向量能够用作到运算电路903的激活输入，例如用于在神经网络中的后续层中的使用。
控制器904连接的取指存储器(instruction fetch buffer)909，用于存储控制器904使用的指令；
统一存储器906，输入存储器901，权重存储器902以及取指存储器909均为On-Chip存储器。外部存储器私有于该NPU硬件架构。
其中，上述任一处提到的处理器，可以是一个通用中央处理器，微处理器，ASIC，或一个或多个用于控制上述程序执行的集成电路。
另外需说明的是，以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际 的需要选择其中的部分或者全部模块来实现本实施例方案的目的。另外，本申请提供的装置实施例附图中，模块之间的连接关系表示它们之间具有通信连接，具体可以实现为一条或多条通信总线或信号线。
通过以上的实施方式的描述，所属领域的技术人员可以清楚地了解到本申请可借助软件加必需的通用硬件的方式来实现，当然也可以通过专用硬件包括专用集成电路、专用CPU、专用存储器、专用元器件等来实现。一般情况下，凡由计算机程序完成的功能都可以很容易地用相应的硬件来实现，而且，用来实现同一功能的具体硬件结构也可以是多种多样的，例如模拟电路、数字电路或专用电路等。但是，对本申请而言更多情况下软件程序实现是更佳的实施方式。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在可读取的存储介质中，如计算机的软盘、U盘、移动硬盘、ROM、RAM、磁碟或者光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本申请各个实施例所述的方法。
在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。
所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本申请实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(DSL))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存储的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，DVD)、或者半导体介质(例如固态硬盘(Solid State Disk，SSD))等。

Claims (19)

  1. 一种任务求解方法，其特征在于，所述方法包括：
    获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束；
    获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度；
    根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；
    根据所述多个第一规划约束的子集构建第二线性规划任务；
    对所述第二线性规划任务进行求解，得到第一求解结果；
    将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。
  2. 根据权利要求1所述的方法，其特征在于，所述第一线性规划任务和所述第二线性规划任务均包括规划目标。
  3. 根据权利要求1或2所述的方法，其特征在于，所述方法还包括：
    获取对所述第二线性规划任务进行求解的第一求解时间、以及对初始化后的所述第一线性规划任务进行求解的第二求解时间；
    对所述第一线性规划任务进行求解，得到求解所述第一线性规划任务的第三求解时间；
    根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性，其中，更新后的所述重要性与所述减少程度正相关。
  4. 根据权利要求3所述的方法，其特征在于，所述方法还包括：获取对所述多个第一规划约束进行采样的采样时间；
    所述根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性，包括：
    根据所述第一求解时间、所述第三求解时间以及所述采样时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性，以得到更新后的每个第一规划约束的重要性。
  5. 根据权利要求3或4所述的方法，其特征在于，所述方法还包括：
    获取第三线性规划任务，所述第三线性规划任务包括所述多个第二规划约束，所述多个第二规划约束和所述多个第一规划约束的约束类型相同；
    获取所述多个第二规划约束中每个第二规划约束的重要性，其中更新后的每个第一规划约束的重要性用于作为约束类型相同的第二规划约束的重要性；
    根据所述每个第二规划约束的重要性，对所述多个第二规划约束进行采样，以获取第 四线性规划任务，其中，所述每个第二规划约束的重要性用于确定第二规划约束的采样概率，所述第四线性规划任务包括所述多个第二规划约束中的部分第二规划约束；
    对所述第四线性规划任务进行求解，得到第三求解结果；
    将所述第三求解结果作为所述第三线性规划任务的初始值，并对初始化后的所述第三线性规划任务进行求解，得到第四求解结果。
  6. 根据权利要求1至5任一所述的方法，其特征在于，所述第二线性规划任务包括M个求解变量，所述第一求解结果包括各个求解变量的参数值；
    所述将所述第一求解结果作为所述第一线性规划任务的初始值，包括：
    将所述第一求解结果中各个求解变量的参数值作为所述第一线性规划任务中的M个求解变量的参数值。
  7. 根据权利要求1至6任一所述的方法，其特征在于，所述第一线性规划任务用于为至少一个待调度任务分配调度资源，所述第一规划约束为调度资源满足的约束，所述调度资源为生产线、生产设备或生产厂家。
  8. 根据权利要求1至7任一所述的方法，其特征在于，所述得到第二求解结果之后，所述方法还包括：
    获取第二规划约束，所述第二规划约束包括松弛变量以及所述松弛变量的上界；
    将所述第二规划约束增加至所述第一线性规划任务，以得到更新后的所述第一线性规划任务，并求解所述更新后的第一线性规划任务。
  9. 一种任务求解装置，其特征在于，所述装置包括：
    获取模块，用于获取第一线性规划任务，所述第一线性规划任务包括多个第一规划约束；
    获取所述多个第一规划约束中每个第一规划约束的重要性，所述重要性表示第一规划约束对于降低所述第一线性规划任务的求解时间的贡献程度；
    采样模块，用于根据所述重要性，对所述多个第一规划约束进行采样，以得到所述获取所述多个第一规划约束的子集，其中，所述重要性用于确定第一规划约束的采样概率；
    根据所述多个第一规划约束的子集构建第二线性规划任务；
    求解模块，用于对所述第二线性规划任务进行求解，得到第一求解结果；
    将所述第一求解结果作为所述第一线性规划任务的初始值，并对初始化后的所述第一线性规划任务进行求解，得到第二求解结果。
  10. 根据权利要求9所述的装置，其特征在于，所述第一线性规划任务和所述第二线性规划任务均包括规划目标。
  11. 根据权利要求9或10所述的装置，其特征在于，所述获取模块，还用于：
    获取对所述第二线性规划任务进行求解的第一求解时间、以及对初始化后的所述第一线性规划任务进行求解的第二求解时间；
    所述求解模块，还用于对所述第一线性规划任务进行求解，得到求解所述第一线性规划任务的第三求解时间；
    所述装置还包括：
    重要性更新模块，用于根据所述第一求解时间和所述第三求解时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性，其中，更新后的所述重要性与所述减少程度正相关。
  12. 根据权利要求11所述的装置，其特征在于，所述获取模块，还用于：
    获取对所述多个第一规划约束进行采样的采样时间；
    所述重要性更新模块，具体用于：
    根据所述第一求解时间、所述第三求解时间以及所述采样时间的加和，相对于所述第一求解时间的减少程度，更新所述每个第一规划约束的重要性。
  13. 根据权利要求11或12所述的装置，其特征在于，所述获取模块，还用于：
    获取第三线性规划任务，所述第三线性规划任务包括所述多个第二规划约束，所述多个第二规划约束和所述多个第一规划约束的约束类型相同；
    获取所述多个第二规划约束中每个第二规划约束的重要性，其中更新后的每个第一规划约束的重要性用于作为约束类型相同的第二规划约束的重要性；
    所述采样模块，还用于：
    根据所述每个第二规划约束的重要性，对所述多个第二规划约束进行采样，以获取第四线性规划任务，其中，所述每个第二规划约束的重要性用于确定第二规划约束的采样概率，所述第四线性规划任务包括所述多个第二规划约束中的部分第二规划约束；
    所述求解模块，还用于：
    对所述第四线性规划任务进行求解，得到第三求解结果；
    将所述第三求解结果作为所述第三线性规划任务的初始值，并对初始化后的所述第三线性规划任务进行求解，得到第四求解结果。
  14. 根据权利要求9至13任一所述的装置，其特征在于，所述第二线性规划任务包括M个求解变量，所述第一求解结果包括各个求解变量的参数值；
    所述求解模块，具体用于：
    将所述第一求解结果中各个求解变量的参数值作为所述第一线性规划任务中的M个求解变量的参数值。
  15. 根据权利要求9至14任一所述的装置，其特征在于，所述第一线性规划任务用于为 至少一个待调度任务分配调度资源，所述第一规划约束为调度资源满足的约束，所述调度资源为生产线、生产设备或生产厂家。
  16. 根据权利要求9至15任一所述的装置，其特征在于，所述获取模块，还用于：
    在所述得到第二求解结果之后，获取第二规划约束，所述第二规划约束包括松弛变量以及所述松弛变量的上界；
    所述求解模块，还用于将所述第二规划约束增加至所述第一线性规划任务，以得到更新后的所述第一线性规划任务，并求解所述更新后的第一线性规划任务。
  17. 一种计算机存储介质，其特征在于，所述计算机存储介质存储有一个或多个指令，所述指令在由一个或多个计算机执行时使得所述一个或多个计算机执行权利要求1-8中任一项所述方法的操作。
  18. 一种计算机程序产品，其特征在于，包括计算机可读指令，当所述计算机可读指令在计算机设备上运行时，使得所述计算机设备执行如权利要求1至8任一所述的方法。
  19. 一种系统，包括至少一个处理器，至少一个存储器以及至少一个通信接口；所述处理器、所述存储器和所述通信接口通过通信总线连接并完成相互间的通信；
    所述至少一个存储器用于存储代码；
    所述至少一个处理器用于执行所述代码，以执行如权利要求1-8任一所述的任务求解方法，以得到求解结果；
    所述至少一个通信接口，用于与设备或通信网络通信，以将所述求解结果发送至所述设备或通信网络。
PCT/CN2022/121620 2021-09-30 2022-09-27 一种任务求解方法及其装置 Ceased WO2023051505A1 (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP22874890.1A EP4394595A4 (en) 2021-09-30 2022-09-27 Job solving method and apparatus
US18/619,068 US20240242137A1 (en) 2021-09-30 2024-03-27 Task solving method and apparatus thereof

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN202111166727.3A CN114237835B (zh) 2021-09-30 2021-09-30 一种任务求解方法及其装置
CN202111166727.3 2021-09-30

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US18/619,068 Continuation US20240242137A1 (en) 2021-09-30 2024-03-27 Task solving method and apparatus thereof

Publications (1)

Publication Number Publication Date
WO2023051505A1 true WO2023051505A1 (zh) 2023-04-06

Family

ID=80743060

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2022/121620 Ceased WO2023051505A1 (zh) 2021-09-30 2022-09-27 一种任务求解方法及其装置

Country Status (4)

Country Link
US (1) US20240242137A1 (zh)
EP (1) EP4394595A4 (zh)
CN (1) CN114237835B (zh)
WO (1) WO2023051505A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN118038702A (zh) * 2024-03-11 2024-05-14 北京工业大学 混行场景下车道通行能力上下限计算与分析方法和系统

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114237835B (zh) * 2021-09-30 2025-12-02 华为技术有限公司 一种任务求解方法及其装置
CN116993063A (zh) * 2022-04-24 2023-11-03 华为技术有限公司 一种任务求解方法及其装置
CN114596012A (zh) * 2022-05-10 2022-06-07 支付宝(杭州)信息技术有限公司 用于资源调度的方法、系统、装置和介质
CN115796405B (zh) * 2023-02-03 2023-05-02 阿里巴巴达摩院(杭州)科技有限公司 针对优化模型的求解报告生成方法及计算设备
CN115829169B (zh) * 2023-02-10 2023-05-16 阿里巴巴达摩院(杭州)科技有限公司 基于混合整数线性规划的业务处理方法及装置
CN116341838A (zh) * 2023-02-23 2023-06-27 华为技术有限公司 一种计算机任务处理方法及其相关设备
US20250111308A1 (en) * 2023-09-29 2025-04-03 Ukg Inc. Workforce scheduling based on problem decomposition
CN118396291B (zh) * 2024-04-19 2025-02-28 深圳市金地物业管理有限公司 一种基于线性规划的保洁作业排程方法

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6336110B1 (en) * 1997-03-31 2002-01-01 Kabushiki Kaisha Toshiba System for solving of a constraint-satisfaction problem and constructing of a system
US20070198446A1 (en) * 2006-02-21 2007-08-23 Indraneel Das System and method for exploiting a good starting guess for binding constraints in quadratic programming with an infeasible and inconsistent starting guess for the solution
US20120127893A1 (en) * 2010-11-22 2012-05-24 May Patents Ltd. Apparatus and method for using and solving linear programming problem and applications thereof
CN114237835A (zh) * 2021-09-30 2022-03-25 华为技术有限公司 一种任务求解方法及其装置

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8412551B2 (en) * 2004-10-21 2013-04-02 Abb Research Ltd. Formal structure-based algorithms for large scale resource scheduling optimization
US9135581B1 (en) * 2011-08-31 2015-09-15 Amazon Technologies, Inc. Resource constrained task scheduling
CN104156508A (zh) * 2014-07-23 2014-11-19 国家电网公司 混合整数线性规划模型的求解方法
US10970682B1 (en) * 2015-06-04 2021-04-06 Incontact, Inc. System and method for agent scheduling using mixed integer linear programming
US10509654B2 (en) * 2017-08-09 2019-12-17 Red Hat, Inc. Multi-threaded constraint satisfaction solver
US11537995B2 (en) * 2019-02-01 2022-12-27 King Fahd University Of Petroleum And Minerals Method and system for cyclic scheduling
CN110334391B (zh) * 2019-05-23 2023-03-28 明阳智慧能源集团股份公司 一种多维度约束风电场集电线路自动规划方法

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6336110B1 (en) * 1997-03-31 2002-01-01 Kabushiki Kaisha Toshiba System for solving of a constraint-satisfaction problem and constructing of a system
US20070198446A1 (en) * 2006-02-21 2007-08-23 Indraneel Das System and method for exploiting a good starting guess for binding constraints in quadratic programming with an infeasible and inconsistent starting guess for the solution
US20120127893A1 (en) * 2010-11-22 2012-05-24 May Patents Ltd. Apparatus and method for using and solving linear programming problem and applications thereof
CN114237835A (zh) * 2021-09-30 2022-03-25 华为技术有限公司 一种任务求解方法及其装置

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
See also references of EP4394595A4
刘经德 (LIU, JINGDE): "面向复杂运算程序的符号执行搜索策略研究 (A Search Strategy for the Symbolic Execution of the Programs with Complex Computations)", 中国优秀硕士学位论文全文数据库信息科技辑 (INFORMATION & TECHNOLOGY, CHINA MASTER'S THESES FULL-TEXT DATABASE), 15 March 2017 (2017-03-15), ISSN: 1674-0246 *
隋建威 (SUI, JIANWEI): "面向软件完整路径的测试用例生成技术研究 (Research on Full-Path Test Case Generation Technology)", 中国优秀硕士学位论文全文数据库信息科技辑 (INFORMATION & TECHNOLOGY, CHINA MASTER'S THESES FULL-TEXT DATABASE), 15 May 2021 (2021-05-15), ISSN: 1674-0246 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN118038702A (zh) * 2024-03-11 2024-05-14 北京工业大学 混行场景下车道通行能力上下限计算与分析方法和系统

Also Published As

Publication number Publication date
EP4394595A4 (en) 2024-12-18
CN114237835A (zh) 2022-03-25
CN114237835B (zh) 2025-12-02
EP4394595A1 (en) 2024-07-03
US20240242137A1 (en) 2024-07-18

Similar Documents

Publication Publication Date Title
WO2023051505A1 (zh) 一种任务求解方法及其装置
CN111738488B (zh) 一种任务调度方法及其装置
Mishra et al. An adaptive task allocation technique for green cloud computing
US20220391260A1 (en) Method and Apparatus for Creating Container, Device, Medium, and Program Product
CN110389816B (zh) 用于资源调度的方法、装置以及计算机可读介质
CN113886080B (zh) 高性能集群任务调度方法、装置、电子设备及存储介质
CN112764893B (zh) 数据处理方法和数据处理系统
CN110609742A (zh) 一种Kubernetes调度器的队列的配置方法和装置
CN114610474B (zh) 一种异构超算环境下多策略的作业调度方法及系统
US12204934B2 (en) Method, device, and program product for managing multiple computing tasks based on batch
CN115880132A (zh) 图形处理器、矩阵乘法任务处理方法、装置及存储介质
Zhang et al. A resource optimization scheduling model and algorithm for heterogeneous computing clusters based on GNN and RL: Z. Zhang et al.
CN118626275B (zh) 异构计算资源虚拟化处理方法、电子设备和存储介质
CN118819903A (zh) 基于可视化建模与作业编排调度的数据分析方法及系统
CN106293947B (zh) 虚拟化云环境下gpu-cpu混合资源分配系统和方法
WO2025044621A1 (zh) 构建调度模型的方法和系统、调度目标任务的方法和系统
CN116880994B (zh) 基于动态dag的多处理器任务调度方法、装置及设备
CN115361285B (zh) 实现离在线业务混合部署的方法、装置、设备及介质
US20250053828A1 (en) Task solving method and apparatus thereof
CN118740844B (zh) 执行节点的确定方法和装置、存储介质及电子设备
CN114091807B (zh) 多无人机任务分配及调度方法、装置、系统及存储介质
CN117762583A (zh) 任务调度方法、装置、电子设备、存储介质
CN116643866A (zh) 作业调度处理方法、装置、芯片、存储介质和程序产品
CN116957311A (zh) 一种应急策略的智能分配方法及系统
CN110764886B (zh) 一种支持多分区处理的批量作业协同调度方法及系统

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 22874890

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2022874890

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 2022874890

Country of ref document: EP

Effective date: 20240328

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 11202402133T

Country of ref document: SG