Patent
System and method for multi-mission prioritization using cost-based mission scheduling
| العنوان: | System and method for multi-mission prioritization using cost-based mission scheduling |
|---|---|
| Patent Number: | 7,895,071 |
| تاريخ النشر: | February 22, 2011 |
| Appl. No: | 11/504227 |
| Application Filed: | August 14, 2006 |
| مستخلص: | Described is a system for multi-mission scheduling. The system is configured to compile a list of missions, where each mission includes at least one task. Additionally, each mission has a mission value associated with it such that the mission value reflects an ordering priority of the mission. The system also compiles a list of available resources that can be utilized to complete the tasks. The resources have, varying capabilities of completing tasks. Based on the lists, the system allocates and schedules the resources to complete tasks within the missions to maximize a total mission value of completed missions. Thus, the system schedules multiple missions to maximize the value of completed missions given available resources, whereby a mission is scheduled when the totality of its tasks have been allocated a sufficient amount of resources. |
| Inventors: | Khosla, Deepak (Camarillo, CA, US); Dow, Alex (Los Angeles, CA, US) |
| Assignees: | HRL Laboratories, LLC (Malibu, CA, US) |
| Claim: | 1. A computer implemented method for multi-mission scheduling, the method comprising an act of: causing a computer with a processor and a memory to execute instructions encoded on the memory to cause the processor to perform operations of: compiling a list of a plurality of missions, each of which includes at least one task, and where each mission has a mission value associated with it such that the mission value reflects an ordering priority of the mission; compiling a list of available resources, the available resources being usable for completing tasks; specifying a global time-budget for allocating available resources to complete missions to maximize a total mission value; identifying the mission with the largest mission value; identifying whether the mission includes a task that needs additional resources in order to complete the task; when the mission includes a task that needs additional resources, identifying and scheduling the available resources that can complete the task, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying if the mission includes any tasks that need additional resources; when the resources that can complete the task are unavailable, then specifying a task-specific time-budget for a first task, wherein the task-specific time-budget is based on the amount of time remaining in the global time-budget and a value of the mission the first task belongs to; and re-allocating resources among the tasks until can either schedule the task or the task-specific time-budget is exhausted, and if the task-specific time budget is exhausted, then the task is a failed task; identifying whether there are any failed tasks; when there is at least one failed task, then identifying and scheduling the available resources that can complete the task; when the resources that can complete the task are unavailable, then add the task to a list of unscheduled tasks and perform the following acts: identifying a perturbed list, the perturbed list comprising all tasks in the schedule that are currently allocated resources that are sufficient to complete a task in the list of unscheduled tasks; generating a first value of the schedule choosing a task at random from a list selected from a group consisting of the perturbed list and the list of unscheduled tasks; when the task chosen is from the perturbed list, then de-allocating its resources, and if possible, re-allocate other resources chosen at random to the task, and if not possible, remove the task from the perturbed list and put it in the unscheduled list because it no longer has resources allocated to it; when the task chosen is from the list of unscheduled tasks, then allocating resources chosen at random to the task and move it from the unscheduled list to the perturbed list; generating a second value of the schedule; comparing the first value to the second value; when the second value is greater than the first value, then keeping the schedule corresponding to the second value, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying whether the mission includes a task that needs additional resources; and when the first value is greater than the second value, then reverting to the schedule that corresponds to the first value, then repeating the above procedure beginning with the act of identifying a perturbed list, such that the procedure is repeated until a predetermined probability threshold is reached, where the predetermined probability threshold is dependent upon the task-specific time-budget; and when all tasks in the mission have been allocated a sufficient amount of resources, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying whether the mission includes a task that needs additional resources until all missions in the list of plurality of missions have been scheduled or processed through the above procedure. |
| Claim: | 2. A system for multi-mission scheduling, the system comprising: a memory and a processor, the memory being encoded with instructions that, when executed, cause the processor to perform operations of: compiling a list of a plurality of missions, each of which includes at least one task, and where each mission has a mission value associated with it such that the mission value reflects an ordering priority of the mission; compiling a list of available resources, the available resources being usable for completing tasks; specifying a global time-budget for allocating available resources to complete missions to maximize a total mission value; identifying the mission with the largest mission value; identifying whether the mission includes a task that needs additional resources in order to complete the task; when the mission includes a task that needs additional resources, identifying and scheduling the available resources that can complete the task, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying if the mission includes any tasks that need additional resources; when the resources that can complete the task are unavailable, then specifying a task-specific time-budget for a first task, wherein the task-specific time-budget is based on the amount of time remaining in the global time-budget and a value of the mission the first task belongs to; and re-allocating resources among the tasks until can either schedule the task or the task-specific time-budget is exhausted, and if the task-specific time budget is exhausted, then the task is a failed task; and identifying whether there are any failed tasks; when there is at least one failed task, then identifying and scheduling the available resources that can complete the task, when the resources that can complete the task are unavailable, then add the task to a list of unscheduled tasks and perform the following acts: identifying a perturbed list, the perturbed list comprising all tasks in the schedule that are currently allocated resources that are sufficient to complete a task in the list of unscheduled tasks; generating a first value of the schedule choosing a task at random from a list selected from a group consisting of the perturbed list and the list of unscheduled tasks; when the task chosen is from the perturbed list, then de-allocating its resources, and if possible, re-allocate other resources chosen at random to the task, and if not possible, remove the task from the perturbed list and put it in the unscheduled list because it no longer has resources allocated to it; when the task chosen is from the list of unscheduled tasks, then allocating resources chosen at random to the task and move it from the unscheduled list to the perturbed list, generating a second value of the schedule; comparing the first value to the second value; when the second value is greater than the first value, then keeping the schedule corresponding to the second value, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying whether the mission includes a task that needs additional resources; and when the first value is greater than the second value, then reverting to the schedule that corresponds to the first value, then repeating the above procedure beginning with the act of identifying a perturbed list, such that the procedure is repeated until a predetermined probability threshold is reached, where the predetermined probability threshold is dependent upon the task-specific time-budget; and when all tasks in the mission have been allocated a sufficient amount of resources, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying whether the mission includes a task that needs additional resources until all missions in the list of plurality of missions have been scheduled or processed through the above procedure. |
| Claim: | 3. A computer program product for multi-mission scheduling, the computer program product comprising computer-readable instruction means stored on a non-transitory computer-readable medium that are executable by a computer for causing the computer to perform operations of: compiling a list of a plurality of missions, each of which includes at least one task, and where each mission has a mission value associated with it such that the mission value reflects an ordering priority of the mission; compiling a list of available resources, the available resources being usable for completing tasks; specifying a global time-budget for allocating available resources to complete missions to maximize a total mission value; identifying the mission with the largest mission value; identifying whether the mission includes a task that needs additional resources in order to complete the task; when the mission includes a task that needs additional resources, identifying and scheduling the available resources that can complete the task, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying if the mission includes any tasks that need additional resources; when the resources that can complete the task are unavailable, then specifying a task-specific time-budget for a first task, wherein the task-specific time-budget is based on the amount of time remaining in the global time-budget and a value of the mission the first task belongs to; and re-allocating resources among the tasks until can either schedule the task or the task-specific time-budget is exhausted, and if the task-specific time budget is exhausted, then the task is a failed task; and identifying whether there are any failed tasks; when there is at least one failed task, then identifying and scheduling the available resources that can complete the task; when the resources that can complete the task are unavailable, then add the task to a list of unscheduled tasks and perform the following acts: identifying a perturbed list, the perturbed list comprising all tasks in the schedule that are currently allocated resources that are sufficient to complete a task in the list of unscheduled tasks; generating a first value of the schedule choosing a task at random from a list selected from a group consisting of the perturbed list and the list of unscheduled tasks; when the task chosen is from the perturbed list, then de-allocating its resources, and if possible, re-allocate other resources chosen at random to the task, and if not possible, remove the task from the perturbed list and put it in the unscheduled list because it no longer has resources allocated to it; when the task chosen is from the list of unscheduled tasks, then allocating resources chosen at random to the task and move it from the unscheduled list to the perturbed list; generating a second value of the schedule; comparing the first value to the second value; when the second value is greater than the first value, then keeping the schedule corresponding to the second value, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying whether the mission includes a task that needs additional resources; and when the first value is greater than the second value, then reverting to the schedule that corresponds to the first value, then repeating the above procedure beginning with the act of identifying a perturbed list, such that the procedure is repeated until a predetermined probability threshold is reached, where the predetermined probability threshold is dependent upon the task-specific time-budget; and when all tasks in the mission have been allocated a sufficient amount of resources, then identifying the mission with the next largest mission value and repeating the above procedure beginning with identifying whether the mission includes a task that needs additional resources until all missions in the list of plurality of missions have been scheduled or processed through the above procedure. |
| Current U.S. Class: | 705/9 |
| Patent References Cited: | 5340056 August 1994 Guelman et al. 5406476 April 1995 Deziel et al. 5890134 March 1999 Fox 6497169 December 2002 Khosla 6882989 April 2005 Stevens 7089193 August 2006 Newbold 7236861 June 2007 Paradis et al. 7516455 April 2009 Matheson et al. 7765038 July 2010 Appleby et al. 2005/0216324 September 2005 Maithell et al. |
| Other References: | Moss, Paula et al., Multi-mission Prioritiziation Using Cost-Based Mission Scheduling 11th ICCRTS, Coalition Command and Control in the Networked Era, 2006. cited by examiner Moss, Paula et al., Multi-mission Prioritiziation Using Cost-Based Mission Scheduling 11th ICCRTS, Coalition Command and Control in the Networked Era, 2006, PowerPoint Presentation. cited by examiner Santos, Eugene Jr. et al.. Achieving dynamic, multi-commander, multi-mission planning and execution Appl. Intell., vol. 25, 2006. cited by examiner Rui, Xu et al., Design for autonomous mission planning system Aircraft Engineering and Aerospace Technology, vol. 25, No. 4, 2003. cited by examiner Goldman, Robert P. et al., MACBETH: A Multi-Agent Constraint Based Planner IEEE, 2002. cited by examiner Hillard, Michael R. et al., Scheudling the Operation Desert Storm Airlift: An Advanced Automated Scheduling Support System Interfaces, vol. 22, Jan.-Feb. 1992. cited by examiner Koepke, Corbin G., Multi-Mission Optimized Re-Planning In Air-Mobility Command's Channel Route Execution Massachusetts Institute of Technology, Jun. 2004, Abstract. cited by examiner Hillard, Michael R. et al., Scheduling the Operation Dessert Storm Airlight: An Advanced Automated Scheduling Support System, Interfaces, vol. 22, Jan.-Feb. 1992. cited by examiner Freed, Michael, Reactive Prioritization In Proceedings of the 2nd NASA International Workshop on Planning and Scheduling in Space, 2000. cited by examiner Atkins, Ella M., Planning and Resource Allocation for Hard Real-time, Fault-Tolerant Plan Execution Kluwer, Oct. 9, 1999. cited by examiner Levine, David L. et al., Dynamic Scheduling Strategies for Avionics Mission Computing in Proceedings of the 17th IEEE/AIAA Digital Avionics Systems Conference, 1998. cited by examiner M.A. Becker, et al., “Mixed initiative resource management: The AMC Barrel allocator,” In Proceedings of the Fifth International Conference on AI Planning and Scheduling, pp. 32-41, Breckenridge, CO, Apr. 2000. cited by other S. Billups, et al., “Satellite mission scheduling with dynamic tasking,” Mathematics Clinic, Univ. of Colorado, Denver. http://www-math.cudenver,edu/clinic/reports/ClinicReportSpring2005.pdf.gz, Spring 2005. cited by other R. Cheng and M. Gen, “Evolution program for resource constrained project scheduling problem,” in Proceedings of the First IEEE Conference on Evolutionary Computational Intelligence, 2, pp. 736-741, 1994. cited by other T. Dean and M. Boddy, “An analysis of time-dependant planning,” In Proceedings of the Sevent National Conference on Artificial Intelligence, pp. 49-54, Minneapolis, Minnesota, 1988. cited by other J. Dorn, et al., “Comparison of iterative improvement techniques for schedule optimization,” In European Journal of Operations Research, 94(2), pp. 349-361, 1996. cited by other M. Hindsberger, et al., “Tabu search for target-radar allocation,” Technical Report, IMM Publications, http://www2.imm.dtu.dk/pubdb/views/edoc—download.php/506/pdf/imm506.pdf , 1998. cited by other E. Johnson, et al., “A high capacity object oriented mission scheduling system for XTE,” In Astronomical Data Analysis Software and Systems V, pp. 463-466, 1996. cited by other K. Mesghouni, et al., “Evolution programs for job-shop scheduling,” In IEEE Transactions on Systems, Man, and Cybernetics, pp. 720-25, 1997. cited by other L. Ozdamar, “A genetic algorithm approach to a general category project scheduling problem,” In IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews, 29(1), Feb. 1999. cited by other G. Rabideau, et al., “Using iterative repair to automate planning and scheduling of shuttle payload operations,” In Innovative Applications of Artificial Intelligence (IAAI), Orlando, FL, Jul. 1999. cited by other S.J. Russell, “Composing real-time systems,” In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, pp. 212-217, Sydney, Australia, 1991. cited by other G. Shi, “A new encoding scheme for solving job shop problems by genetic algorithm,” In Proceedings of the 35th Conference on Decision and Control, Kobe, Japan, Dec. 1996. cited by other A. Shtub, et al., “Scheduling programs with repetitive projects: A comparison of a simulated annealing, a genetic and a pair-wise swap algorithm,” In European Journal of Operations Research, 88, pp. 124-138, 1996. cited by other T. Yamada, et al., “A simulated annealing approach to job shop scheduling using critical block transition operators,” In Proceedings of the IEEE International Conference on Neural Networks (ICNN), pp. 4687-4692, 1994. cited by other S. Zilberstein, “Optimizing Decision Quality with Contract Algorithms,” In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pp. 1576-82, Montreal, Canada, 1995. cited by other S. Zilberstein, “Using anytime algorithms in intelligent systems,” In AI Magazine, 17(3), pp. 73-73, 1996. cited by other |
| Primary Examiner: | Jarrett, Scott L |
| Attorney, Agent or Firm: | Tope-McKay & Assoc. |
| رقم الانضمام: | edspgr.07895071 |
| قاعدة البيانات: | USPTO Patent Grants |
| الوصف غير متاح. |