Uniprocessor Schedulability Test and Scheduler for Task Sets with Well-Formed Precedence Relations, Temporal Deadlines, and Wait Constraints

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.  

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.  

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  

Publications

"A Uniprocessor Scheduling Policy for Non-Preemptive Task Sets with Precedence and Temporal Constraints." American Institute of Aeronautics and Astronautics, 2012, 2431.