Uniprocessor Schedulability Test and Scheduler for Industrial Robotic Manufacturing

Technology #15539-15540

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Categories
Inventors
Professor Julie Shah
Department of Aeronautics and Astronautics
External Link (people.csail.mit.edu)
Matthew Gombolay
MIT Lincoln Laboratories
Managed By
Daniel Dardani
MIT Technology Licensing Officer
Patent Protection

Uniprocessor schedulability testing for non-preemptive task sets

US Patent Pending 2013-0290970
Publications
A Uniprocessor Scheduling Policy for Non-Preemptive Task Sets with Precedence and Temporal Constraints
Infotech@ Aerospace, 2012, p. 2431

Applications

This scheduling solution is designed to achieve high-quality sequencing of human and robotic workers in a myriad of industry applications including engineering, aerospace and commercial manufacturing.

Problem Addressed

Industrial robots can provide significant flexibility in manufacturing operations compared to the current state-of-the-art large, gantry-style automated solutions. Harnessing the full capability of these robotic systems requires coordinating work-sharing and scheduling among multiple human workers and robots to achieve safety and high productivity despite inevitable disturbances due to robot servicing and other unanticipated delays in the build process. The Inventors have developed a solution for flexible work sequencing and scheduling (WSS) capable of automatically rescheduling a robot’s action sequence to adapt to changes in a work plan, while guaranteeing hard scheduling deadlines are met.

Technology

This computationally efficient approach for performing factory-relevant scheduling relies on modeling the robotic and human workers in the system as processors within a computer. The build piece (e.g. the part currently being worked on) is modeled as a shared memory resource that the “processors” (human and robotic workers) must coordinate to access. The full solution to the multi-robot coordination problem relies on the efficient solution to this single robot scheduling problem.

Assembly tasks are related through precedence constraints, where tasks must be completed within a given time window, and wait constraints, where a given task must be started a minimum time t after a previous task ends. A check is performed to determine whether deadline constraints are temporally consistent with the task costs, wait constraints, and network structure, and whether a task set can be executed in parallel with a set of currently executing deadline constraints. Once it is established that these task sets are “well-formed” according to these composability rules, a sufficient schedulability criteria is computed in polynomial time. The Inventors provide an Earliest Deadline First (EDF)-based scheduling strategy for task sets that meet this schedulability criteria, a method shown to be optimal for uniprocessor environments.

Advantages

  • Approach is far more efficient and scalable than previous state-of-the-art scheduling solutions which can take up to hours to compute a feasible schedule
  • Flexible scheduling adapts to changes in the work plan while still meeting hard deadlines
  • Schedulability criteria is tight and informative for real-world structured problems.