Search

US-12625724-B1 - Persistent schedule evaluation and adaptive re-scheduling

US12625724B1US 12625724 B1US12625724 B1US 12625724B1US-12625724-B1

Abstract

Methods and systems are provided for dynamic evaluation and elastic re-planning for a variant of the flexible job-shop scheduling problem, wherein a set of jobs have been pre-allocated to a set of machines for performing the various subtasks for the jobs. The machines are allocated the tasks under a pre-defined but estimated schedule based on initial knowledge of the jobs and desired outcome. However, due to a level of autonomy and reactivity to job characteristics (such as material imperfections, environment, or job difficulty), the precise duration and actions individual machines will require to accomplish the tasks is unknown a priori. A Hidden Markov Model is developed for propagating task estimates. A quadratic-programming-based elastic re-scheduling algorithm is formulated, which quickly and efficiently re-plans overall job schedules.

Inventors

  • Matthew J Bays
  • Thomas A Wettergren

Assignees

  • UNITED STATES OF AMERICA AS REPRESENTED BY THE SECRETARY OF THE NAVY

Dates

Publication Date
20260512
Application Date
20230731

Claims (18)

  1. 1 . A method of evaluating and replanning schedules for a set of machines, M , that have been allocated tasks under a pre-defined but estimated original schedule based on initial knowledge of the tasks and desired outcome, said method comprising: developing a Hidden Markov Model (HMM) describing evolution of observable schedule delays dependent on factors not directly observable; propagating updated task estimates for each task based on using said HMM and then-current data; and applying a quadratic programming (QP) approach to combine said updated task estimates into an optimally delayed end-to-end schedule; wherein propagating said updated task estimates comprises: obtaining fixed task type starttimes and endtimes, wherein each said fixed task type maintains an original schedule starttime and endtime; obtaining flexible task type starttimes and endtimes, wherein a duration of each said flexible task type is a constant and a starttime of each said flexible task type is dependent on an endtime of a preceding task, and obtaining production task type start times and endtimes, wherein each production task type is divided into a finite number of subtasks and each of said subtasks is executed in one of a finite number of modes based on sensed characteristics of an area wherein each said subtask is executed; wherein developing said Hidden Markov Model comprises: developing a first calculation for the expectation of the mean endtime for each said production task, T ˆ m , p e ⁢ n ⁢ d ( s ) , where m is an index of an m th machine in said set of an machines, p is an index of a p th task of said m th machine, and S is an index of a S th subtask of said p th task; and developing a second calculation for the transient variance of each executed endtime of each of said production tasks, VAS ⁡ ( T _ m , p end ) .
  2. 2 . The method of claim 1 , wherein said quadratic programming approach comprises: developing an ontology describing relative interactions between tasks; and minimizing an overall difference between a replanned schedule and said original schedule by weighting a perturbation of future tasks, while respecting constraints inherent in said ontology.
  3. 3 . The method of claim 2 , wherein said interactions comprise: interactions with said fixed tasks, wherein said fixed tasks are constrained to maintain an original schedule start time during replanning; interactions with cross-scheduled tasks, wherein said cross-scheduled tasks are constrained to have a same start time and a same end time; interactions with loosely connected tasks, wherein there exist implicit constraints that a start time of a first of said loosely connected tasks is at least one of before and equal to a start time of a second one of said loosely connected tasks; interactions with coupled tasks, wherein corresponding relative start times and precedence remain the same within a schedule; and interactions with adjacent tasks, wherein there exist implicit constraints a start time of a following one of said adjacent tasks is an end time of a preceding one of said adjacent tasks.
  4. 4 . The method of claim 3 , wherein said quadratic programming approach further comprises constraining said executed endtimes of said production tasks to occur at a current expected production time based on said first and second calculations for said production tasks.
  5. 5 . The method of claim 1 , wherein said quadratic programming approach comprises: developing an ontology describing relative interactions between tasks; and minimizing an overall difference between a replanned schedule and said original schedule by weighting a perturbation of future tasks, while respecting constraints inherent is said ontology.
  6. 6 . The method of claim 5 , wherein said interactions comprise: interactions with fixed tasks, wherein said fixed tasks are constrained to maintain an original schedule start time and endtime during replanning; interactions with cross-scheduled tasks, wherein said cross-scheduled tasks are constrained to have a same start time and a same endtime; interactions with loosely connected tasks, wherein there exist implicit constraints that a start time of a first of said loosely connected tasks is at least one of before and equal to a start time of a second one of said loosely connected tasks; interactions with coupled tasks, wherein corresponding relative start times and precedence remain the same within a schedule; and interactions with adjacent tasks, wherein there exist implicit constraints that a start time of a following one of said adjacent tasks is an end time of a preceding one of said adjacent tasks.
  7. 7 . The method of claim 6 , wherein said quadratic programming approach further comprises constraining endtimes of production tasks to occur at a current expected production time based on said updated task estimates for said production tasks, wherein each production task is divided into a finite number of subtasks and each of said subtasks is executed in one of a finite number of modes based on sensed characteristics of an area wherein each said subtask is executed.
  8. 8 . A method of evaluating and replanning schedules for a set of machines, M , that have been allocated tasks under a pre-defined but estimated original schedule based on initial knowledge of the tasks and desired outcome, said method comprising: developing a Hidden Markov Model (HMM) describing evolution of observable schedule delays dependent on factors not directly observable; propagating updated task estimates for each task based on using said HMM and then-current data; and applying a quadratic programming (QP) approach to combine said updated task completion estimates and constraints into an optimally delayed end-to-end schedule; wherein propagating said updated task estimates comprises: obtaining fixed task type start times and end times, wherein each said fixed task type maintains an original schedule start time and endtime; obtaining flexible task type start times and end times, wherein a duration of each said flexible task type is a constant and a start time of each said flexible task type is dependent on an endtime of a preceding task; and obtaining production task type start times and end times, wherein each production task type is divided into a finite number of subtasks and each of said subtasks is executed in one of a finite number of modes based on sensed characteristics of an area wherein each said subtask is executed; wherein developing said Hidden Markov Model comprises: developing a first calculation for the expectation of the mean endtime for each said production task T ˆ m , p e ⁢ n ⁢ d ( s ) where m is an index of an m th machine in said set of machines, P is an index of a p th task of said m th machine, and S is an index of a S th subtask of said p th task; and developing a second calculation for the transient variance of each executed endtime of each of said production tasks, VAR ⁡ ( T _ m , p end ) .
  9. 9 . The method of claim 8 , wherein applying a quadratic programming approach comprises: applying elasticity parameters to said updated task completion estimates; and optimally weighting a perturbation of future tasks based on said elasticity parameters.
  10. 10 . The method of claim 9 , wherein said weighting comprises obtaining a transient variance of each said estimated endtime, VAR ( T ¯ m , p e ⁢ n ⁢ d ( s ) ) , where m is an index of an m th machine in said set of machines, p is an index of a p th task of a set P tasks of said m th machine, and S is an index of a s th subtask of said p th task.
  11. 11 . The method of claim 10 , wherein said constraints comprise: enforcing precedence between task schedules; enforcing fixed tasks be scheduled at start times consistent with said original schedule; and enforcing cross-scheduled tasks be scheduled with a same start time and a same end time.
  12. 12 . The method of claim 11 , wherein obtaining an updated task completion estimated endtime comprises obtaining production task start times and endtimes, wherein each production task is divided into a finite number of subtasks and each of said subtasks is executed in one of a finite number of modes based on sensed characteristics of an area wherein each said subtask is executed.
  13. 13 . The method of claim 12 , wherein said constraints further comprise enforcing endtimes of production tasks occur at a current expected production time based on said updated task estimates for said production tasks.
  14. 14 . The method of claim 13 , wherein said optimally delayed schedule minimizes a cost function ∑ m ∈ M , p ∈ P m ⁢ k m , p ⁢ ❘ "\[LeftBracketingBar]" ( T m , p + 1 s ⁢ t ⁢ a ⁢ r ⁢ t - T m , p e ⁢ n ⁢ d ) - ( T ¯ m , p + 1 s ⁢ t ⁢ a ⁢ r ⁢ t - T ¯ m , p e ⁢ n ⁢ d ) ❘ "\[RightBracketingBar]" 2 , wherein k m,p is a summation of said transient variances over the set P, T m , p + 1 s ⁢ t ⁢ a ⁢ r ⁢ t signifies an original start time of a task, p+1 of machine m, T m , p e ⁢ n ⁢ d signifies an original end time of a task, p of machine m, T ¯ m , p + 1 s ⁢ t ⁢ a ⁢ r ⁢ t signifies an expected start time of task p+1 and T ¯ m , p e ⁢ n ⁢ d signifies an expected end time of task p.
  15. 15 . The method of claim 14 , further comprising determining if said optimally delayed end-to-end schedule is found to be infeasible in view of said constraints.
  16. 16 . The method of claim 15 , further comprising replanning said updating of task schedules when said end-to-end schedule is found to be infeasible.
  17. 17 . The method of claim 8 , further comprising determining if said optimally delayed end-to-end schedule is found to be infeasible in view of said constraints.
  18. 18 . The method of claim 17 , further comprising replanning said updating of task schedules when said end-to-end schedule is found to be infeasible.

Description

STATEMENT OF GOVERNMENT INTEREST The invention described herein may be manufactured and used by or for the Government of the United States of America for governmental purposes without the payment of any royalties. BACKGROUND OF THE INVENTION (1) Field of the Invention The present invention relates to evaluating and re-planning of job schedules for a set of machines performing the various subtasks for the job. More particularly, the present invention relates to a model developed for propagating task estimates, with an elastic re-scheduling algorithm to quickly and efficiently re-plan overall job schedules. (2) Description of the Prior Art The flexible job-shop scheduling problem (FJSP) is a classic problem in operations research, where a number of work centers consisting of identical machines are available to process a set of jobs. Each job must visit each work center, but any machine at the work center may process the job. The goal of the optimization problem is to develop an assignment of operations to machines, along with a corresponding schedule, such that some function of the assigned costs is minimized. Very often this objective is phrased as minimizing the makespan, which is given as the final completion time for the last completed operation. The makespan for the entire set of assigned jobs schedules the time for completion of the last-completed job. While the complete optimization problem has been extensively studied, less studied has been how to efficiently estimate and re-plan an initial job-shop schedule when the precise time required for the various tasks is unknown beforehand. In the late 1980's it was recognized that FJSP was a computationally hard problem and most efforts attempted to solve it as a special case of a Traveling Salesperson Problem (TSP). In the early 1990's the focus became on trying to use more modern computational optimization methods (like metaheuristics) but there was always difficulty maintaining a direct connection from the symbolic optimization solution to the actual schedule because some of the “production rules” were often violated (such as precedence constraints). Early on, it was shown that clever representations of the chromosomes of genetic algorithms could be developed that were consistent with FJSP formulations. This led to a natural way to enforce production rules of the FJSP within the optimization procedure. Similarly, it was shown that local solutions to a job shop scheduling problem can be found using simulated annealing (when given enough time to converge). More recent work in this area is based on advanced numerical solutions to the problem. Recently, there have been other metaheuristic approaches proposed for solving FJSP's, including tabu search algorithms, particle swarm optimization (PSO), and even using Lagrangian relaxation methods to reformulate the original Mixed-Integer Linear Programming (MILP) problem as a pure Linear Programming (LP) problem. All of these approaches can be applied to the re-scheduling problem, but they effectively optimize the main problem again without directly solving it as an adaptation of the existing plan. Multiple objective variants of flexible job shop scheduling problems have also recently appeared in the literature. There has been developed a multi-objective metaheuristic solution approach for the FJSP problem. This approach allows an operator to choose operating points along a Pareto front and modify the schedule in response to desired changes in the objective preferences. Also, a particle swarm optimization (PSO) approach has been used to solve a multi-objective version of FJSP. Some of the applications involve modifying the formulation for application-specific needs or developing a new objective function. It has been shown that multiple robotic arms can be coordinated to execute multiple tasks by performing the scheduling using a genetic algorithm. In this case all of the complexity is taken into the genetic chromosome and it becomes a standard genetic algorithm problem. Some have looked at the tardiness objective as an interesting objective for FJSP problems, where tardiness is defined as how late tasks are behind a due date (as opposed to getting done as soon as possible). In this approach there are new heuristics for local solutions to the problem, given an initial schedule, which is an alternative approach to re-scheduling that doesn't take advantage of the computational benefits of the elastic approach. The direct application of adaptive approaches that do not involve an adaptive solution of the original scheduling optimization problem have been limited. One recent approach adapts the scheduling of search-and-rescue vehicles by prioritizing the objective of maximizing the number of allocated tasks in a fixed amount of time over more direct objectives. Another recent example of re-scheduling looks at the impact of machine disruption on schedule adaptation. A genetic algorithm is used to solve the schedule adaptat