Scheduling method for robotic manufacturing processes

A method for planning and controlling a processing of a group of objects by a cluster tool, the cluster tool having resources that respectively include each of a plurality of process modules, each of the process modules performing a desired process on selected objects of the group of objects while each of the selected objects are located in each of the process modules, the resources further including a manipulator that, on a plurality of respective carrying paddles, carries and moves the objects into and out of the process modules in a series of discrete movements, the carrying paddles and the process modules each defining a single respective object location, each object location being constructed and arranged to have located thereat only one object of the group of objects at any time, operations being performed by the resources on the objects, wherein the operations each occur to a single one of the objects using predetermined resources of the resources and occurring at corresponding predetermined of the object locations, the operations each having an operation time period defined by a predetermined operation start time and an operation time duration, each object having a sequence of operations performed thereupon including (a) an initial operation of moving the related object to one of the paddles from an initial location, (b) a final operation of moving the related object to a final location from one of the paddles and (c) intervening operations between the initial operation and the final operation, wherein there are a plurality of sets of the operations each respectively performed upon each related object and, by each of the sets of the operations, each related object is moved from one of the paddles on which it is located to a desired process module, the related object is processed by the desired process module and the related object is moved from the desired process module to one of the paddles, the object locations being occupied by respective objects for a respective occupancy time period, each occupancy time period starting at a start of an operation that moves an object to the object location and ending at an end of an earliest subsequent operation that moves the object from the object location, the method comprising the steps of:

• 1. planning discrete movements and processing each object of the group of objects, in turn, in desired process modules, the step of planning, for each of the object, including:
• A. assigning operation start times for operations in a sequence of operations related to the object, including:
• i. setting each operation start time for the related object so that the operation start time follows an immediately preceding operation time period for the related object;
• ii. setting each operation start time for the related object so that, for each resource to be used for the respective operation, the operation time period is free of overlap with all previously set operation time periods for operations using the same resource for other objects;
• iii. setting each operation start time for the related object so that, for each specific operation location for a respective operation, the operation time period is free of overlap with any previously set occupancy time period for the specific operation location for operations performed upon other objects, and
• iv. setting each operation start time to start as early as possible based upon each of steps 1A(i) and 1A(ii) and 1A(iii);
• B. i. interrupting each of steps 1A(i), 1A(ii), 1A(iii) and 1A(iv) when an operation start time (T), for a respective operation-to-be-set (OP2), for the related object that includes a sequence of operations having at least a first operation (OP1) through a last operation (OP2), wherein OP1 is a movement of a selected object (O) to a selected object location (L) and OP2 is a subsequent removal of O from L, is set so that an operation time period for a prior operation at L for another object overlaps any time from an end of OP1 to a start of OP2, and thereafter,
• ii. restarting step 1A from OP1 with the operation start time of OP1 not less than T;
• C. after all desired operation start times are set in steps A and B, revising the operation start times for all previously set operations in reverse order from a next-to-last operation to a first operation by adding the lesser of:
• i. a time duration from the end of the operation time period of an operation start time being revised to an operation start time of a earliest subsequent operation time period for the related object and
• ii. a time duration from an end of the operation time period of the operation start time being revised to the operation start time of an earliest subsequent operation time period for a previously planned operation for another object using any of the same resources as used by the operation with the revised operation start time;
• D. repeating steps 1A, 1B, and 1C, each time setting the operation start time of the first operation for the related object to be greater than the operation start time of the first operation set in an immediately preceding set of steps 1A, 1B, and 1C until the operation start time for the last operation for the related object changes relative to the operation start time for the last operation in the immediately preceding set of steps 1A, 1B and 1C, and setting each of the operation start times in the sequence of operations for the next related object as the corresponding operation start times from the immediately preceding steps 1A, 1B and 1C;
• and
• 2.