Controlling operation of machine tools using combinatorial optimization problem solvers
Methods, systems and apparatus, including computer programs encoded on computer storage medium, for processing parts using machine tool workstations. The machine tool workstations are grouped into multiple groups, where each group includes workstations of the same type. For each of the multiple groups, data representing parts to be processed by the type of workstations included in the group are transmitted to a combinatorial optimization problem solver. Data representing a sequence of ordered subsets of the multiple parts that produce a reduced setup time for the workstations in the group are received from the solver. An average delay time associated with the generated sequence of ordered subsets of the collection of parts is computed. If the average delay time is less than the predetermined threshold, parts are released according to the generated sequence of ordered subsets of the collection of parts to the group for processing.
1. A method comprising:
grouping, by one or more computers that are in data communication with a collection of machine tool workstations that are used to process a plurality of parts, the plurality of machine tool workstations into multiple functional groups, wherein each functional group includes machine tool workstations of the same type;
for each of the multiple functional groups:
transmitting, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, and to a combinatorial optimization problem solver, data representing multiple parts to be processed by the type of workstations included in the functional group;
receiving, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, and from the combinatorial optimization problem solver, data representing a sequence of ordered subsets of the multiple parts that, when processed by the functional group, produces a reduced set up time for the workstations in the functional group;
computing, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, an average delay time associated with the generated sequence of ordered subsets of the multiple parts;
determining, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, whether the average delay time is less than a predetermined threshold;
in response to determining that the average delay time is less than the predetermined threshold, releasing, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, parts according to the generated sequence of ordered subsets of the multiple parts to machine tool workstations in the functional group for processing; and
processing, by the machine tool workstations in the functional group that are in data communication with the one or more computers, the released parts according to the generated sequence of ordered subsets of the multiple parts to generate processed parts.
2. A system comprising:
a collection of machine tool workstations used to process a plurality of parts;
one or more computers in data communication with the collection of machine tool workstations;
a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
grouping the collection of machine tool workstations into multiple functional groups, wherein each functional group includes workstations of the same type;
for each of the multiple functional groups:
transmitting, to a combinatorial optimization problem solver, data representing multiple parts to be processed by the type of workstations included in the functional group;
receiving, from the combinatorial optimization problem solver, data representing a sequence of ordered subsets of the multiple parts that, when processed by the functional group, produces a reduced set up time for the workstations in the functional group;
computing an average delay time associated with the generated sequence of ordered subsets of the multiple parts;
determining whether the average delay time is less than a predetermined threshold;
in response to determining that the average delay time is less than the predetermined threshold, releasing parts according to the generated sequence of ordered subsets of the multiple parts to the functional group for processing.
3. The system of claim 2 , wherein the plurality of machine tool workstations comprise one or more of (i) cutting tools, (ii) drilling machines, (iii) lathes, (iv) boring machines, or (v) grinding machines.
4. The system of claim 2 , wherein each workstation is associated with a set of performance parameters, the set comprising workstation setup time and part delivery time.
5. The system of claim 2 , wherein workstations of a same type comprise workstations with a common Kanban inventory.
6. The system of claim 2 , wherein each functional group is configured to receive a constrained number of days of work in progress per batch of parts, wherein the number of days depends on an average setup and machining time per part over each workstation in the functional group.
7. The system of claim 6 , wherein a number of the multiple functional groups is dependent on computational capabilities of the combinatorial optimization problem solver and properties of the plurality of machine tool workstations.
8. The system of claim 7 , wherein properties of the plurality of machine tool workstations comprise one or more of (i) location of machine tool workstation, (ii) an acceptable uninterrupted machine tool workstation runtime.
9. The system of claim 2 , wherein the combinatorial optimization problem solver is configured to solve travelling salesman problems.
10. The system of claim 2 , wherein the combinatorial optimization problem solver is configured to implement a cutting-plane method.
11. The system of claim 2 , wherein the method further comprises selecting, based on the data representing the multiple parts to be processed by the type of workstations included in the functional group, the combinatorial optimization problem solver from multiple available combinatorial optimization problem solvers and transmitting the data representing the multiple parts to be processed by the type of workstations included in the functional group to the selected combinatorial optimization problem solver.
12. The system of claim 2 , wherein the size of the ordered subsets is dependent on acceptable uninterrupted machine tool workstation runtimes.
13. The system of claim 2 , wherein releasing parts according to the generated sequence of ordered subsets of the multiple parts to the functional group for processing generates processed parts, and wherein the method further comprises routing one or more subsets of the processed parts to other functional groups for further processing.
14. The system of claim 2 , wherein determining the average delay time comprises applying Little's Law.
15. The system of claim 2 , wherein determining whether the average delay time is less than a predetermined threshold comprises:
computing a standard deviation of delay time;
adding a multiple of the computed standard deviation to the computed average delay time to generate an adjusted average delay time; and
determining whether the adjusted average delay time is less than the predetermined threshold.
16. The system of claim 2 , further comprising, in response to determining that the average delay time exceeds the predetermined threshold:
iteratively reducing the size of the ordered subsets in the generated sequence of ordered subsets until the average delay time is less than the predetermined threshold.
17. The system of claim 2 , wherein the subset size is equal to one, and wherein the method further comprises releasing a random sequence of parts to next available machine tool workstations.
18. One or more non-transitory computer-readable media storing instructions that, when executed by one or more computers that are in data communication with a collection of machine tools that are used to process a plurality of parts, cause the one or more computers that are in data communication with the collection of machine tools that are used to process the plurality of parts to perform operations comprising: grouping, by the one or more computers that are in data communication with a collection of machine tool workstations that are used to process a plurality of parts, the plurality of machine tool workstations into multiple functional groups, wherein each functional group includes machine tool workstations of the same type; for each of the multiple functional groups: transmitting, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, and to a combinatorial optimization problem solver, data representing multiple parts to be processed by the type of workstations included in the functional group; receiving, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, and from the combinatorial optimization problem solver, data representing a sequence of ordered subsets of the multiple parts that, when processed by the functional group, produces a reduced set up time for the workstations in the functional group; computing, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, an average delay time associated with the generated sequence of ordered subsets of the multiple parts; determining, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, whether the average delay time is less than a predetermined threshold; and in response to determining that the average delay time is less than the predetermined threshold, releasing, by the one or more computers that are in data communication with the collection of the machine tool workstations that are used to process the plurality of parts, parts according to the generated sequence of ordered subsets of the multiple parts to machine tool workstations in the functional group for processing.