Method and system for splitting scheduling problems into sub-problems

Patent metadata

Field	Value
Publication number	US-9798947-B2
Application number	US-201213655934-A
Country	US
Kind code	B2
Filing date	Oct 19, 2012
Priority date	Oct 31, 2011
Publication date	Oct 24, 2017
Grant date	Oct 24, 2017

Abstract

A computing system receives user input of scheduling problem data. The scheduling problem data relates to a scheduling problem and includes one or more stations and tasks to be performed by at least one station. The computing system constructs a graph problem using the scheduling problem data. The graph problem includes a graph. The computing system cuts the graph into sub-graphs using a cut algorithm to create a cut result that satisfies a threshold and identifies one or more task exceptions from the sub-graphs in the cut result. The one or more task exceptions are tasks that can be assigned to more than one sub-graph. The computing system creates scheduling sub-problems pertaining to the one or more task exceptions using the cut result.

First claim

What is claimed is:

1. A method comprising:
receiving, by a processing device, user input of first scheduling data in a first format to schedule a plurality of tasks to be performed by a plurality of stations of a manufacturing system, the first scheduling data comprising the plurality of stations, the plurality of tasks, information indicating, for each of the plurality of tasks, one or more corresponding stations of the plurality of stations that is capable of performing a corresponding task of the plurality of tasks, and a number of a plurality of combinations of tasks and stations, wherein a scheduling system of the manufacturing system is unable to process the number of the plurality of combinations in the first format;
creating, by the processing device, second scheduling data in a second format, the second format comprising a graph and a plurality of nodes in the graph to represent the plurality of stations;
determining, by the processing device, one or more pairs of nodes of the plurality of nodes in the graph having at least one respective task of the plurality of tasks that is common to nodes in respective pairs of nodes;
creating, by the processing device, node connectors in the graph to represent the one or more pairs of nodes of the plurality of nodes having the at least one respective task of the plurality of tasks that is common to the nodes in the respective pairs of nodes;
applying, by the processing device, a weight to one or more node connectors in the graph based on the at least one respective task of the plurality of tasks that is common to the nodes in the respective pairs of nodes;
creating, by the processing device, a plurality of partitions of the graph based on the weight applied to the one or more node connectors in the graph;
determining, by the processing device, from the plurality of partitions of the graph, one or more task exceptions that are associated with a respective partition, wherein the one or more task exceptions are tasks that are eligible to be processed by stations that are represented by nodes in different partitions;
for each of the plurality of partitions, grouping, by the processing device, a subset of stations in the respective partition with a corresponding task subset;
creating, by the processing device, a new task set comprising the one or more task exceptions;
creating, by the processing device, a plurality of new representations of the plurality of partitions in a third format that is compatible with the scheduling system, the plurality of new representations reducing the number of the plurality of combinations of tasks and stations based on the grouping; and
initiating, by the processing device, the scheduling system to generate a schedule for performing, by the one or more stations, the plurality of tasks based on the plurality of new representations in the third format that is compatible with the scheduling system and the new task set comprising the one or more task exceptions, wherein the manufacturing system is to perform the plurality of tasks based on the schedule.

2. The method of claim 1 , wherein creating the plurality of partitions of the graph comprises:
partitioning the graph to have a fewest number of tasks eligible to be processed by stations that are represented by nodes in different partitions, a fewest number of types of tasks, or a fewest number of task recipes comprising tasks eligible to be processed by stations that are represented by nodes in different partitions.

3. The method of claim 1 , wherein the node connectors comprise lines connecting one or more pairs of the plurality of nodes to represent tasks relating to the stations corresponding to the connected nodes.

4. The method of claim 1 , wherein the weight indicates at least one of a number of tasks associated with the stations corresponding to the pair of nodes, a percentage of tasks associated with the stations corresponding to the pair of nodes, or a task priority.

5. The method of claim 1 , wherein the plurality of tasks are processed in a specified flow order.

6. The method of claim 1 , wherein the plurality of tasks relate to manufacturing semiconductors.

7. A non-transitory computer readable storage medium including instructions that, when executed by a processing device, cause the processing device to perform operations comprising:
receiving user input of first scheduling data in a first format to schedule a plurality of tasks to be performed by a plurality of stations of a manufacturing system, the first scheduling data comprising the plurality of stations, the plurality of tasks, information indicating, for each of the plurality of tasks, one or more corresponding stations of the plurality of stations that is capable of performing a corresponding task of the plurality of tasks, and a number of a plurality of combinations of tasks and stations, wherein a scheduling system of the manufacturing system is unable to process the plurality of combinations in the first format;
creating second scheduling data in a second format, the second format comprising a graph and a plurality of nodes in the graph to represent the plurality of stations;
determining one or more pairs of nodes of the plurality of nodes in the graph having at least one respective task of the plurality of tasks that is common to nodes in respective pairs of nodes;
creating node connectors in the graph to represent the one or more pairs of nodes of the plurality of nodes having the at least one respective task of the plurality of tasks that is common to the nodes in the respective pairs of nodes;
applying a weight to one or more node connectors in the graph based on the at least one respective task of the plurality of tasks that is common to the nodes in the respective pairs of nodes;
creating, by the processing device, a plurality of partitions of the graph based on the weight applied to the one or more node connectors in the graph;
determining, by the processing device, from the plurality of partitions of the graph, one or more task exceptions that are associated with a respective partition, wherein the one or more task exceptions are tasks that are eligible to be processed by stations that are represented by nodes in different partitions;
for each of the plurality of partitions, grouping, by the processing device, a subset of stations in the respective partition with a corresponding task subset;
creating, by the processing device, a new task set comprising the one or more task exceptions;
creating, by the processing device, a plurality of new representations of the plurality of partitions in a third format that is compatible with the scheduling system, the plurality of new representations reducing the number of the plurality of combinations of tasks and stations based on the grouping; and
initiating, by the processing device, the scheduling system to generate a schedule for performing, by the one or more stations, the plurality of tasks based on the plurality of new representations in the third format that is compatible with the scheduling system and the new task set comprising the one or more task exceptions, wherein the manufacturing system is to perform the plurality of tasks based on the schedule.

8. The non-transitory computer readable storage medium of claim 7 , wherein creating the plurality of partitions of the graph comprises:
partitioning the graph to have a fewest number of tasks eligible to be processed by stations that are represented by nodes in different partitions, fewest number of types of tasks, or a fewest number of task recipes comprising tasks eligible to be processed by stations that are represented by nodes in different partitions.

9. The non-transitory computer readable storage medium of claim 7

Assignees

• Applied Materials Inc

Inventors

• Norman David Everton

Classifications

• G06Q10/06311 Primary

  Scheduling, planning or task assignment for a person or group · CPC title

• G06T2207/10072

  Tomographic images · CPC title

• G06F8/45

  Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions · CPC title

• G06T7/12

  Edge-based segmentation · CPC title

• G06T7/11

  Region-based segmentation · CPC title