DETAILED ACTION
This communication is a Non-Final Office Action rejection on the merits. Claims 1-18 are currently pending and have been addressed below.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Information Disclosure Statement (IDS)
The information disclosure statement(s) filed on 06/06/2024 comply with the provisions 37 CFR 1.97, 1.98, and MPEP 609 and is considered by the Examiner.
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-18 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., an abstract idea) without reciting significantly more.
Independent Claim 1
Step One - First, pursuant to step 1 in the January 2019 Revised Patent Subject Matter Eligibility Guidance (“2019 PEG”) on 84 Fed. Reg. 53, the claim 1 is directed to an apparatus which is a statutory category.
Step 2A, Prong One - Claim 1 recites: A shift generation system that accepts a shift condition and member information, generates a shift for a member based on the shift condition and the member information, evaluates an achievement state of the shift condition for the generated shift, predicts an effect of a change in the shift condition on the evaluation, and presents the predicted effect. These claim elements are considered to be abstract ideas because they are directed to “certain methods of organizing human activity” which include “managing interactions between people.” In this case, generating a shift based on a predicted effect of a change in the shift condition is a social activity. If a claim limitation, under its broadest reasonable interpretation, covers managing interactions between people, then it falls within the “certain methods of organizing human activity” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
Step 2A Prong 2 - The judicial exception is not integrated into a practical application. Claim 1 includes additional elements: a hardware processor.
The hardware processor is merely used to accept a shift condition and member information, generate a shift for a member based on the shift condition and the member information, evaluate an achievement state of the shift condition for the generated shift, predicts an effect of a change in the shift condition on the evaluation, and present the predicted effect (Paragraph 0009). Merely stating that the step is performed by a computer component results in “apply it” on a computer (MPEP 2106.05f). This element of “processor” is recited at a high level of generality such that it amounts no more than mere instructions to apply the exception using a generic computer element. Also, the processor is considered “field of use” since it’s just used to receive inputs and provide information for a predicted effect, but the technology is not improved (MPEP 2106.05h). Accordingly, alone and in combination, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. Therefore, the claim is directed to an abstract idea.
Step 2B - The claim does not include additional elements that are sufficient to amount significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the claims describe how to generally “apply” the concept of generating a shift based on a predicted effect of a change in the shift condition. The specification shows that the hardware processor is merely used to accept a shift condition and member information, generate a shift for a member based on the shift condition and the member information, evaluate an achievement state of the shift condition for the generated shift, predicts an effect of a change in the shift condition on the evaluation, and present the predicted effect (Paragraph 0009). Further, the step of “present the predicted effect” is considered a well-understood, routine, and conventional function since it's just “receiving or transmitting data over a network” (MPEP 2106.05(d)). Thus, nothing in the claim adds significantly more to the abstract idea. The claim is ineligible.
Independent claim 7 is directed to a method at step 1, which is a statutory category. Claim 7 recites similar limitations as claim 1 and is rejected for the same reasons at step 2a, prong one; step 2a, prong 2; and step 2b. Claim 7 does not recite any additional elements to consider under step 2A prong 2 and step 2B. Therefore, viewed as a whole, the claim does not provide meaningful limitations to transform the abstract idea into a patent eligible application of the abstract idea such that the claims amount to significantly more than the abstract idea itself. The claim is ineligible.
Independent claim 13 is directed to an article of manufacture at step 1, which is a statutory category. Claim 13 recites similar limitations as claim 1 and is rejected for the same reasons at step 2a, prong one; step 2a, prong 2; and step 2b. Claim 13 further recites: a non-transitory recording medium – which is treated as just an explicit “processor/computer” for storing and executing the operations and is treated under MPEP 2106.05f in the same manner as claim 1. Accordingly, this additional element is viewed as “apply it on a computer” at step 2a, prong 2 and step 2b.
Dependent claims 2-3, 6, 8-9, 12, 14-15, and 18 are not directed to any additional claim elements. Rather, these claims offer further descriptive functions of elements found in the independent claims and addressed above - such as wherein the hardware processor is used to: evaluate an achievement state by limiting the shift conditions to any one of the shift conditions of which the evaluated achievement states do not satisfy a predetermined criterion. In this case, the main functions are merely used to: collect data (e.g., specify limited shift conditions) and analyze the data (e.g., whether there’s an improvement when the shift conditions are limited). Those are functions that the courts have described as merely indicating a field of use or technological environment in which to apply a judicial exception (see MPEP 2106.05(h)). Mere instructions to apply an exception using a generic computer component cannot provide an inventive concept. Thus, nothing in the claim adds significantly more to the abstract idea. The claim is ineligible.
Dependent claims 4-5, 10-11, and 16-17 are directed to an additional element such as: a genetic algorithm. The genetic algorithm is merely used to generate a plurality of shifts based on set shift conditions (Paragraph 0040). Merely stating that the step is performed by a computer component (e.g., genetic algorithm) results in “apply it” on a computer (MPEP 2106.05f) being applicable at both Step 2A, Prong 2 and Step 2B. Mere instructions to apply an exception using a generic computer component cannot provide an inventive concept. Thus, nothing in the claim adds significantly more to the abstract idea. The claim is ineligible.
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.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-3, 6-9, 12-15, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Yang (US 11948106 B1), in view of DeSilva et al. (US 2005/0004828 A1).
Regarding claim 1, Yang discloses a shift generation system comprising a hardware processor that accepts a shift condition and member information (Figure 2, item 208, processor; Column 3, lines 34-41, A system for simultaneous shift design and shift assignment transforms input data to determine an appropriate optimization problem. The optimization problem is concerned about making a set of related decisions in such a way that a set of given constraints are satisfied and a utility function (called the objective function) is optimized (e.g., either minimized or maximized depending on the type of the objective function); Column 4, lines 25-49, The scheduling engine determines the optimal schedule by … (4) transforming input data to determine a set of constraints using the decision variables wherein the set of constraints is built based on a set of conditions/restrictions that are to be respected while determining the optimal schedule (e.g., the labor demands need to be met, worker's availability and qualification should be respected, two shifts assigned to one worker cannot overlap, the budget should be respected, etc.); Column 6, lines 52-57, A generated shift candidate is subject to labor law legal constraints, union contract constraints, company policy constraints, etc. For example, a union contract can dictate that the duration of a shift has to be between four and nine hours, or a state law can require a half hour unpaid meal break for every 5 hours consecutive work; Examiner interprets “worker’s qualification” as the “member information.” Also, Examiner interprets the “union contract” as the “shift condition”), generates a shift for a member based on the shift condition and the member information (Column 7, lines 20-45, The next step for the Scheduling Engine is to form the proper decision variables for the shift design and shift assignment problem at hand. The optimization algorithm provided by a MIP solver is the process of determining the proper values for the decision variables to take on in such a way that all relevant constraints are satisfied and the objective function is optimized (i.e., total schedule cost is minimized here. Thus the decision variables x.sub.i,j and y.sub.j together are able to describe what shape of the shifts that should be used to cover the labor demand (the shift design or shift selection) and which worker should work on which shift (the shift assignment)), evaluates an achievement state of the shift condition for the generated shift (Column 8, lines 41-48, Within the set of solutions that satisfy all constraints, an optimal or near-optimal solution is determined with respect to an objective function (e.g., by minimizing or maximizing the objective function). For example, a typical objective function represents the total cost of the schedule, wherein the total cost comprises the real cost of paying the workers for the schedule and a soft penalty cost that measures the desirability of the schedule along many dimensions; Column 14, lines 29-35, If in the test of 616 a feasible solution is found, the quality of the solution will be assessed in 620. This can be done either objectively by using the pre-configured criteria (e.g., at least 95% of the demand is covered and spending is within 2% of the given budget, etc.) or manually judged by the user through the examining of the resulting schedule; Examiner interprets “minimize cost while covering 95% of the demand” as the “achievement state”), predicts an effect of a change in the shift condition on the evaluation (Column 8, lines 53-67, The soft penalty cost comprises, for example, a schedule consistency cost (e.g., a cost associated with assigning a worker an inconsistent week to week schedule), a worker below average skill proficiency cost (e.g., a cost associated with assigning a below average skilled worker to a shift), a worker day and time preference violation cost (e.g., a cost associated with assigning an employee to a shift outside of his/her days of the week or time of the day preferences), a worker weekly scheduled time preference violation cost (e.g., a cost associated with assigning a worker to a weekly scheduled time below or above of his/her weekly scheduled time preferences), a worker job role preference violation cost (e.g., a cost associated with assigning a worker to a shift associated with job role outside of his/her preferred role when the worker is qualified for multiple roles), and/or any other appropriate costs; Column 9, lines 4-39, With the decision variables defined, a set of constraints expressed in terms of the decision variables and an objective function (total cost) expressed in terms of the decision variable, the Scheduling Engine invokes a solver (a MIP solver) which determines the optimal value each decision variable should take on in such a way that all constraints are respected and the objective function is optimized (in this case the total cost is minimized). In the case that the solver does not find a solution for the given set of constraints, the Scheduling Engine will relax certain constraints and invoke the solver again with the relaxed problem. When the Scheduling Engine relaxes a constraint, it removes the constraint from the set of constraints sent to the solver and adds the amount of the constraint violation (expressed as a function of the decision variables) multiplied by a penalty cost factor to the objective function. For example, Σ.sub.jx.sub.i,j (β.sub.j−α.sub.j−b.sub.j)≤H.sub.i is the maximum weekly hours constraint for worker i where (β.sub.j−α.sub.j−b.sub.j) is the paid number of hours for shift candidate j and H.sub.i is the maximum weekly hours for worker i. To relax this constraint, in addition to removing it from the set of constraints, a term c.sub.i.sup.H max (0, Σ.sub.jx.sub.i,j(β.sub.j−α.sub.j−b.sub.j)−H.sub.i) is added to the objective function of the total cost, where c.sub.i.sup.H is the hourly penalty cost if the assigned total weekly shift hours is above the maximum weekly hours H.sub.i for worker i. When a constraint is relaxed, the solver will try to find a solution that respects the remaining constraints and at the same time minimizes the amount of the violation of the relaxed constraint due to the penalty cost term added to the objective function. A constraint that can be relaxed by the Scheduling Engine is called a soft constraint. The order in which the Scheduling Engine may relax varieties of soft constraints is configurable. For example, if it is more important to cover the labor demands than to conform to maximum weekly hours for a particular company, the maximum weekly hour constraints would be relaxed first before relaxing the labor demand coverage constraint), and presents the … (Column 14, lines 35-45, If the schedule quality is not good enough (e.g., only 40% of workers' preferences are respected), the control is passed to 622 to adjust the corresponding penalty cost weight of a particular term in the objective function and new objective function is formed in 612 (as will be illustrated in FIG. 9 later). In the event that the schedule quality is good, the final schedule is presented to the user in 624. For any practical scheduling problem, once certain number of constraints are relaxed (such as demand coverage constraint and minimum weekly hour constraints), a feasible solution is always found).
Although Yang discloses a system that evaluates a predicted effect of a change in the shift condition and presents the generated shift (e.g., presenting a schedule with a change in the shift condition), Yang does not specifically disclose wherein the predicted effect is presented to the user.
However, DeSilva et al. discloses presents the predicted effect (Paragraph 0007, In another respect, embodiments of the invention improve the way that staff schedules are optimized by distributing resources over the planning horizon in proportion to demand, to the extent possible. Embodiments of the system and method seek to meet all hard constraints imposed by a user, and utilize a flexible scoring technique to minimize the violation of soft constraints. Embodiments also consider the substitution of higher skilled workers in cases where there is an unmet demand for lower skilled workers; Paragraph 0097, Periodically, the staff resources available for scheduling shifts (a constraint in step 105) needs to be updated. These updates may include the modification of staff profiles and rules to better match changing operating requirements, the addition of staff to reduce understaffing, and/or the reduction of staff to reduce overstaffing; Paragraph 0098, scheduling constraints and parameters are input by the user in order to run scenarios on the effect of changes to constraints, such as a change to shift structures; Paragraph 0103, If the number of staff to modify for a particular category is not zero in step 930, the process proceeds to the modification suggestion algorithm in step 935 to derive optimal modifications of staff profiles to meet unit requirements. Then, in step 940, the user is presented with suggested staff profile modifications generated in step 935).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the shift generation system, wherein an effect of a change in the shift condition is evaluated (e.g., change the minimum weekly hour constraint) of the invention of Yang to further specify wherein the effect of the change in the shift condition is presented to the user of the invention of DeSilva et al. because doing so would allow the system to run scenarios on the effect of changes to constraints and present them to the user (see DeSilva et al., Paragraphs 0098 & 0103). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 7, Yang discloses a shift generation method executed by a shift generation system that generates a shift for a member, the shift generation method comprising (Column 3, lines 34-41, A system for simultaneous shift design and shift assignment transforms input data to determine an appropriate optimization problem. The optimization problem is concerned about making a set of related decisions in such a way that a set of given constraints are satisfied and a utility function (called the objective function) is optimized (e.g., either minimized or maximized depending on the type of the objective function):
(a) accepting a shift condition and member information (Column 4, lines 25-49, The scheduling engine determines the optimal schedule by … (4) transforming input data to determine a set of constraints using the decision variables wherein the set of constraints is built based on a set of conditions/restrictions that are to be respected while determining the optimal schedule (e.g., the labor demands need to be met, worker's availability and qualification should be respected, two shifts assigned to one worker cannot overlap, the budget should be respected, etc.); Column 6, lines 52-57, A generated shift candidate is subject to labor law legal constraints, union contract constraints, company policy constraints, etc. For example, a union contract can dictate that the duration of a shift has to be between four and nine hours, or a state law can require a half hour unpaid meal break for every 5 hours consecutive work; Examiner interprets “worker’s qualification” as the “member information.” Also, Examiner interprets the “union contract” as the “shift condition”);
(b) generating the shift for the member based on the shift condition and the member information (Column 7, lines 20-45, The next step for the Scheduling Engine is to form the proper decision variables for the shift design and shift assignment problem at hand. The optimization algorithm provided by a MIP solver is the process of determining the proper values for the decision variables to take on in such a way that all relevant constraints are satisfied and the objective function is optimized (i.e., total schedule cost is minimized here. Thus the decision variables x.sub.i,j and y.sub.j together are able to describe what shape of the shifts that should be used to cover the labor demand (the shift design or shift selection) and which worker should work on which shift (the shift assignment));
(c) evaluating an achievement state of the shift condition for the generated shift (Column 8, lines 41-48, Within the set of solutions that satisfy all constraints, an optimal or near-optimal solution is determined with respect to an objective function (e.g., by minimizing or maximizing the objective function). For example, a typical objective function represents the total cost of the schedule, wherein the total cost comprises the real cost of paying the workers for the schedule and a soft penalty cost that measures the desirability of the schedule along many dimensions; Column 14, lines 29-35, If in the test of 616 a feasible solution is found, the quality of the solution will be assessed in 620. This can be done either objectively by using the pre-configured criteria (e.g., at least 95% of the demand is covered and spending is within 2% of the given budget, etc.) or manually judged by the user through the examining of the resulting schedule; Examiner interprets “minimize cost while covering 95% of the demand” as the “achievement state”);
(d) predicting an effect of a change in the shift condition on the evaluation (Column 8, lines 53-67, The soft penalty cost comprises, for example, a schedule consistency cost (e.g., a cost associated with assigning a worker an inconsistent week to week schedule), a worker below average skill proficiency cost (e.g., a cost associated with assigning a below average skilled worker to a shift), a worker day and time preference violation cost (e.g., a cost associated with assigning an employee to a shift outside of his/her days of the week or time of the day preferences), a worker weekly scheduled time preference violation cost (e.g., a cost associated with assigning a worker to a weekly scheduled time below or above of his/her weekly scheduled time preferences), a worker job role preference violation cost (e.g., a cost associated with assigning a worker to a shift associated with job role outside of his/her preferred role when the worker is qualified for multiple roles), and/or any other appropriate costs; Column 9, lines 4-39, With the decision variables defined, a set of constraints expressed in terms of the decision variables and an objective function (total cost) expressed in terms of the decision variable, the Scheduling Engine invokes a solver (a MIP solver) which determines the optimal value each decision variable should take on in such a way that all constraints are respected and the objective function is optimized (in this case the total cost is minimized). In the case that the solver does not find a solution for the given set of constraints, the Scheduling Engine will relax certain constraints and invoke the solver again with the relaxed problem. When the Scheduling Engine relaxes a constraint, it removes the constraint from the set of constraints sent to the solver and adds the amount of the constraint violation (expressed as a function of the decision variables) multiplied by a penalty cost factor to the objective function. For example, Σ.sub.jx.sub.i,j (β.sub.j−α.sub.j−b.sub.j)≤H.sub.i is the maximum weekly hours constraint for worker i where (β.sub.j−α.sub.j−b.sub.j) is the paid number of hours for shift candidate j and H.sub.i is the maximum weekly hours for worker i. To relax this constraint, in addition to removing it from the set of constraints, a term c.sub.i.sup.H max (0, Σ.sub.jx.sub.i,j(β.sub.j−α.sub.j−b.sub.j)−H.sub.i) is added to the objective function of the total cost, where c.sub.i.sup.H is the hourly penalty cost if the assigned total weekly shift hours is above the maximum weekly hours H.sub.i for worker i. When a constraint is relaxed, the solver will try to find a solution that respects the remaining constraints and at the same time minimizes the amount of the violation of the relaxed constraint due to the penalty cost term added to the objective function. A constraint that can be relaxed by the Scheduling Engine is called a soft constraint. The order in which the Scheduling Engine may relax varieties of soft constraints is configurable. For example, if it is more important to cover the labor demands than to conform to maximum weekly hours for a particular company, the maximum weekly hour constraints would be relaxed first before relaxing the labor demand coverage constraint);
and (e) presenting the … (Column 14, lines 35-45, If the schedule quality is not good enough (e.g., only 40% of workers' preferences are respected), the control is passed to 622 to adjust the corresponding penalty cost weight of a particular term in the objective function and new objective function is formed in 612 (as will be illustrated in FIG. 9 later). In the event that the schedule quality is good, the final schedule is presented to the user in 624. For any practical scheduling problem, once certain number of constraints are relaxed (such as demand coverage constraint and minimum weekly hour constraints), a feasible solution is always found).
Although Yang discloses a system for evaluating a predicted effect of a change in the shift condition and presenting the generated shift (e.g., presenting a schedule with a change in the shift condition), Yang does not specifically disclose wherein the predicted effect is presented to the user.
However, DeSilva et al. discloses (e) presenting the effect obtained in (d) (Paragraph 0007, In another respect, embodiments of the invention improve the way that staff schedules are optimized by distributing resources over the planning horizon in proportion to demand, to the extent possible. Embodiments of the system and method seek to meet all hard constraints imposed by a user, and utilize a flexible scoring technique to minimize the violation of soft constraints. Embodiments also consider the substitution of higher skilled workers in cases where there is an unmet demand for lower skilled workers; Paragraph 0097, Periodically, the staff resources available for scheduling shifts (a constraint in step 105) needs to be updated. These updates may include the modification of staff profiles and rules to better match changing operating requirements, the addition of staff to reduce understaffing, and/or the reduction of staff to reduce overstaffing; Paragraph 0098, scheduling constraints and parameters are input by the user in order to run scenarios on the effect of changes to constraints, such as a change to shift structures; Paragraph 0103, If the number of staff to modify for a particular category is not zero in step 930, the process proceeds to the modification suggestion algorithm in step 935 to derive optimal modifications of staff profiles to meet unit requirements. Then, in step 940, the user is presented with suggested staff profile modifications generated in step 935).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the shift generation system, wherein an effect of a change in the shift condition is evaluated (e.g., change the minimum weekly hour constraint) of the invention of Yang to further specify wherein the effect of the change in the shift condition is presented to the user of the invention of DeSilva et al. because doing so would allow the system to run scenarios on the effect of changes to constraints and present them to the user (see DeSilva et al., Paragraphs 0098 & 0103). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 13, Yang discloses a non-transitory recording medium storing a computer-readable shift generation program for causing a computer to execute processing comprising (Abstract, A system includes one or more processors; and at least one non-transitory machine-readable storage media comprising instructions which, when executed by the one or more processors, cause the one or more processors to; Column 3, lines 34-41, A system for simultaneous shift design and shift assignment transforms input data to determine an appropriate optimization problem. The optimization problem is concerned about making a set of related decisions in such a way that a set of given constraints are satisfied and a utility function (called the objective function) is optimized (e.g., either minimized or maximized depending on the type of the objective function):
(a) accepting a shift condition and member information (Column 4, lines 25-49, The scheduling engine determines the optimal schedule by … (4) transforming input data to determine a set of constraints using the decision variables wherein the set of constraints is built based on a set of conditions/restrictions that are to be respected while determining the optimal schedule (e.g., the labor demands need to be met, worker's availability and qualification should be respected, two shifts assigned to one worker cannot overlap, the budget should be respected, etc.); Column 6, lines 52-57, A generated shift candidate is subject to labor law legal constraints, union contract constraints, company policy constraints, etc. For example, a union contract can dictate that the duration of a shift has to be between four and nine hours, or a state law can require a half hour unpaid meal break for every 5 hours consecutive work; Examiner interprets “worker’s qualification” as the “member information.” Also, Examiner interprets the “union contract” as the “shift condition”);
(b) generating a shift for a member based on the shift condition and the member information (Column 7, lines 20-45, The next step for the Scheduling Engine is to form the proper decision variables for the shift design and shift assignment problem at hand. The optimization algorithm provided by a MIP solver is the process of determining the proper values for the decision variables to take on in such a way that all relevant constraints are satisfied and the objective function is optimized (i.e., total schedule cost is minimized here. Thus the decision variables x.sub.i,j and y.sub.j together are able to describe what shape of the shifts that should be used to cover the labor demand (the shift design or shift selection) and which worker should work on which shift (the shift assignment));
(c) evaluating an achievement state of the shift condition for the generated shift (Column 8, lines 41-48, Within the set of solutions that satisfy all constraints, an optimal or near-optimal solution is determined with respect to an objective function (e.g., by minimizing or maximizing the objective function). For example, a typical objective function represents the total cost of the schedule, wherein the total cost comprises the real cost of paying the workers for the schedule and a soft penalty cost that measures the desirability of the schedule along many dimensions; Column 14, lines 29-35, If in the test of 616 a feasible solution is found, the quality of the solution will be assessed in 620. This can be done either objectively by using the pre-configured criteria (e.g., at least 95% of the demand is covered and spending is within 2% of the given budget, etc.) or manually judged by the user through the examining of the resulting schedule; Examiner interprets “minimize cost while covering 95% of the demand” as the “achievement state”);
(d) predicting an effect of a change in the shift condition on the evaluation (Column 8, lines 53-67, The soft penalty cost comprises, for example, a schedule consistency cost (e.g., a cost associated with assigning a worker an inconsistent week to week schedule), a worker below average skill proficiency cost (e.g., a cost associated with assigning a below average skilled worker to a shift), a worker day and time preference violation cost (e.g., a cost associated with assigning an employee to a shift outside of his/her days of the week or time of the day preferences), a worker weekly scheduled time preference violation cost (e.g., a cost associated with assigning a worker to a weekly scheduled time below or above of his/her weekly scheduled time preferences), a worker job role preference violation cost (e.g., a cost associated with assigning a worker to a shift associated with job role outside of his/her preferred role when the worker is qualified for multiple roles), and/or any other appropriate costs; Column 9, lines 4-39, With the decision variables defined, a set of constraints expressed in terms of the decision variables and an objective function (total cost) expressed in terms of the decision variable, the Scheduling Engine invokes a solver (a MIP solver) which determines the optimal value each decision variable should take on in such a way that all constraints are respected and the objective function is optimized (in this case the total cost is minimized). In the case that the solver does not find a solution for the given set of constraints, the Scheduling Engine will relax certain constraints and invoke the solver again with the relaxed problem. When the Scheduling Engine relaxes a constraint, it removes the constraint from the set of constraints sent to the solver and adds the amount of the constraint violation (expressed as a function of the decision variables) multiplied by a penalty cost factor to the objective function. For example, Σ.sub.jx.sub.i,j (β.sub.j−α.sub.j−b.sub.j)≤H.sub.i is the maximum weekly hours constraint for worker i where (β.sub.j−α.sub.j−b.sub.j) is the paid number of hours for shift candidate j and H.sub.i is the maximum weekly hours for worker i. To relax this constraint, in addition to removing it from the set of constraints, a term c.sub.i.sup.H max (0, Σ.sub.jx.sub.i,j(β.sub.j−α.sub.j−b.sub.j)−H.sub.i) is added to the objective function of the total cost, where c.sub.i.sup.H is the hourly penalty cost if the assigned total weekly shift hours is above the maximum weekly hours H.sub.i for worker i. When a constraint is relaxed, the solver will try to find a solution that respects the remaining constraints and at the same time minimizes the amount of the violation of the relaxed constraint due to the penalty cost term added to the objective function. A constraint that can be relaxed by the Scheduling Engine is called a soft constraint. The order in which the Scheduling Engine may relax varieties of soft constraints is configurable. For example, if it is more important to cover the labor demands than to conform to maximum weekly hours for a particular company, the maximum weekly hour constraints would be relaxed first before relaxing the labor demand coverage constraint);
and (e) presenting the … (Column 14, lines 35-45, If the schedule quality is not good enough (e.g., only 40% of workers' preferences are respected), the control is passed to 622 to adjust the corresponding penalty cost weight of a particular term in the objective function and new objective function is formed in 612 (as will be illustrated in FIG. 9 later). In the event that the schedule quality is good, the final schedule is presented to the user in 624. For any practical scheduling problem, once certain number of constraints are relaxed (such as demand coverage constraint and minimum weekly hour constraints), a feasible solution is always found).
Although Yang discloses a system for evaluating a predicted effect of a change in the shift condition and presenting the generated shift (e.g., presenting a schedule with a change in the shift condition), Yang does not specifically disclose wherein the predicted effect is presented to the user.
However, DeSilva et al. discloses (e) presenting the effect obtained in (d) (Paragraph 0007, In another respect, embodiments of the invention improve the way that staff schedules are optimized by distributing resources over the planning horizon in proportion to demand, to the extent possible. Embodiments of the system and method seek to meet all hard constraints imposed by a user, and utilize a flexible scoring technique to minimize the violation of soft constraints. Embodiments also consider the substitution of higher skilled workers in cases where there is an unmet demand for lower skilled workers; Paragraph 0097, Periodically, the staff resources available for scheduling shifts (a constraint in step 105) needs to be updated. These updates may include the modification of staff profiles and rules to better match changing operating requirements, the addition of staff to reduce understaffing, and/or the reduction of staff to reduce overstaffing; Paragraph 0098, scheduling constraints and parameters are input by the user in order to run scenarios on the effect of changes to constraints, such as a change to shift structures; Paragraph 0103, If the number of staff to modify for a particular category is not zero in step 930, the process proceeds to the modification suggestion algorithm in step 935 to derive optimal modifications of staff profiles to meet unit requirements. Then, in step 940, the user is presented with suggested staff profile modifications generated in step 935).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the shift generation system, wherein an effect of a change in the shift condition is evaluated (e.g., change the minimum weekly hour constraint) of the invention of Yang to further specify wherein the effect of the change in the shift condition is presented to the user of the invention of DeSilva et al. because doing so would allow the system to run scenarios on the effect of changes to constraints and present them to the user (see DeSilva et al., Paragraphs 0098 & 0103). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claims 2, 8, and 14, which are dependent of claims 1, 7, and 13, the combination of Yang and DeSilva et al. discloses all the limitations in claims 1, 7, and 13. Yang further discloses wherein the hardware processor evaluates an achievement state for each of shift conditions, and predicts the effect on the evaluation based on whether or not the evaluation is improved by limiting the shift conditions to any one of the shift conditions of which the evaluated achievement states do not satisfy a predetermined criterion (Column 8, lines 53-67, The soft penalty cost comprises, for example, a schedule consistency cost (e.g., a cost associated with assigning a worker an inconsistent week to week schedule), a worker below average skill proficiency cost (e.g., a cost associated with assigning a below average skilled worker to a shift), a worker day and time preference violation cost (e.g., a cost associated with assigning an employee to a shift outside of his/her days of the week or time of the day preferences), a worker weekly scheduled time preference violation cost (e.g., a cost associated with assigning a worker to a weekly scheduled time below or above of his/her weekly scheduled time preferences), a worker job role preference violation cost (e.g., a cost associated with assigning a worker to a shift associated with job role outside of his/her preferred role when the worker is qualified for multiple roles), and/or any other appropriate costs; Column 9, lines 4-39, With the decision variables defined, a set of constraints expressed in terms of the decision variables and an objective function (total cost) expressed in terms of the decision variable, the Scheduling Engine invokes a solver (a MIP solver) which determines the optimal value each decision variable should take on in such a way that all constraints are respected and the objective function is optimized (in this case the total cost is minimized). In the case that the solver does not find a solution for the given set of constraints, the Scheduling Engine will relax certain constraints and invoke the solver again with the relaxed problem. When the Scheduling Engine relaxes a constraint, it removes the constraint from the set of constraints sent to the solver and adds the amount of the constraint violation (expressed as a function of the decision variables) multiplied by a penalty cost factor to the objective function. For example, Σ.sub.jx.sub.i,j (β.sub.j−α.sub.j−b.sub.j)≤H.sub.i is the maximum weekly hours constraint for worker i where (β.sub.j−α.sub.j−b.sub.j) is the paid number of hours for shift candidate j and H.sub.i is the maximum weekly hours for worker i. To relax this constraint, in addition to removing it from the set of constraints, a term c.sub.i.sup.H max (0, Σ.sub.jx.sub.i,j(β.sub.j−α.sub.j−b.sub.j)−H.sub.i) is added to the objective function of the total cost, where c.sub.i.sup.H is the hourly penalty cost if the assigned total weekly shift hours is above the maximum weekly hours H.sub.i for worker i. When a constraint is relaxed, the solver will try to find a solution that respects the remaining constraints and at the same time minimizes the amount of the violation of the relaxed constraint due to the penalty cost term added to the objective function. A constraint that can be relaxed by the Scheduling Engine is called a soft constraint. The order in which the Scheduling Engine may relax varieties of soft constraints is configurable. For example, if it is more important to cover the labor demands than to conform to maximum weekly hours for a particular company, the maximum weekly hour constraints would be relaxed first before relaxing the labor demand coverage constraint).
Regarding claims 3, 9, and 15, which are dependent of claims 2, 8, and 14, the combination of Yang and DeSilva et al. discloses all the limitations in claims 2, 8, and 14. Yang further discloses wherein the hardware processor predicts the effect on the evaluation based on whether or not all of the limited shift conditions are achieved by limiting the shift conditions to two or more shift conditions including the shift condition for which the evaluation has been improved and the shift condition other than the shift condition for which the evaluation has been improved (Column 8, lines 53-67, The soft penalty cost comprises, for example, a schedule consistency cost (e.g., a cost associated with assigning a worker an inconsistent week to week schedule), a worker below average skill proficiency cost (e.g., a cost associated with assigning a below average skilled worker to a shift), a worker day and time preference violation cost (e.g., a cost associated with assigning an employee to a shift outside of his/her days of the week or time of the day preferences), a worker weekly scheduled time preference violation cost (e.g., a cost associated with assigning a worker to a weekly scheduled time below or above of his/her weekly scheduled time preferences), a worker job role preference violation cost (e.g., a cost associated with assigning a worker to a shift associated with job role outside of his/her preferred role when the worker is qualified for multiple roles), and/or any other appropriate costs; Column 9, lines 4-39, With the decision variables defined, a set of constraints expressed in terms of the decision variables and an objective function (total cost) expressed in terms of the decision variable, the Scheduling Engine invokes a solver (a MIP solver) which determines the optimal value each decision variable should take on in such a way that all constraints are respected and the objective function is optimized (in this case the total cost is minimized). In the case that the solver does not find a solution for the given set of constraints, the Scheduling Engine will relax certain constraints and invoke the solver again with the relaxed problem. When the Scheduling Engine relaxes a constraint, it removes the constraint from the set of constraints sent to the solver and adds the amount of the constraint violation (expressed as a function of the decision variables) multiplied by a penalty cost factor to the objective function. For example, Σ.sub.jx.sub.i,j (β.sub.j−α.sub.j−b.sub.j)≤H.sub.i is the maximum weekly hours constraint for worker i where (β.sub.j−α.sub.j−b.sub.j) is the paid number of hours for shift candidate j and H.sub.i is the maximum weekly hours for worker i. To relax this constraint, in addition to removing it from the set of constraints, a term c.sub.i.sup.H max (0, Σ.sub.jx.sub.i,j(β.sub.j−α.sub.j−b.sub.j)−H.sub.i) is added to the objective function of the total cost, where c.sub.i.sup.H is the hourly penalty cost if the assigned total weekly shift hours is above the maximum weekly hours H.sub.i for worker i. When a constraint is relaxed, the solver will try to find a solution that respects the remaining constraints and at the same time minimizes the amount of the violation of the relaxed constraint due to the penalty cost term added to the objective function. A constraint that can be relaxed by the Scheduling Engine is called a soft constraint. The order in which the Scheduling Engine may relax varieties of soft constraints is configurable. For example, if it is more important to cover the labor demands than to conform to maximum weekly hours for a particular company, the maximum weekly hour constraints would be relaxed first before relaxing the labor demand coverage constraint; Column 14, lines 29-35, If in the test of 616 a feasible solution is found, the quality of the solution will be assessed in 620. This can be done either objectively by using the pre-configured criteria (e.g., at least 95% of the demand is covered and spending is within 2% of the given budget, etc.) or manually judged by the user through the examining of the resulting schedule; Examiner notes that Yang evaluates whether the change in the shift condition resulted in a better percentage of the demand covered of the shift/schedule).
Regarding claims 6, 12, and 18, which are dependent of claims 2, 8, and 14, the combination of Yang and DeSilva et al. discloses all the limitations in claims 2, 8, and 14. Yang further discloses wherein the hardware processor generates the shift based on the plurality of shift conditions, generates, in response to acceptance of one of the plurality of shift conditions, the shift based on the one of the plurality of shift conditions, and predicts whether or not the evaluation is improved based on the shift generated based on the one of the plurality of shift conditions (Column 8, lines 53-67, The soft penalty cost comprises, for example, a schedule consistency cost (e.g., a cost associated with assigning a worker an inconsistent week to week schedule), a worker below average skill proficiency cost (e.g., a cost associated with assigning a below average skilled worker to a shift), a worker day and time preference violation cost (e.g., a cost associated with assigning an employee to a shift outside of his/her days of the week or time of the day preferences), a worker weekly scheduled time preference violation cost (e.g., a cost associated with assigning a worker to a weekly scheduled time below or above of his/her weekly scheduled time preferences), a worker job role preference violation cost (e.g., a cost associated with assigning a worker to a shift associated with job role outside of his/her preferred role when the worker is qualified for multiple roles), and/or any other appropriate costs; Column 9, lines 4-39, With the decision variables defined, a set of constraints expressed in terms of the decision variables and an objective function (total cost) expressed in terms of the decision variable, the Scheduling Engine invokes a solver (a MIP solver) which determines the optimal value each decision variable should take on in such a way that all constraints are respected and the objective function is optimized (in this case the total cost is minimized). In the case that the solver does not find a solution for the given set of constraints, the Scheduling Engine will relax certain constraints and invoke the solver again with the relaxed problem. When the Scheduling Engine relaxes a constraint, it removes the constraint from the set of constraints sent to the solver and adds the amount of the constraint violation (expressed as a function of the decision variables) multiplied by a penalty cost factor to the objective function. For example, Σ.sub.jx.sub.i,j (β.sub.j−α.sub.j−b.sub.j)≤H.sub.i is the maximum weekly hours constraint for worker i where (β.sub.j