DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
The Office Action is in response to claims filed 02/05/2024.
Claims 1-15 are pending.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: “data interface,” “processor subsystem,” and “output interface” in claims 10-14. Claims 11-14 also recite “the one or more systems for carrying out the one or more jobs.” Claim 14 also recites “the system is configured to autonomously schedule and carry out the jobs.” See MPEP § 2181(I)(A) “The following is a list of non-structural generic placeholders that may invoke 35 U.S.C. 112(f): "mechanism for," "module for," "device for," "unit for," "component for," "element for," "member for," "apparatus for," "machine for," or "system for."” Examiner notes that “interface” and “subsystem” are similar generic placeholders.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof. A review of the disclosure as originally filed , hereafter “disclosure”, reveals that the corresponding structure of the “data interface” and “output interface” is generic computer hardware (Page 12 Line 24-25 states “the data interface 120 may be constituted by a data storage interface.” Page 12 Line 27 – Page 13 Line 4 additionally states “the data storage interface 120 may be a memory interface or a persistent storage interface, e.g., a hard disk or an SSD interface, but also a personal, local or wide area network interface such as a Bluetooth, Zigbee or Wi-Fi interface or an ethernet or fibreoptic interface.” Page 15 Lines 11-13 additionally states “The output interface 180 may comprise data interface and/or a communication interface as described for the input interface 160.” See at least Pages 12-15 for more details). The disclosure also reveals that “processor subsystem” and “the system” are generic computing hardware (Page 16 Lines 1-4 states “the processor subsystem of the respective system may be embodied by a single Central Processing Unit (CPU), but also by a combination or system of such CPUs and/or other types of processing units.” See at least Pages 15-16 for more details). In accordance with MPEP § 2181(II)(B), when the corresponding structure of computer implemented mean plus function limitations corresponds to a general purpose computer, an algorithm is required to transform the general purpose computer into a special purpose computer to be sufficient as corresponding structure. Upon further review of the disclosure, Applicant has failed to define the algorithm for each of the claimed functions and has instead only provided either verbatim support for the claimed function (which is insufficient as a steps of steps of a corresponding algorithm) or exemplary language that does not make clear the metes and bounds of the algorithm. As such, see rejections under 35 U.S.C. § 112(a) and (b) below.
The disclosure also reveals that “the one or more systems for carrying out the one or more jobs" are physical machines, such as robots, autonomous vehicles, etcetera (Page 10 Lines 16-17 states “the systems for carrying out the jobs can be physical machines, such as robots, autonomous vehicles, etcetera”).
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claim 10-14 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention. Claims 10-14 recite “a data interface,” “a processor subsystem,” and “an output interface.” These recitations invoke 35 U.S.C. § 112(f), see claim interpretation above. The disclosure does not recite sufficient corresponding structure (in this instance computer + algorithm), again see claim interpretation above. As such, and in accordance with MPEP § 2181 (ll)(B), last paragraph "When a claim containing a computer-implemented 35 U.S.C. 112(f) claim limitation is found to be indefinite under 35 U.S.C. 112(b) for failure to disclose sufficient corresponding structure (e.g., the computer and the algorithm) in the specification that performs the entire claimed function, it will also lack written description under 35 U.S.C. 112(a)."
Claims 10-14 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim limitation “a data interface”, “a processor subsystem,” and “an output interface” invokes 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function. The disclosure fails to disclose sufficient corresponding structure (in this instance computer + algorithm), see claim interpretation above. As such, and in accordance with MPEP § 2181 (ll)(B) "For a computer-implemented 35 U.S.C. 112(f) claim limitation, the specification must disclose an algorithm for performing the claimed specific computer function, or else the claim is indefinite under 35 U.S.C. 112(b).". Therefore, the claim is indefinite and is rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112, second paragraph.
Applicant may:
(a) Amend the claim so that the claim limitation will no longer be interpreted as a limitation under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph;
(b) Amend the written description of the specification such that it expressly recites what structure, material, or acts perform the entire claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(c) Amend the written description of the specification such that it clearly links the structure, material, or acts disclosed therein to the function recited in the claim, without introducing any new matter (35 U.S.C. 132(a)).
If applicant is of the opinion that the written description of the specification already implicitly or inherently discloses the corresponding structure, material, or acts and clearly links them to the function so that one of ordinary skill in the art would recognize what structure, material, or acts perform the claimed function, applicant should clarify the record by either:
(a) Amending the written description of the specification such that it expressly recites the corresponding structure, material, or acts for performing the claimed function and clearly links or associates the structure, material, or acts to the claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(b) Stating on the record what the corresponding structure, material, or acts, which are implicitly or inherently set forth in the written description of the specification, perform the claimed function. For more information, see 37 CFR 1.75(d) and MPEP §§ 608.01(o) and 2181.
With regard to claims 12-14, the claims are indefinite because claim 12 recites “the systems” and claim 13 and 14 recite “the system.” Claim 11, from which claim 12-14 depend on, recites “a system,” “a job scheduling system,” and “one or more actual systems for carrying out the jobs.” It is unclear which systems claims 12-14 are referring to. Appropriate clarification correction is required.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-15 are rejected under 35 U.S.C. 101 because the claimed invention recites a judicial exception, an abstract idea, and it has not been integrated into practical application and the claims further do not recite significantly more than the judicial exception. Examiner has evaluated the claims under the framework provided in the 2019 Patent Eligibility Guidance published in the Federal Register 01/07/2019 and has provided such analysis below.
Step 1: Claims 1-9 are directed to a computer-implemented job scheduling method and fall within the statutory class of process. Claim 10 is directed to a job scheduling system and falls within the statutory class of machine. Claim 11 is directed to a system and falls within the statutory class of machine. Claim 15 is directed to a non-transitory computer readable medium and falls within the statutory class of articles of manufacture. Therefore, “Are the claims to a process, machine, manufacture or composition of matter?” Yes.
Step 2A Prong 1:
Claims 1, 10, 11, and 15: The limitations “determining an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system,” “applying a job scheduler to the augmented scheduling instance to obtain an augmented schedule,” and “determining an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule.” These limitations are considered a mental process because they involve steps of observing, evaluation, and forming a judgement. It is understood that these limitations are to be performed within a computer environment, however, it can also entirely be performed in the mind.
Therefore, Yes, claims 1, 10, 11, and 15 recite a judicial exception. Step 2A Prong 2 will evaluate whether the claims integrate the judicial exception into a practical application.
Step 2A Prong 2:
Claims 1, 10, 11, and 15: The judicial exception is not integrated into a practical application. Claims 1, 10, 11, and 15 recites the following additional elements – “obtaining data representing an actual scheduling instance, wherein the actual scheduling instance includes one or more jobs to be scheduled and one or more actual systems for carrying out the jobs” and “outputting data representing the actual schedule for carrying out the scheduled jobs.” These limitations are insignificant extra-solution activity of data gathering and transmission (MPEP § 2106.05(g)). Claims 10 and 11 additionally recites “a data interface configured for accessing data,” “a processor system configured to,” and “an output interface configured to output data.” In light of the 112(f) interpretation and associated 112(a) and 112(b) rejections, these limitations are considered generic computing components used as a means to apply an exception (MPEP § 2106.05(f)). Claim 15 additionally recites “A non-transitory computer-readable medium on which is stored instructions for job scheduling, the instructions, when executed by a processor system, causing the processor system to perform the following steps.” This limitation is also considered a generic computing component used as a means to apply the exception (MPEP § 2106.05(f)). Claim 11 additionally recites “the one or more systems for carrying out the one or more jobs.” In explained in the 112(f) interpretation, these systems are understood to be at least physical machines such as robots or autonomous vehicles. Therefore, the claim is interpreted as physical machines such as robots or autonomous vehicles performing the one or more jobs and is considered means to apply an exception (MPEP § 2106.05(f)). These additional elements do not integrate the judicial exception into practical application.
Therefore, “Do the claims recite additional elements that integrate the judicial exception in a practical application?” No, these additional elements do not integrate the abstract idea into a practical application and they do not impose any meaningful limits on practicing the abstract idea. The claim is directed to an abstract idea.
After having evaluated the inquiries set forth in Steps 2A Prong 1 and 2, it has been concluded that claims 1, 10, 11, and 15 not only recite a judicial exception but that the claims are directed to the judicial exception as the judicial exception has not been integrated into practical application.
Step 2B:
Claims 1, 10, 11, and 15: The claims do not include additional elements, alone or in combination, that are sufficient to amount to significantly more than the judicial exception. As discussed above, the additional elements only amount to insignificant extra-solution activity and means to apply an exception. When reevaluating the additional elements, alone or in combination, no inventive concept that amounts to significantly more was found. When reevaluating the insignificant extra-solution activities for an inventive concept that is significantly more, the claims do not add an inventive concept that is other than what is well understood, routine, and conventional in the field. MPEP § 2106.05(d)(II) lists that “Receiving or transmitting data over a network” is a well understood, routine, and conventional computer function. Obtaining data and outputting data is receiving and transmitting data over a network.
Therefore, “Do the claims recite additional elements that amount to significantly more than the judicial exception? No, these additional elements, alone or in combination, do not amount to significantly more than the judicial exception.
Having concluded analysis with in the provided framework, claims 1, 10, 11, and 15 do not recite eligible subject matter under 35 U.S.C. § 101.
With regard to claims 2, it recites “wherein the job scheduler is configured to perform an optimization that penalizes jobs for being scheduled to the virtual system.” This limitation is a mental process because it involves steps of observation and forming a judgement and it can be performed entirely in the mind. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 2 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 3, it recites “wherein the job scheduler is configured to optimize a hierarchical objective that primarily minimizes a cost of assigning jobs to the virtual system and secondarily minimizes a cost associated to the actual scheduling instance.” This limitation is a mental process because it involves steps of observation and forming a judgement and it can be performed entirely in the mind. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 3 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 4, it recites “wherein a cost of assigning a first job to the virtual system is different from a cost of assigning a second job to the virtual system.” This limitation further limits the mental process in claim 3 and is also considered as such. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 4 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 5 it recites “wherein the job scheduler is applied to the augmented scheduling instance after a failure to determine a schedule for the actual scheduling instance.” This limitation is a mental process because it involves steps of observation and forming a judgement and it can be performed entirely in the mind. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 5 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 6, it recites “wherein the actual schedule has a time window, and wherein the method further comprises, before an end of the time window, performing a re-scheduling of at least one unstarted job from the actual schedule.” This limitation is a mental process because it involves steps of observation and forming a judgement and it can be performed entirely in the mind. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 6 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 7, it recites “further comprising: maintaining a job queue and repeatedly scheduling jobs of the job queue; wherein jobs that are not scheduled in the actual schedule are kept in the job queue for a next scheduling.” This limitation is a mental process because it involves steps of observation and forming a judgement and it can be performed entirely in the mind. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 7 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 8, it recites “wherein applying the job scheduler includes representing the augmented scheduling instance as mathematical optimization problem of a given type, and applying a solver for the given type of mathematical optimization problem.” This limitation further limits the mental process in claim 1, so it also considered as such. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 8 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 9, it recites “wherein the type of mathematical optimization problems is a constraint program, or a mixed integer program, or a local search program.” This limitation further limits the mental process in claim 8, so it also considered as such. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim does not include any additional elements that integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the claim limitations, alone or in combination, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 9 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 12, it recites “wherein the systems for carrying out the jobs are physical machines.” This limitation is considered field of use/technological environment (MPEP § 2106.05(h)) because it limits what the systems are. It does not integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the field of use/technological environment, alone or in combination with other limitations, no inventive concept that amounts to significantly more was found. Therefore, the claims fail Step 2B. Therefore claim 12 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 13, it recites “wherein the system is a semiconductor fabrication plant.” This limitation is considered field of use/technological environment (MPEP § 2106.05(h)) because it limits what the system is. It does not integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the field of use/technological environment, alone or in combination with other limitations, no inventive concept that amounts to significantly more was found. Therefore, the claims fail Step 2B. Therefore claim 13 does not recite patent eligible subject matter under 35 U.S.C. 101.
With regard to claim 14, it recites “wherein the system is configured to autonomously schedule” This limitation is considered a mental process because scheduling can be performed entirely in the mind. Therefore, the claim recites a judicial exception and fails Step 2A Prong 1. The claim further recites “carry out the jobs.” This limitation is considered means to apply an exception (MPEP § 2106.05(f)). It does not integrate the judicial exception into a practical application, so the claim fails Step 2A Prong 2. When reevaluating the means to apply an exception, alone or in combination with other limitations, no inventive concept that amounts to significantly more was found. Therefore, the claim fails Step 2B. Therefore claim 14 does not recite patent eligible subject matter under 35 U.S.C. 101.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-2, 8, 10-12, and 15 is/are rejected under 35 U.S.C. 103 as being unpatentable over Ballantyne et al. Pat. No. US 20180143852 A1 (hereafter Ballantyne) in view of Hsu et al. Pat. No. US 20200159876 A1 (hereafter Hsu) and further in view of Lesaint et al. Pat. No. US 6578005 B1 (hereafter Lesaint).
With regard to claim 1, Ballantyne teaches a computer-implemented job scheduling method, comprising the following steps (¶ [0016] states “Various embodiments of methods and apparatus for managing the allocation of resources to be used to fulfill job requests submitted by clients of a batch job management service are described.”):
obtaining data representing an actual scheduling instance, wherein the actual scheduling instance includes one or more jobs to be scheduled and one or more actual systems for carrying out the jobs (¶ [0017] states “One or more scheduler instances (e.g., each comprising a respective thread or process) may be instantiated for the jobs of one or more queues of a client in one embodiment.” ¶ [0025] states “a given compute environment may represent a logical grouping of resources with associated constraints specified by a client. The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed” and “a given compute environment 212 may be used for executing jobs from several different queues 205 in the depicted embodiment, so that an m:n relationship may be said to exist between queues and compute environments. A given scheduler instance 210 may be configured to schedule the executions of the jobs of one or more queues 205 at the appropriate set of compute environments associated with the queues in the depicted embodiment.” Examiner’s Note: the computing environment, scheduler instances, job queues, and jobs are all part of the actual scheduling instance);
determining an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0025] states “The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed.” Examiner’s Note: virtual machines are a virtual system. The virtual system is for scheduling because it is used for scheduling tasks);
determining an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0053] states “As shown in element 801, at a batch job management service, compute environments, job queues, job definitions and resource definitions may be set up or established, e.g., in response to programmatic requests submitted via clients of the service.” ¶ [0058] states “At the resource controller, a selected optimization algorithm such as a largest-job-first bin-packing algorithm, may be used to map pending jobs to resources given the constraints imposed for example by the compute environment definitions indicated by the client (element 819).” See FIG. 8. Examiner’s Note: FIG. 8 is a process of determining a schedule);
outputting data representing the actual schedule for carrying out the scheduled jobs (¶ [0060] states “the scheduler may schedule pending jobs (if any) on currently allocated resources (element 825) and wait for the next event notification.” ¶ [0017] states “In various embodiments, the term “pending job” may be used to refer to a submitted job that has not yet been completed, e.g., either because it has not yet begun execution or because it has begun execution but has not yet completed execution.” Examiner’s Note: jobs are actually executed within the system, so the schedule must have been outputted).
Ballantyne does not explicitly teach an augmented scheduling instance.
However, in an analogous art, Hsu teaches determining an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0017] states “System Twin 7 can be established by integrating the digital twin models of the device network, human network, and smart network in the factory.” ¶ [0007] states “The storage stores a plurality of digital twin models, each of the digital twin models simulating one entity of the at least one production line.” ¶ [0027] states “In addition, since the digital twin model actually simulates the condition of the entity, according to the simulation results of the digital twin model (digital twin model, task twin model, etc.), the present invention can exclude the situation that some evaluations indicate the entity can be involved in the task but is impossible in the actual operation.” Examiner’s Note: the system twin and digital twins simulate the factory. The factory is analogous to the scheduling instance. Therefore, the system and digital twins are the augmented scheduling instance that is derived from the actual, or physical, system. By using digital twins, it is determined if a task is feasible and whether that task is excluded);
applying a job scheduler to the augmented scheduling instance to obtain an augmented schedule (¶ [0024] states “the processor 25 generates a plurality of task requirements according to the production specification and the production data, the task requirements indicate the needs of the production capacity to achieve the production specification.” ¶ [0032] states “the simulation device 2 generates a plurality of task requirements according to a production specification proposed by the customer and a production data.” ¶ [0036] states “the simulation device broadcasts the task requirements to each of the digital twin models that meets one of the task requirements, wherein each of the digital twin models generates a state report based on the received task requirements.” Examiner’s Note: the generated task requirements that are broadcasted to the digital twins are analogous to the augmented schedule. The simulation device is the job scheduler. The simulation device is applied to the augmented scheduling instance because the job scheduler generates the task requirements that are performed on digital twins);
determining an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0038] states “Thereafter, in step S307, the simulation device generates a plurality of simulation results according to the task twin models. Specifically, the simulation device determines if the production specification is feasible according to the task twin models. If the production specification is feasible, each of the simulation results is a simulated production line schedule, and the simulated production line schedule is at least one production line configuration corresponding to the production specification.” Examiner’s Note: the simulation production line schedule is the actual schedule. It is determined from the augmented schedule because it is determined from the simulation results which is determined from the task requirements, or augmented scheduled, that was sent to the digital twins).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the use of digital twins to determine task feasibility and a simulated production line schedule of Hsu with the scheduler instances of Ballantyne. As a result, the system and digital twins are copies of the computing environment and scheduler instances of Ballantyne. A person having ordinary skill in the art would have been motivated to make this combination for the purpose of improving the accuracy of scheduling decisions (¶ [0043] states “Since the digital twin model actually simulates the entity, the state of the entity can be evaluated more accurately. The simulation technology provided by the present invention generates task twin models by dynamically combining the digital twin models that can complete the task, and generates simulation results that can assist the decision maker to make a decision, so that the decision maker can predict the possible situation more accurately”).
Ballantyne and Hsu do not explicitly teach jobs not being executed on a virtual system.
However, in an analogous art, Lesaint teaches determining an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.” Examiner’s Note: the dummy technician is the virtual system. Scheduling tasks on the dummy technician is equivalent to deallocating a task. In other words, scheduling tasks on the dummy node is excluding that task from execution);
determining an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.”);
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the dummy technician with tasks that are not executed of Lesaint with the scheduling instances of Ballantyne and the digital twin task simulations of Hsu. As a result, the digital twins of Hsu are the augmented scheduling instances. The digital twins are simulations of the scheduling instances of Ballantyne. In the combination, the simulated computer environment and scheduling instances include the dummy technician of Lesaint. The dummy of Lesaint is represented by the virtual machine of Ballantyne. In the combination, when task requirements are being tested on the digital twins of Hsu, it is the schedule of Ballantyne that is being tested. During the simulation, if a task cannot be scheduled to digital twins, the task is scheduled to the virtual machine that is the dummy technician. The simulated production line schedule of Hsu does not include the tasks scheduled to the dummy technician because those tasks are infeasible.
A person having ordinary skill in the art would have been motivated to make this combination because the invention “allows the schedule generation process more time to generate each schedule, allowing it to generate a more optimal solution,” (Col. 4 Lines 18-20). Additionally, the invention “is particularly suited for use in situations where the availability of resources, and the tasks to be performed, both change dynamically” (Col. 1 Lines 11-14).
With regard to claim 2, Ballantyne, Hsu, and Lesaint teach the method of claim 1. Lesaint additionally teaches wherein the job scheduler is configured to perform an optimization that penalizes jobs for being scheduled to the virtual system (Col. 23 Lines 22-23 states “Deallocating a task (i.e. scheduling it to the dummy technician) will always increase the objective function.”).
With regard to claim 8, Ballantyne, Hsu, and Lesaint teach the method of claim 1. Hsu additionally teaches wherein applying the job scheduler includes representing the augmented scheduling instance as mathematical optimization problem of a given type, and applying a solver for the given type of mathematical optimization problem (¶ [0029] states “the processor 25 further optimizes the outcomes of the simulation results. Specifically, the processor 25 further receives a target demand which may be proposed by the decision maker, and the target demand includes at least one of a minimal total cost configuration, a maximum demand fulfillment configuration, and a maximum profit configuration. Based on the target demand, the processor 25 calculates a simulation result that best meets the target demand as an operational suggestion from the simulation results (i.e., at least one production line configuration).” ¶ [0030] states “the optimization can be implement by a decision matrix, numerical standardization, weighting, determining the optimal solution and the worst solution, distinguishing measures, and the approximate value of the optimal solution”).
With regard to claim 10, Ballantyne teaches a job scheduling system, comprising (¶ [0020] states “FIG. 1 illustrates an example system environment in which a resource controller may fulfill multi-dimensional resource requirements identified by event-driven schedulers for batch job processing, according to at least some embodiments.”):
a data interface configured for accessing data representing an actual scheduling instance, wherein the actual scheduling instance includes one or more jobs to be scheduled and one or more actual systems for carrying out the jobs (¶ [0077] states “In the illustrated embodiment, computing device 9000 includes one or more processors 9010 coupled to a system memory 9020 (which may comprise both non-volatile and volatile memory modules) via an input/output (I/O) interface 9030.” ¶ [0080] states “I/O interface 9030 may be configured to coordinate I/O traffic between processor 9010, system memory 9020, and any peripheral devices in the device, including network interface 9040 or other peripheral interfaces such as various types of persistent and/or volatile storage devices.” ¶ [0017] states “One or more scheduler instances (e.g., each comprising a respective thread or process) may be instantiated for the jobs of one or more queues of a client in one embodiment.” ¶ [0025] states “a given compute environment may represent a logical grouping of resources with associated constraints specified by a client. The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed” and “a given compute environment 212 may be used for executing jobs from several different queues 205 in the depicted embodiment, so that an m:n relationship may be said to exist between queues and compute environments. A given scheduler instance 210 may be configured to schedule the executions of the jobs of one or more queues 205 at the appropriate set of compute environments associated with the queues in the depicted embodiment.” Examiner’s Note: the computing environment, scheduler instances, job queues, and jobs are all part of the actual scheduling instance);
a processor subsystem configured to: determine an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0078] states “computing device 9000 may be a uniprocessor system including one processor 9010, or a multiprocessor system including several processors 9010.” ¶ [0025] states “The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed.” Examiner’s Note: virtual machines are a virtual system. The virtual system is for scheduling because it is used for scheduling tasks),
determine an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0053] states “As shown in element 801, at a batch job management service, compute environments, job queues, job definitions and resource definitions may be set up or established, e.g., in response to programmatic requests submitted via clients of the service.” ¶ [0058] states “At the resource controller, a selected optimization algorithm such as a largest-job-first bin-packing algorithm, may be used to map pending jobs to resources given the constraints imposed for example by the compute environment definitions indicated by the client (element 819).” See FIG. 8. Examiner’s Note: FIG. 8 is a process of determining a schedule);
and an output interface configured to output data representing the actual schedule for carrying out the scheduled jobs (¶ [0077] states “In the illustrated embodiment, computing device 9000 includes one or more processors 9010 coupled to a system memory 9020 (which may comprise both non-volatile and volatile memory modules) via an input/output (I/O) interface 9030.” ¶ [0080] states “I/O interface 9030 may be configured to coordinate I/O traffic between processor 9010, system memory 9020, and any peripheral devices in the device, including network interface 9040 or other peripheral interfaces such as various types of persistent and/or volatile storage devices.” ¶ [0060] states “the scheduler may schedule pending jobs (if any) on currently allocated resources (element 825) and wait for the next event notification.” Examiner’s Note: jobs are actually executed within the system, so the schedule must have been outputted).
Ballantyne does not explicitly teach an augmented scheduling instance.
However, in an analogous art, Hsu teaches a processor subsystem configured to: determine an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0017] states “System Twin 7 can be established by integrating the digital twin models of the device network, human network, and smart network in the factory.” ¶ [0007] states “The storage stores a plurality of digital twin models, each of the digital twin models simulating one entity of the at least one production line.” ¶ [0027] states “In addition, since the digital twin model actually simulates the condition of the entity, according to the simulation results of the digital twin model (digital twin model, task twin model, etc.), the present invention can exclude the situation that some evaluations indicate the entity can be involved in the task but is impossible in the actual operation.” Examiner’s Note: the system twin and digital twins simulate the factory. The factory is analogous to the scheduling instance. Therefore, the system and digital twins are the augmented scheduling instance that is derived from the actual, or physical, system. By using digital twins, it is determined if a task is feasible and whether that task is excluded),
apply a job scheduler to the augmented scheduling instance to obtain an augmented schedule (¶ [0024] states “the processor 25 generates a plurality of task requirements according to the production specification and the production data, the task requirements indicate the needs of the production capacity to achieve the production specification.” ¶ [0032] states “the simulation device 2 generates a plurality of task requirements according to a production specification proposed by the customer and a production data.” ¶ [0036] states “the simulation device broadcasts the task requirements to each of the digital twin models that meets one of the task requirements, wherein each of the digital twin models generates a state report based on the received task requirements.” Examiner’s Note: the generated task requirements that are broadcasted to the digital twins are analogous to the augmented schedule. The simulation device is the job scheduler. The simulation device is applied to the augmented scheduling instance because the job scheduler generates the task requirements that are performed on digital twins),
determine an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0038] states “Thereafter, in step S307, the simulation device generates a plurality of simulation results according to the task twin models. Specifically, the simulation device determines if the production specification is feasible according to the task twin models. If the production specification is feasible, each of the simulation results is a simulated production line schedule, and the simulated production line schedule is at least one production line configuration corresponding to the production specification.” Examiner’s Note: the simulation production line schedule is the actual schedule. It is determined from the augmented schedule because it is determined from the simulation results which is determined from the task requirements, or augmented scheduled, that was sent to the digital twins).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the use of digital twins to determine task feasibility and a simulated production line schedule of Hsu with the scheduler instances of Ballantyne. As a result, the system and digital twins are copies of the computing environment and scheduler instances of Ballantyne. A person having ordinary skill in the art would have been motivated to make this combination for the purpose of improving the accuracy of scheduling decisions (¶ [0043] states “Since the digital twin model actually simulates the entity, the state of the entity can be evaluated more accurately. The simulation technology provided by the present invention generates task twin models by dynamically combining the digital twin models that can complete the task, and generates simulation results that can assist the decision maker to make a decision, so that the decision maker can predict the possible situation more accurately”).
Ballantyne and Hsu do not explicitly teach jobs not being executed on a virtual system.
However, in an analogous art, Lesaint teaches a processor subsystem configured to: determine an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.” Examiner’s Note: the dummy technician is the virtual system. Scheduling tasks on the dummy technician is equivalent to deallocating a task. In other words, scheduling tasks on the dummy node is excluding that task from execution),
determine an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.”).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the dummy technician with tasks that are not executed of Lesaint with the scheduling instances of Ballantyne and the digital twin task simulations of Hsu. As a result, the digital twins of Hsu are the augmented scheduling instances. The digital twins are simulations of the scheduling instances of Ballantyne. In the combination, the simulated computer environment and scheduling instances include the dummy technician of Lesaint. The dummy of Lesaint is represented by the virtual machine of Ballantyne. In the combination, when task requirements are being tested on the digital twins of Hsu, it is the schedule of Ballantyne that is being tested. During the simulation, if a task cannot be scheduled to digital twins, the task is scheduled to the virtual machine that is the dummy technician. The simulated production line schedule of Hsu does not include the tasks scheduled to the dummy technician because those tasks are infeasible.
A person having ordinary skill in the art would have been motivated to make this combination because the invention “allows the schedule generation process more time to generate each schedule, allowing it to generate a more optimal solution,” (Col. 4 Lines 18-20). Additionally, the invention “is particularly suited for use in situations where the availability of resources, and the tasks to be performed, both change dynamically” (Col. 1 Lines 11-14).
With regard to claim 11, Ballantyne teaches a system, comprising: a job scheduling system including (¶ [0020] states “FIG. 1 illustrates an example system environment in which a resource controller may fulfill multi-dimensional resource requirements identified by event-driven schedulers for batch job processing, according to at least some embodiments.”):
a data interface configured for accessing data representing an actual scheduling instance, wherein the actual scheduling instance includes one or more jobs to be scheduled and one or more actual systems for carrying out the jobs (¶ [0077] states “In the illustrated embodiment, computing device 9000 includes one or more processors 9010 coupled to a system memory 9020 (which may comprise both non-volatile and volatile memory modules) via an input/output (I/O) interface 9030.” ¶ [0080] states “I/O interface 9030 may be configured to coordinate I/O traffic between processor 9010, system memory 9020, and any peripheral devices in the device, including network interface 9040 or other peripheral interfaces such as various types of persistent and/or volatile storage devices.” ¶ [0017] states “One or more scheduler instances (e.g., each comprising a respective thread or process) may be instantiated for the jobs of one or more queues of a client in one embodiment.” ¶ [0025] states “a given compute environment may represent a logical grouping of resources with associated constraints specified by a client. The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed” and “a given compute environment 212 may be used for executing jobs from several different queues 205 in the depicted embodiment, so that an m:n relationship may be said to exist between queues and compute environments. A given scheduler instance 210 may be configured to schedule the executions of the jobs of one or more queues 205 at the appropriate set of compute environments associated with the queues in the depicted embodiment.” Examiner’s Note: the computing environment, scheduler instances, job queues, and jobs are all part of the actual scheduling instance);
a processor subsystem configured to: determine an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0078] states “computing device 9000 may be a uniprocessor system including one processor 9010, or a multiprocessor system including several processors 9010.” ¶ [0025] states “The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed.” Examiner’s Note: virtual machines are a virtual system. The virtual system is for scheduling because it is used for scheduling tasks),
apply a job scheduler to the augmented scheduling instance to obtain an augmented schedule,
determine an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0053] states “As shown in element 801, at a batch job management service, compute environments, job queues, job definitions and resource definitions may be set up or established, e.g., in response to programmatic requests submitted via clients of the service.” ¶ [0058] states “At the resource controller, a selected optimization algorithm such as a largest-job-first bin-packing algorithm, may be used to map pending jobs to resources given the constraints imposed for example by the compute environment definitions indicated by the client (element 819).” See FIG. 8. Examiner’s Note: FIG. 8 is a process of determining a schedule);
and an output interface configured to output data representing the actual schedule for carrying out the scheduled jobs (¶ [0077] states “In the illustrated embodiment, computing device 9000 includes one or more processors 9010 coupled to a system memory 9020 (which may comprise both non-volatile and volatile memory modules) via an input/output (I/O) interface 9030.” ¶ [0080] states “I/O interface 9030 may be configured to coordinate I/O traffic between processor 9010, system memory 9020, and any peripheral devices in the device, including network interface 9040 or other peripheral interfaces such as various types of persistent and/or volatile storage devices.” ¶ [0060] states “the scheduler may schedule pending jobs (if any) on currently allocated resources (element 825) and wait for the next event notification.” Examiner’s Note: jobs are actually executed within the system, so the schedule must have been outputted).
the one or more systems for carrying out the one or more jobs (¶ [0024] states “Any desired combination of a wide variety of resources may be allocated or activated for clients' batch jobs in different embodiments, such as guest virtual machines instantiated at a virtualized computing service 170A, physical hosts or servers, storage devices of a storage service 170B, database instances, graphics processing devices (e.g., GPU-based appliances or virtual machine), appliances optimized for machine learning, program execution containers, and the like.”).
Ballantyne does not explicitly teach an augmented scheduling instance.
However, in an analogous art, Hsu teaches a processor subsystem configured to: determine an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0017] states “System Twin 7 can be established by integrating the digital twin models of the device network, human network, and smart network in the factory.” ¶ [0007] states “The storage stores a plurality of digital twin models, each of the digital twin models simulating one entity of the at least one production line.” ¶ [0027] states “In addition, since the digital twin model actually simulates the condition of the entity, according to the simulation results of the digital twin model (digital twin model, task twin model, etc.), the present invention can exclude the situation that some evaluations indicate the entity can be involved in the task but is impossible in the actual operation.” Examiner’s Note: the system twin and digital twins simulate the factory. The factory is analogous to the scheduling instance. Therefore, the system and digital twins are the augmented scheduling instance that is derived from the actual, or physical, system. By using digital twins, it is determined if a task is feasible and whether that task is excluded),
apply a job scheduler to the augmented scheduling instance to obtain an augmented schedule (¶ [0024] states “the processor 25 generates a plurality of task requirements according to the production specification and the production data, the task requirements indicate the needs of the production capacity to achieve the production specification.” ¶ [0032] states “the simulation device 2 generates a plurality of task requirements according to a production specification proposed by the customer and a production data.” ¶ [0036] states “the simulation device broadcasts the task requirements to each of the digital twin models that meets one of the task requirements, wherein each of the digital twin models generates a state report based on the received task requirements.” Examiner’s Note: the generated task requirements that are broadcasted to the digital twins are analogous to the augmented schedule. The simulation device is the job scheduler. The simulation device is applied to the augmented scheduling instance because the job scheduler generates the task requirements that are performed on digital twins),
determine an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0038] states “Thereafter, in step S307, the simulation device generates a plurality of simulation results according to the task twin models. Specifically, the simulation device determines if the production specification is feasible according to the task twin models. If the production specification is feasible, each of the simulation results is a simulated production line schedule, and the simulated production line schedule is at least one production line configuration corresponding to the production specification.” Examiner’s Note: the simulation production line schedule is the actual schedule. It is determined from the augmented schedule because it is determined from the simulation results which is determined from the task requirements, or augmented scheduled, that was sent to the digital twins).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the use of digital twins to determine task feasibility and a simulated production line schedule of Hsu with the scheduler instances of Ballantyne. As a result, the system and digital twins are copies of the computing environment and scheduler instances of Ballantyne. A person having ordinary skill in the art would have been motivated to make this combination for the purpose of improving the accuracy of scheduling decisions (¶ [0043] states “Since the digital twin model actually simulates the entity, the state of the entity can be evaluated more accurately. The simulation technology provided by the present invention generates task twin models by dynamically combining the digital twin models that can complete the task, and generates simulation results that can assist the decision maker to make a decision, so that the decision maker can predict the possible situation more accurately”).
Ballantyne and Hsu do not explicitly teach jobs not being executed on a virtual system.
However, in an analogous art, Lesaint teaches a processor subsystem configured to: determine an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.” Examiner’s Note: the dummy technician is the virtual system. Scheduling tasks on the dummy technician is equivalent to deallocating a task. In other words, scheduling tasks on the dummy node is excluding that task from execution),
determine an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.”).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the dummy technician with tasks that are not executed of Lesaint with the scheduling instances of Ballantyne and the digital twin task simulations of Hsu. As a result, the digital twins of Hsu are the augmented scheduling instances. The digital twins are simulations of the scheduling instances of Ballantyne. In the combination, the simulated computer environment and scheduling instances include the dummy technician of Lesaint. The dummy of Lesaint is represented by the virtual machine of Ballantyne. In the combination, when task requirements are being tested on the digital twins of Hsu, it is the schedule of Ballantyne that is being tested. During the simulation, if a task cannot be scheduled to digital twins, the task is scheduled to the virtual machine that is the dummy technician. The simulated production line schedule of Hsu does not include the tasks scheduled to the dummy technician because those tasks are infeasible.
A person having ordinary skill in the art would have been motivated to make this combination because the invention “allows the schedule generation process more time to generate each schedule, allowing it to generate a more optimal solution,” (Col. 4 Lines 18-20). Additionally, the invention “is particularly suited for use in situations where the availability of resources, and the tasks to be performed, both change dynamically” (Col. 1 Lines 11-14).
With regard to claim 12, Ballantyne, Hsu, and Lesaint teach the method of claim 11. Ballantyne additionally teaches wherein the systems for carrying out the jobs are physical machines (¶ [0025] states “a given compute environment may represent a logical grouping of resources with associated constraints specified by a client. The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed”).
With regard to claim 15, Ballantyne teaches a non-transitory computer-readable medium on which is stored instructions for job scheduling, the instructions, when executed by a processor system, causing the processor system to perform the following steps (¶ [0082] states “system memory 9020 may be one embodiment of a computer-accessible medium configured to store program instructions and data as described above for FIG. 1 through FIG. 10 for implementing embodiments of the corresponding methods and apparatus” and “a computer-accessible medium may include non-transitory storage media or memory media”):
obtaining data representing an actual scheduling instance, wherein the actual scheduling instance includes one or more jobs to be scheduled and one or more actual systems for carrying out the jobs (¶ [0017] states “One or more scheduler instances (e.g., each comprising a respective thread or process) may be instantiated for the jobs of one or more queues of a client in one embodiment.” ¶ [0025] states “a given compute environment may represent a logical grouping of resources with associated constraints specified by a client. The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed” and “a given compute environment 212 may be used for executing jobs from several different queues 205 in the depicted embodiment, so that an m:n relationship may be said to exist between queues and compute environments. A given scheduler instance 210 may be configured to schedule the executions of the jobs of one or more queues 205 at the appropriate set of compute environments associated with the queues in the depicted embodiment.” Examiner’s Note: the computing environment, scheduler instances, job queues, and jobs are all part of the actual scheduling instance);
determining an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0025] states “The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed.” Examiner’s Note: virtual machines are a virtual system. The virtual system is for scheduling because it is used for scheduling tasks);
determining an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0053] states “As shown in element 801, at a batch job management service, compute environments, job queues, job definitions and resource definitions may be set up or established, e.g., in response to programmatic requests submitted via clients of the service.” ¶ [0058] states “At the resource controller, a selected optimization algorithm such as a largest-job-first bin-packing algorithm, may be used to map pending jobs to resources given the constraints imposed for example by the compute environment definitions indicated by the client (element 819).” See FIG. 8. Examiner’s Note: FIG. 8 is a process of determining a schedule);
outputting data representing the actual schedule for carrying out the scheduled jobs (¶ [0060] states “the scheduler may schedule pending jobs (if any) on currently allocated resources (element 825) and wait for the next event notification.” ¶ [0017] states “In various embodiments, the term “pending job” may be used to refer to a submitted job that has not yet been completed, e.g., either because it has not yet begun execution or because it has begun execution but has not yet completed execution.” Examiner’s Note: jobs are actually executed within the system, so the schedule must have been outputted).
Ballantyne does not explicitly teach an augmented scheduling instance.
However, in an analogous art, Hsu teaches determining an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (¶ [0017] states “System Twin 7 can be established by integrating the digital twin models of the device network, human network, and smart network in the factory.” ¶ [0007] states “The storage stores a plurality of digital twin models, each of the digital twin models simulating one entity of the at least one production line.” ¶ [0027] states “In addition, since the digital twin model actually simulates the condition of the entity, according to the simulation results of the digital twin model (digital twin model, task twin model, etc.), the present invention can exclude the situation that some evaluations indicate the entity can be involved in the task but is impossible in the actual operation.” Examiner’s Note: the system twin and digital twins simulate the factory. The factory is analogous to the scheduling instance. Therefore, the system and digital twins are the augmented scheduling instance that is derived from the actual, or physical, system. By using digital twins, it is determined if a task is feasible and whether that task is excluded);
applying a job scheduler to the augmented scheduling instance to obtain an augmented schedule (¶ [0024] states “the processor 25 generates a plurality of task requirements according to the production specification and the production data, the task requirements indicate the needs of the production capacity to achieve the production specification.” ¶ [0032] states “the simulation device 2 generates a plurality of task requirements according to a production specification proposed by the customer and a production data.” ¶ [0036] states “the simulation device broadcasts the task requirements to each of the digital twin models that meets one of the task requirements, wherein each of the digital twin models generates a state report based on the received task requirements.” Examiner’s Note: the generated task requirements that are broadcasted to the digital twins are analogous to the augmented schedule. The simulation device is the job scheduler. The simulation device is applied to the augmented scheduling instance because the job scheduler generates the task requirements that are performed on digital twins);
determining an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (¶ [0038] states “Thereafter, in step S307, the simulation device generates a plurality of simulation results according to the task twin models. Specifically, the simulation device determines if the production specification is feasible according to the task twin models. If the production specification is feasible, each of the simulation results is a simulated production line schedule, and the simulated production line schedule is at least one production line configuration corresponding to the production specification.” Examiner’s Note: the simulation production line schedule is the actual schedule. It is determined from the augmented schedule because it is determined from the simulation results which is determined from the task requirements, or augmented scheduled, that was sent to the digital twins).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the use of digital twins to determine task feasibility and a simulated production line schedule of Hsu with the scheduler instances of Ballantyne. As a result, the system and digital twins are copies of the computing environment and scheduler instances of Ballantyne. A person having ordinary skill in the art would have been motivated to make this combination for the purpose of improving the accuracy of scheduling decisions (¶ [0043] states “Since the digital twin model actually simulates the entity, the state of the entity can be evaluated more accurately. The simulation technology provided by the present invention generates task twin models by dynamically combining the digital twin models that can complete the task, and generates simulation results that can assist the decision maker to make a decision, so that the decision maker can predict the possible situation more accurately”).
Ballantyne and Hsu do not explicitly teach jobs not being executed on a virtual system.
However, in an analogous art, Lesaint teaches determining an augmented scheduling instance from the actual scheduling instance, wherein the augmented scheduling instance includes a virtual system for scheduling one or more jobs that are infeasible at the one or more actual systems, wherein the virtual system does not correspond to a physical entity and jobs are not actually executed on the virtual system and jobs scheduled on the virtual system are excluded from execution when scheduled on the virtual system (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.” Examiner’s Note: the dummy technician is the virtual system. Scheduling tasks on the dummy technician is equivalent to deallocating a task. In other words, scheduling tasks on the dummy node is excluding that task from execution);
determining an actual schedule from the augmented schedule, wherein jobs that are scheduled on the virtual system in the augmented schedule, are not scheduled in the actual schedule (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 23 Lines 23-24 states “Deallocating a task (i.e. scheduling it to the dummy technician).” Col. 23 Lines 28-31 states “Note that there are no skill, time, or other constraints on allocating a task to the dummy technician--such an allocation is always feasible, but always increases the objective function.”);
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the dummy technician with tasks that are not executed of Lesaint with the scheduling instances of Ballantyne and the digital twin task simulations of Hsu. As a result, the digital twins of Hsu are the augmented scheduling instances. The digital twins are simulations of the scheduling instances of Ballantyne. In the combination, the simulated computer environment and scheduling instances include the dummy technician of Lesaint. The dummy of Lesaint is represented by the virtual machine of Ballantyne. In the combination, when task requirements are being tested on the digital twins of Hsu, it is the schedule of Ballantyne that is being tested. During the simulation, if a task cannot be scheduled to digital twins, the task is scheduled to the virtual machine that is the dummy technician. The simulated production line schedule of Hsu does not include the tasks scheduled to the dummy technician because those tasks are infeasible.
A person having ordinary skill in the art would have been motivated to make this combination because the invention “allows the schedule generation process more time to generate each schedule, allowing it to generate a more optimal solution,” (Col. 4 Lines 18-20). Additionally, the invention “is particularly suited for use in situations where the availability of resources, and the tasks to be performed, both change dynamically” (Col. 1 Lines 11-14).
Claim(s) 3-4, 9, 13-14 is/are rejected under 35 U.S.C. 103 as being unpatentable over Ballantyne in view of Hsu and Lesaint and further in view of Xenos et al. Pat. No. US 20250085698 A1 (hereafter Xenos).
With regard to claim 3, Ballantyne, Hsu, and Lesaint teach the method of claim 2. Ballantyne additionally teaches wherein the job scheduler is configured to optimize a hierarchical objective that primarily minimizes a cost of assigning jobs to the virtual system and secondarily minimizes a cost associated to the actual scheduling instance (¶ [0017] states “One or more scheduler instances (e.g., each comprising a respective thread or process) may be instantiated for the jobs of one or more queues of a client in one embodiment.” ¶ [0025] states “a given compute environment may represent a logical grouping of resources with associated constraints specified by a client. The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed”).
Lesaint additionally teaches wherein the job scheduler is configured to optimize a hierarchical objective that primarily minimizes a cost of assigning jobs to the virtual system and secondarily minimizes a cost associated to the actual scheduling instance (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.” Col. 16 Lines 1-3 states “The function of the optimising subsystem 31 is to produce a set of tours for the technicians which minimises the objective cost function.” Col. 8 Lines 18-23 states “The method calculates a time-dependent "cost function" for each task. This takes into account the penalty for failing to meet an agreed time. The penalty may be a real monetary cost if compensation is payable to a customer for failures to meet a time, or a `virtual` cost; e.g. damage to a company's reputation.” Examiner’s Note: the tasks are actually performed belong to the actual scheduling instance. Since these tasks have costs, the actual scheduling system also has a cost).
Ballantyne, Hsu, and Lesaint do not explicitly teach a hierarchical objective.
However, in an analogous art, Xenos teaches wherein the job scheduler is configured to optimize a hierarchical objective that primarily minimizes a cost of assigning jobs to the virtual system and secondarily minimizes a cost associated to the actual scheduling instance (¶ [0216] states “in this embodiment the objective function is modified to be hierarchical such that: it optimises a first objective f.sub.1(x) only; then it optimises the second objective f.sub.2(x) such that f.sub.1(x) does not worsen by μ % (typically 0-10%).” ¶ [0175] states “The aim of at least some embodiments is to minimise any or any combination of: the total weighted batching costs; queuing time; and the number of violations of time link constraints.” ¶ [0197] states “The described embodiment therefore presents a method of batch scheduling with different batch costs and job time link constraints in a multi-objective approach. Specifically, the described embodiment considers different batching costs.”).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the hierarchical objective function to optimize multiple objective functions of Xenos with the optimization of an objective cost function by minimizing of Lesaint, the scheduling instances of Ballantyne, and the digital twin task requirement simulation of Hsu. As a result, tasks that are assigned to actual physical resources or the virtual system have a cost. In the combination, the objective function of assigning tasks to physical resources is different from the objective function of assigning tasks to the virtual system. Both are optimized according to the hierarchical optimization of Xenos. A person having ordinary skill in the art would have been motivated to make this combination because “This is especially useful when dealing with different orders of magnitude in the objective terms of considerably different coefficients because only one sub-problem is considered at a time. This further enables us to model the time link constraints via an objective function penalty term and once the number of time links has been minimised without considering any confounding KPIs, the remaining terms can be optimised given that number of time link violations” (¶ [0216]). The teachings of Xenos are for the purpose of “to utilise as many machines as fully as possible to optimise efficiency” (¶ [0008]).
With regard to claim 4, Ballantyne, Hsu, Lesaint, and Xenos teach the method of claim 3. To reestablish the teaching, Ballantyne teaches a virtual system (¶ [0025] states “a given compute environment may represent a logical grouping of resources with associated constraints specified by a client. The resources of a given compute environment may in effect represent placeholders in the depicted embodiment, for which corresponding actual resources (such as virtual or physical machines or devices) may be allocated as and when needed”) and Lesaint teaches a virtual system (Col. 9 Lines 17-22 states “The cost of not allocating a task must also be considered, and this is done by including a non-existent, or "dummy" technician. Other things being equal, if there are more tasks than resources to perform them, the lowest priority task would be scheduled for the dummy technician.”).
Xenos additionally teaches wherein a cost of assigning a first job to the virtual system is different from a cost of assigning a second job to the virtual system (¶ [0173] states “In these embodiments, batches have different operating costs and consecutive steps of a job are constrained with time links.”).
With regard to claim 9, Ballantyne, Hsu, and Lesaint teach the method of claim 8. Ballantyne, Hsu, and Lesaint do not explicitly teach that the mathematical optimization problems are either a constraint program, mixed integer program, or a local search program.
However, in an analogous art, Xenos teaches wherein the type of mathematical optimization problems is a constraint program, or a mixed integer program, or a local search program (¶ [0051] states “the one or more predictive models comprise any or any combination of: a mixed integer linear programming model; heuristics; complex flexible job-shop-scheduling problem with time link constraints model; integer programming model; metaheuristics; mixed integer programming model; genetic algorithm; simulated annealing; greedy randomised adaptive search procedure; constraint programming model; Monte Carlo methods; multivariate predictive models; relaxed mixed integer linear programming model.” Examiner’s Note: simulated annealing is a type of local search program).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the predictive models of Xenos with the optimization of simulated results of Hsu, the scheduling instances of Ballantyne, and the dummy technician of Lesaint. A person having ordinary skill in the art would have been motivated to make this combination because “A variety of models/techniques can be used to provide a substantially optimal schedule for the manufacturing facility” (¶ [0052]). Additionally, combining predictive model strategies can lead to improvements in scheduling (¶ [0026] states “A two-stage solution strategy combining mixed integer linear programming (MILP) models and heuristics can provide substantially significant improvements in scheduling”).
With regard to claim 13, Ballantyne, Hsu, and Lesaint teach the method of claim 12. Ballantyne, Hsu, and Lesaint do not explicitly teach that the system is a semiconductor fabrication plant.
However, in an analogous art, Xenos teaches wherein the system is a semiconductor fabrication plant (¶ [0009] states “Aspects and/or embodiments seek to provide a method and system of generating scheduling data that can be used in complex manufacturing settings such as semiconductor wafer fabrication plants”).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the environment of semiconductor wafer fabrication plants of Xenos with the scheduling instances of Ballantyne, the digital twins to simulate task requirements of Hsu, and the dummy technicians of Lesaint. A person having ordinary skill in the art would have been motivated to make this combination for the purpose of “enables generation of optimal and efficiency manufacturing scheduling data for the manufacture of complex products across a wide variety of industries” (¶ [0013]).
With regard to claim 14, Ballantyne, Hsu, and Lesaint teach the method of claim 11. Ballantyne, Hsu, and Lesaint do not explicitly teach the system is configured to autonomously schedule and carry out the jobs.
However, in an analogous art, Xenos teaches wherein the system is configured to autonomously schedule and carry out the jobs (¶ [0084] states “the communication means comprises means to transmit control signals 9, wherein the control signals automatically operate the machines in the groups of machines in accordance with the schedule for the group of machines and/or wherein the control signals automatically operate processes in the factory to enable the machines to operate in accordance with the schedule for the group of machines.” ¶ [0219] states “Automation: The solution of this embodiment is deployed in a live application where the time available for decision making and human interventions is limited, therefore relevant objective preferences should be set up-front and optimised accordingly.”).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the autonomous factory of Xenos with the scheduling instances of Ballantyne, the simulations of task requirements using digital twins of Hsu, and the dummy technician of Lesaint. A person having ordinary skill in the art would have been motivated to make this combination for the purpose of “[enabling] generation of optimal and efficiency manufacturing scheduling data for the manufacture of complex products across a wide variety of industries” (¶ [0013]). One of ordinary skill in the art would also recognize the benefits of automation such as limiting errors associated with manual steps and reproducibility.
Claim(s) 5 is/are rejected under 35 U.S.C. 103 as being unpatentable over Ballantyne in view of Hsu and Lesaint and further in view of Zweben et al. Pat. No. US 6216109 B1 (hereafter Zweben).
With regard to claim 5, Ballantyne, Hsu, and Lesaint teach the method of claim 1. Hsu additionally teaches wherein the job scheduler is applied to the augmented scheduling instance after a failure to determine a schedule for the actual scheduling instance (¶ [0024] states “the processor 25 generates a plurality of task requirements according to the production specification and the production data, the task requirements indicate the needs of the production capacity to achieve the production specification.” ¶ [0032] states “the simulation device 2 generates a plurality of task requirements according to a production specification proposed by the customer and a production data.” ¶ [0036] states “the simulation device broadcasts the task requirements to each of the digital twin models that meets one of the task requirements, wherein each of the digital twin models generates a state report based on the received task requirements.” Examiner’s Note: the generated task requirements that are broadcasted to the digital twins are analogous to the augmented schedule. The simulation device is the job scheduler. The simulation is applied to the augmented scheduling instance because the job scheduler generates the task requirements that are performed on digital twins).
Ballantyne, Hsu, and Lesaint do not explicitly teach the job scheduling being applied to the augmented scheduling instance after a failure to determine a schedule.
However, in an analogous art, Zweben additionally teaches wherein the job scheduler is applied to the augmented scheduling instance after a failure to determine a schedule for the actual scheduling instance (Col. 10 Lines 11-17 states “The initial schedule stored on the memory device 110 can be determined in any desired manner. For example, the initial schedule could be determined using another scheduling method, e.g., a critical path method such as PERT-CPM (which schedules using only temporal constraints), a constructive method, or a manufacturing resource planning (MRPII) method.” Col. 10 Lines 30-31 states “The initial schedule can violate the established constraints to any degree.” Col. 11 Lines 4-8 states “In step 202, as part of calculating an overall score for the schedule, the method 200 determines for each constraint, by evaluating a penalty function for the constraint (described in more detail below), whether the constraint was violated and, if so, the degree of the violation.” Col. 10 Lines 54-62 states “The score is compared to a pre-established threshold score. The threshold score represents the degree of violation of the constraints that is deemed acceptable. The threshold score can be established so that no constraint violations are allowed. Based upon the comparison of the score to the threshold score (and certain other considerations described more fully below), the system 100 determines whether it is necessary to produce a revised schedule.” Col. 11 Lines 32-33 states “In step 204, a new schedule is determined using schedule modifications made by the individual constraint repairs.” Examiner’s Note: the initial scheduler is analogous to the schedule for the actual scheduling instance. A cost score is calculated for the initial schedule and is based off of the degree of constraint violation within the initial schedule. The score is then compared to a preestablished threshold score. If the score is determined to be unacceptable when compared to the threshold, that is the failure of determining a schedule for the actual scheduling instance. A new schedule is then made).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the initial schedule generation and repair of Zweben with sending task requirement to digital twins to create a schedule of Hsu, the scheduling instances of Ballantyne, and the dummy technician of Lesaint. In the combination of Zweben and Hsu, repairing the initial schedule to create a new schedule is analogous to sending the task requirements to the digital twins. In the combination of Ballantyne, Hsu, Lesaint, and Zweben, it is the schedule of Ballantyne and Zweben that is sent to the digital twins.
A person having ordinary skill in the art would have been motivated to make this combination for the purpose of improving scheduling by rescheduling tasks only where needed which has performance improvement (Col. 6 Line 63 – Col. 7 Line 3 states “If all tasks are rescheduled, the rescheduling process takes too long. If only some of the tasks are rescheduled, tasks that are removed may not necessarily be the best tasks to remove and reschedule. The iterative repair method solves this problem by changing the schedule only where constraint violations occur and in a manner that can vary with the nature of the violation (i.e., tasks can be rescheduled, added and/or removed).”). Other benefits include improved scheduling for over-constrained scheduling problems, more accurate use of global constraints, and improved flexibility of the scheduling system (see at least Col. 7 Lines 4-67).
Claim(s) 6 is/are rejected under 35 U.S.C. 103 as being unpatentable over Ballantyne in view of Hsu and Lesaint and further in view of Davis Pat. No. US 20140108078 A1 (hereafter Davis).
With regard to claim 6, Ballantyne, Hsu, and Lesaint teach the method of claim 1. Lesaint additionally teaches wherein the actual schedule has a time window, and wherein the method further comprises, before an end of the time window, performing a re-scheduling of at least one unstarted job from the actual schedule (Col. 18 Lines 46-48 teaches “A task's time window is defined as the time between the task's earliest start time (EST) and latest start time (LST).” Examiner’s Note: the schedule’s time window would be based on the first task’s earliest start time and the last task’s latest start time because that window would be the schedule’s window for a schedule with one task).
Although Lesaint mentions rescheduling (Col. 13 Line 66 – Col 14 Line 4), Ballantyne, Hsu, and Lesaint do not explicitly teach rescheduling tasks before the end of a time window.
However, in an analogous art, Davis teaches wherein the actual schedule has a time window, and wherein the method further comprises, before an end of the time window, performing a re-scheduling of at least one unstarted job from the actual schedule (¶ [0112] states “In the context of rescheduling "anchor" may further refer to a specified time, or time range, or set of constraints for performance of a task.” ¶ [0126] states “Adjustments made by the schedule management module 1324 to a task's scheduled time may be made automatically at any time provided the changes are within the anchor associated with the task, “ and “a first task may have an anchor that may be a time range of 8 AM to 12 PM and a second task may have an anchor of 9 AM to 1 PM. If the first task were to be rescheduled, the rescheduled time may fall within the first task's anchor, sometime between 8 AM to 12 PM. Thus, if the first task is rescheduled for 9 AM, the rescheduled time range for the task falls within the first task's anchor (i.e., 8 AM to 12 PM). The second task may have been scheduled for 9 AM, but now may need to be adjusted to accommodate the rescheduled first task. Because the first task may take an hour to perform, and the travel time between the first task and the second task may be 18 minutes, the second task's time range may be moved to 10:18 AM, which may be within the second task's anchor of 9 AM to 1 PM.” ¶ [0059] states “One or more of the scheduled tasks may be cancelled and may be rescheduled for a new day and time.” Examiner’s Note: it is understood the rescheduling of the first and/or second task occurs before the job has been started. Even if the first task was rescheduled by means of cancelling, the rescheduling of the second task would still be before the second task started, so the second task would be an unstarted job).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the rescheduling of tasks based on anchors and resolving scheduling conflicts of Davis with the task time windows of Lesaint, the scheduling instances of Ballantyne and the digital twin task simulation of Hsu. A person having ordinary skill in the art would have been motivated to make this combination for “for efficiently scheduling tasks via a networked computing system. More accurate and efficient scheduling and rescheduling of services may allow the services to be priced and delivered in a more uniform fashion, improve the profitability of the service provider, decrease the cost to the customer, increase the quality and timeliness of the service provided, and/or allow the service provider to provide more services to more customers in the same amount of time” (¶ [0024]).
Claim(s) 7 is/are rejected under 35 U.S.C. 103 as being unpatentable over Ballantyne in view of Hsu and Lesaint and further in view of Markov Pat. No. US 20080066070 A1 (hereafter Markov).
With regard to claim 7, Ballantyne, Hsu, and Lesaint teach the method of claim 1. Ballantyne additionally teaches further comprising: maintaining a job queue and repeatedly scheduling jobs of the job queue (¶ [0017] states “The schedulers set up for the client may, at various points in time and under various triggering conditions, examine the pending jobs in a given queue” and “the term “pending job” may be used to refer to a submitted job that has not yet been completed, e.g., either because it has not yet begun execution or because it has begun execution but has not yet completed execution.” ¶ [0060] states “the scheduler may schedule pending jobs (if any) on currently allocated resources (element 825) and wait for the next event notification. When the next event notification is received, operations corresponding to elements 807 onwards may be repeated in the depicted embodiment.”);
Ballantyne, Hsu, and Lesaint do not explicitly state that unscheduled jobs are kept in the job queue.
However, in an analogous art, Markov teaches wherein jobs that are not scheduled in the actual schedule are kept in the job queue for a next scheduling (¶ [0031] states “the maximum capacity of the resources may be met or exceeded before all of the non-running jobs are scheduled. The remaining, unscheduled, non-running jobs may remain in the queue (e.g., Processed Job Queue (105) in FIG. 1) until the next scheduling iteration.”).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date to combine the unscheduled jobs remaining in the job queue of Markov with the job queue and scheduler of Ballantyne, the simulation of task requirements on digital twins of Hsu, and the dummy technician of Lesaint. A person having ordinary skill in the art would have been motivated to make this combination “to dynamically schedule submitted jobs using a trigger threshold and priority values” (¶ [0014]). Additionally, ¶ [0030] teaches “The scheduling of jobs may continue until it is ensured that no resources are idle during the upcoming execution interval.” One of ordinary skill in the art would recognize the benefit of maximizing resource utilization to complete as many jobs as possible.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
US 20230071370 A1
teaches
SYSTEMS AND METHODS FOR DYNAMIC TASK SCHEDULING AND RESCHEDULING USING HETEROGENEOUS MULTI-AGENT FLEET
US 20080040190 A1
teaches
Method, System, And Computer Program Product For Multi-mission Scheduling
US 20230088693 A1
teaches
Part Supply System And Method For Operating Part Supply System
US 20180103116 A1
teaches
Systems And Methods For Resource Allocation For Management Systems
US 5963911 A
teaches
Resource Allocation
Any inquiry concerning this communication or earlier communications from the examiner should be directed to PETER L YUAN whose telephone number is (571)272-5737. The examiner can normally be reached Mon-Fri 7:30am-5pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Bradley Teets can be reached at 571-272-3338. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/PETER LI YUAN/Examiner, Art Unit 2197
/BRADLEY A TEETS/Supervisory Patent Examiner, Art Unit 2197
Prosecution Insights