Systems, devices, and methods for allocation of workpiece transfers in multi-machine, multi-process production systems

1 . A method of generating a schedule for a plurality of machines and robots, the method comprising:

receiving a production-system description that describes respective operations that can be performed on workpieces by each of a plurality of machines and that describes capabilities of one or more robots to transfer the workpieces to and from each of the plurality of machines;

receiving a process description that describes at least one sequence of process operations to be performed on a workpiece;

constructing a plurality of transfer chains by recursively generating transfer chains based on a production-system state, the process description, and on the production-system description, wherein the plurality of transfer chains include a parent transfer chain and one or more child transfer chains that were recursively generated from the parent transfer chain,

wherein the production-system state describes, at a respective point in time in a series of points in time, a respective state of each machine of the plurality of machines, a respective state of each robot of the one or more robots, and a respective state of each workpiece that is held by either a robot of the one or more robots or a machine of the plurality of machines; and

selecting a particular transfer chain of the plurality of transfer chains based on one or more selection criteria.

2 . The method of claim 1 ,

wherein the workpieces are wafers, and

wherein the respective operations that can be performed on workpieces by each of the plurality of machines are semiconductor-fabrication operations.

3 . The method of claim 1 , wherein the one or more selection criteria include the longest transfer chain in the plurality of transfer chains.

4 . The method of claim 1 , wherein the one or more selection criteria include minimizing a standard deviation of a dwell time between depositing formable material on each workpiece and planarizing the formable material.

5 . The method of claim 1 , wherein the one or more selection criteria include minimizing the duration of the particular transfer chain.

6 . The method of claim 1 ,

wherein the respective state of each machine of the plurality of machines includes one of the following operating statuses: idle, operating on a workpiece, and finished operating on a workpiece and waiting for the workpiece to be unloaded; and

wherein the respective state of each robot of the one or more robots includes one of the following operating statuses: idle, moving toward one of the plurality of machines, unloading a workpiece from one of the plurality of machines, and loading a workpiece onto one of the plurality of machines.

7 . The method of claim 1 , wherein each transfer chain of the plurality of transfer chains includes a respective sequence of transfer tasks,

wherein recursively generating the transfer chains includes repeatedly generating a transfer task for a respective transfer chain, of the transfer chains, and then generating all valid transfer tasks that can follow the transfer task in the respective transfer chain.

8 . The method of claim 1 , wherein constructing the plurality of transfer chains and selecting the particular transfer chain are performed while the machines are operating on workpieces.

9 . The method of claim 1 ,

wherein the parent transfer chain includes a sequence of transfer tasks, and

wherein each child transfer chain, of the one or more child transfer chains, includes the sequence of transfer tasks and one or more respective additional transfer tasks that follow the first sequence of transfer tasks.

10 . A system for operating on workpieces, the system comprising:

a plurality of machines that are configured to operate on workpieces;

a plurality of transfer robots, wherein each transfer robot of the plurality of transfer robots respectively comprises one or more transfer arms that are each configured to carry the workpieces;

one or more memories; and

one or more processors, wherein the one or more processors and the one or more memories are configured to

obtain a production-system description that describes respective operations that can be performed on the workpieces by each of the plurality of machines and that describes capabilities of the plurality of robots to transfer the workpieces to and from each of the plurality of machines;

obtain a process description that describes at least one sequence of process operations to be performed on a workpiece;

generate a first plurality of transfer chains based on a first production-system state, the process description, and on the production-system description, wherein each transfer chain of the first plurality of transfer chains includes a respective sequence of transfer tasks, wherein generating the first plurality of transfer chains includes recursively performing a transfer-task-addition process in which an instance of the transfer-task-addition process invokes another instance of the transfer-task-addition process,

wherein the first production-system state describes, at a first point in time, a respective state of each machine of the plurality of machines, a respective state of each robot of the plurality of robots, and a respective state of each workpiece that is held by either a robot of the one or more robots or a machine of the plurality of machines; and

select a first particular transfer chain of the first plurality of transfer chains based on one or more selection criteria.

11 . The system of claim 10 , wherein the one or more processors and the one or more memories are further configured to:

generate a second plurality of transfer chains by recursively generating transfer chains based on a second production-system state, the process description, and on the production-system description,

wherein the second production-system state describes, at a second point in time after the first point in time of the first production-system state, a respective state of each machine of the plurality of machines, a respective state of each robot of the plurality of robots, and a respective state of each workpiece that is held by either a robot of the one or more robots or a machine of the plurality of machines; and

select a second particular transfer chain of the second plurality of transfer chains based on the one or more selection criteria.

12 . The system of claim 11 , wherein the one or more selection criteria include maintaining a constant workpiece-transfer time from a first machine to a second machine of the plurality of machines.

13 . The system of claim 10 , wherein the capabilities of the plurality of robots to transfer workpieces to and from each of the plurality of machines indicates, for each transfer arm of each robot of the plurality of robots, the machines of the plurality of machines that can be loaded and unloaded by the transfer arm.

14 . The system of claim 10 , wherein the first plurality of transfer chains forms a tree of transfer tasks.

15 . The system of claim 10 , wherein the one or more processors and the one or more memories are further configured to:

control a transfer robot of the plurality of transfer robots to execute the respective sequence of transfer tasks in the first particular transfer chain.

16 . The system of claim 10 , wherein the one or more selection criteria include one or more of the following: the longest transfer chain in the first plurality of transfer chains, minimizing a standard deviation of a dwell time between depositing formable material on each workpiece and planarizing the formable material, minimizing the duration of the particular transfer chain.

17 . A method of generating a schedule for a transfer robot, the method comprising:

obtaining a production-system description that describes respective operations that can be performed on workpieces by each of a plurality of machines and that describes capabilities of one or more robots to transfer the workpieces to and from each of the plurality of machines, wherein the one or more robots include a first robot;

obtaining a process description that describes at least one sequence of process operations to be performed on workpieces;

generating a future production-system state based on the process description and on the production-system description, wherein the future production-system state describes, at a future point in time, a respective state of each machine of the plurality of machines, a respective state of each robot of the one or more robots, and a respective state of each workpiece that is held by either a robot of the one or more robots or a machine of the plurality of machines;

generating a plurality of transfer chains for the first robot based on the future production-system state, on the process description, and on the production-system description, and on respective future states of the first robot in the plurality of transfer chains, wherein each transfer chain of the plurality of transfer chains includes a respective sequence of transfer tasks, and wherein the plurality of transfer chains include a first transfer chain and a second transfer chain that share at least one transfer task; and

selecting a particular transfer chain of the plurality of transfer chains based on one or more selection criteria.

18 . The method of claim 17 , wherein generating a transfer chain of the plurality of transfer chains includes generating a first transfer task, determining a future state of the first robot upon the completion of the first transfer task, and generating all valid transfer tasks that can follow the first transfer task based on the future state of the first robot, on the respective states of machines of the plurality of machines that are reachable by the first robot, and on the respective state of each workpiece that is held by either the first robot of the one or more robots or the machines of the plurality of machines that are reachable by the first robot.

19 . The method of claim 17 , wherein generating a transfer chain of the plurality of transfer chains includes:

obtaining a parent transfer task; and

performing instances of a transfer-task generation process that includes:

(a) determining a future state of the first robot upon the completion of the parent transfer task; and

(b) generating all valid child transfer tasks that can follow the parent transfer task based on the future state of the first robot, the respective states of machines of the plurality of machines that are reachable by the first robot, and the respective state of each workpiece that is held by either the first robot of the one or more robots or the machines of the plurality of machines that are reachable by the first robot,

wherein the instances of the transfer-task generation process include, for each valid child transfer task of the valid child transfer tasks generated in (b), a respective instance of the transfer-task generation process that uses the valid child transfer task as the parent transfer task.

20 . The method of claim 17 , wherein the particular transfer chain includes a scheduled time period of execution, and wherein the method further comprises:

marking any machine of the plurality of machines with which the first robot is scheduled to perform a transfer task included in the particular transfer chain as blocked for the scheduled time period of execution.