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.
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.
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.
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
criteria is tight and informative for real-world structured problems.