OPTIMIZED FACTORY SCHEDULE AND LAYOUT GENERATION

Abstract

Systems and methods for optimizing factory scheduling, layout or both which represent active factory elements (human and machine) as computational objects and simulate factory operation to optimize a solution. This enables the efficient assembly of customized products, accommodates variable demand, and mitigates unplanned events (floor blockages, machines/IMRs/workcell/workers downtime, variable quantity, location, and destination of supply parts).

Claims

1-32. (canceled)

33. A method of scheduling, for execution in a facility having a layout, the method comprising the steps of: (a) storing, in a computer memory, a plurality of object data structures each corresponding to a machine or a human and containing data and/or instructions for simulating behavior in (i) carrying out a task, (ii) allowed movement about the facility, (iii) speed of operation and movement based on inherent characteristics of the machine or the human and proximity thereof to other objects, wherein the object data structures include parameter values constraining the simulated behavior and at least some of the machines are mobile; (b) receiving, by a computational simulator, a work order and an objective function specifying a quantity to be maximized and a representation of at least a portion of the layout; (c) based on the work order, simulating, using the computational simulator and the stored object data structures, performance of the work including movement of the mobile machines in the facility along one or more planned paths; (d) iteratively repeating step (c) with object parameter values and paths that have been updated in accordance with, respectively, an optimization algorithm and a path-planning algorithm until the quantity specified by the objective function is maximized; and (e) generating an operation schedule for the machines represented by object data structures.

34. The method of claim 33, wherein the path-planning algorithm finds the best path for a given set of performance metrics.

35. The method of claim 34, wherein the path-planning algorithm uses position and orientation measurements and a motion model of the mobile machines to estimate current and near-future positions and orientation of the mobile machines during performance of the task.

36. The method of claim 35, wherein the path-planning algorithm estimates long-term future states of the mobile machines based on current paths, motion models, and movement constraints.

37. The method of claim 34, further comprising predicting collisions between mobile machines during simulated performance of the work.

38. The method of claim 37, wherein the the path-planning algorithm is responsive to the predicted collisions in generating the best paths.

39. The method of claim 38, wherein the predicted collisions are used to define safety regions around the mobile machines.

40. The method of claim 33, wherein the mobile machine objects specify (i) capability parameter values including a movement speed range of the mobile machine and (ii) behavior parameter values including speed restrictions of the mobile machine based on proximity of the mobile machine to machines or humans represented by other objects.

41. The method of claim 40, wherein the capability parameter values further include a payload capacity of the machine.

42. The method of claim 40, wherein the mobile machine objects further specify loading and unloading capabilities.

43. The method of claim 33, wherein the objective function specifies at least one of (i) minimum time for work order completion, (ii), output quantity, (iii) output quality, (iv) safety to humans, (v) minimum power consumption, (vi) a production cost function, or (vii) a production profit function.

44. The method of claim 33, wherein the optimization algorithm is a continuous optimization algorithm.

45. The method of claim 33, wherein the optimization algorithm is a reinforcement learning algorithm.

46. The method of claim 33, wherein the optimization algorithm is a linear program.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0023] In the drawings, like reference characters generally refer to the same parts throughout the different views. Also, the drawings are not necessarily to scale, with an emphasis instead generally being placed upon illustrating the principles of the invention. In the following description, various embodiments of the present invention are described with reference to the following drawings, in which:

[0024] FIG. 1 schematically illustrates a factory simulation system for layout and scheduling in accordance with embodiments of the invention.

[0025] FIG. 2 is a flowchart showing exemplary operation of a layout simulation subsystem in accordance with embodiments of the invention.

[0026] FIG. 3 is a representative precedence graph in in accordance with embodiments of the invention.

[0027] FIG. 4 schematically illustrates a basic factory layout suitable for use with embodiments of the invention.

[0028] FIG. 5 is a precedence graph corresponding to an initial mapping of groups to workcells in accordance with embodiments of the invention.

[0029] FIG. 6 illustrates an improved mapping of groups to workcells.

[0030] FIG. 7 graphically depicts a methodology for determining a congestion penalty among candidate paths in a factory layout.

[0031] FIGS. 8-10 graphically depict paths followed by a mobile robot in various candidate factory layouts.

[0032] FIG. 11 graphically depicts an exemplary sequence of production tasks whose execution results in production of two products.

[0033] FIG. 12A shows task-execution capabilities of four workcells, and FIG. 12B illustrates a representative layout design for these workcells.

[0034] FIG. 13 depicts a representative [missing word?] generated for the layout design of FIG. 12B.

[0035] FIG. 14A illustrates representation of a factory floor as a grid, and FIG. 14B indicates the locations of the nodes and edges of a transportation network through the grid.

[0036] FIG. 15 illustrates the prediction of a mobile robot position on a given path or trajectory.

[0037] FIG. 16 graphically illustrates an example configuration of two mobile robots and their overlapping safety regions.

[0038] FIG. 17A graphically illustrates a scenario involving the potential collision of two mobile robots and FIG. 17B shows a collision-free path solution for this scenario.

DETAILED DESCRIPTION

1. Representative Architecture

[0039] A representative system is illustrated in FIG. 1. The system 100 includes a processor 110 (e.g., a conventional CPU microprocessor), associated volatile system memory 115 and one or more non-volatile digital storage elements (such as a hard disk, Flash memory, optical drive, etc.). Stored in non-volatile memory are a template store 120, a store 125 for optimized factory layouts, and a store 130 for optimized factory schedules. Any or all of these stores may be organized as databases or simple file hierarchies.

[0040] A user interface 135 permits the user to enter, or specify files containing, factory constraints and requirements 140 that are stored in the system memory 115 and provided to a simulation module 145. The simulation module 145 includes a layout subsystem 150 that accesses data in the template store 120 to produce, in the manner described in detail below, an optimized layout based on the user-provided constraints and factory requirements 140. The template store 120 contains factory objects and, if desired, basic combinations of these objects that are frequently used in factory layouts. The scheduling subsystem 155 takes the optimized layout produced by the layout subsystem 150, or a fixed layout provided by the user, and produces an optimized schedule. The layout and scheduling subsystems 150, 155 can work in tandem (rather than sequentially) to produce an optimized layout and schedule; in this way, scheduling considerations can influence layout optimization.

[0041] The optimized layout and schedule are used to organize and run a physical factory 160, in which raw materials 165 are transformed into finished goods 170.

[0042] The simulation module 145, whose operation is described below, may include one or more modules implemented in hardware, software, or a combination of both. For embodiments in which the functions are provided as one or more software programs, the programs may be written in any of a number of high level languages such as PYTHON, FORTRAN, PASCAL, JAVA, C, C++, C#, BASIC, various scripting languages, and/or HTML. Additionally, the software can be implemented in an assembly language directed to the microprocessor resident on a target computer; for example, the software may be implemented in Intel 80×86 assembly language if it is configured to run on an IBM PC or PC clone. The software may be embodied on an article of manufacture including, but not limited to, a floppy disk, a jump drive, a hard disk, an optical disk, a magnetic tape, a PROM, an EPROM, EEPROM, field-programmable gate array, or CD-ROM. Embodiments using hardware circuitry may be implemented using, for example, one or more FPGA, CPLD or ASIC processors.

2. Factory Objects

[0043] The simulations performed in accordance herewith utilize “factory objects” to represent the various human and machine elements actively involved in the process to be optimized. These elements include workcells, robots, humans, production machinery, work-in-process, tools, and parts. Factory objects may be represented in conventional object-oriented fashion as class types with associated (encapsulated) methods using, e.g., JAVA, C++ or PYTHON. Alternatively, methods can be distinct from the factory objects and executed by the simulation module 145, with the factory objects containing data values that guide the simulator in executing the methods and simulating the object.

[0044] For example, objects corresponding to mobile transport machines may specify (i) capability parameter values including a movement speed range of the mobile transport machine and a payload capacity of the machine, (ii) behavior parameter values including speed restrictions of the mobile transport machine based on proximity of the mobile transport machine to machines or humans represented by other objects, (iii) additional functions on the mobile transport machine, such on-board manufacturing functions or processing, (iv) mobile transport machine loading and unloading capabilities, and (v) information about the mobile transport machine, such as battery life or maintenance intervals. Objects corresponding to production machines may specify (i) capability parameter values including a maximum processing speed of the production machine, (ii) behavior parameter values including speed restrictions of the production machine based on proximity of the production machine to machines or humans represented by other objects, (iii) functions of the production machines, (iv) lifetime and maintenance parameters of the production machines, (v) information about production machine functions that would allow replacement by other machines with different specifications as needed, (vi) a machine support package outlining machine functionality and parameters necessary for operation, such as brand, necessary inputs, and part information.

[0045] A representative set of factory objects appears in Table 1 below. Each of the objects includes a set of associated methods as well as attributes specifying characteristics of, and parameter values associated with, the object. The simulator 145 instantiates specified objects and uses their associated methods and attributes to simulate operation of the elements that the objects represent, including interaction among elements. Frequently, an associated method is generic and, when instantiated, reads the attributes to obtain values for the method variables.

TABLE-US-00001 TABLE 1 Object Associated Methods Attributes Mobile Move from point to point given Autonomous, guided, or remotely transport a floor layout controlled machine/robot Pick up raw material or Payload, physical dimensions and workpiece geometries, speeds Perform manufacturing Turning radius operation on workpiece while Other functions besides transport: on- on mobile transport machine board manufacturing, processing Deliver (offload) raw material Brand, equivalent objects for or workpiece replacement Speed and separation Maintenance schedules and preventive monitoring maintenance Painting Pick part from conveyor or Type and color of paint station mobile transport machine Paint remaining Paint part Primer and finishing processes Offload painted part to available or required conveyor or mobile transport Maintenance schedules and machine instructions No allowed movement Speed and separation monitoring (human may approach) Subtractive Pick part from conveyor or Machining processes available (e.g. metal or mobile transport machine CNC, lathe, mill, drill press, metal plastic Machine or process part bending) fabrication No allowed movement Machine brand and functionality station Speed and separation Maintenance schedules and monitoring or guarding consumables tables Physical dimensions of machines and possible part operations Additive Pick part from conveyor or Additive processes available (e.g. 3D metal or mobile transport machine printing, sintering) plastic Machine or process part Machine brand and functionality fabrication through additive processes Maintenance schedules and station No allowed movement consumables tables Speed and separation Physical dimensions of machines and monitoring or guarding possible part operations Welding Pick parts from conveyor or Weld types possible station mobile transport machine Electrical and mechanical Weld parts characteristics Offload welded parts to Brand and type of welding equipment conveyor or mobile transport Welding recipes machine No allowed movement Speed and separation monitoring (human may approach) General Pick parts from conveyor or Description of type and number of assembly mobile transport machine available tools (power tools, station Humans perform assembly wrenches, etc) operations on workpieces using List of potential assembly operations tools on station possible with existing tool set Put parts back on conveyor or Tool wear and maintenance schedules mobile transport machine Robot station Pick parts from conveyor or Robot arm type, brand and description mobile transport machine (speed, payload, functional Robot perform assembly or applications) manufacturing operations on Description of type and number of workpieces using end of arm available end of arm tooling tools tooling on station (power tools, wrenches, etc.) Put parts back on conveyor or List of potential assembly operations mobile transport machine possible with existing tool set Tool wear and maintenance schedules Parts Store work in progress, Part type and number supermarket assembly parts, or consumables Consumption rates station used in manufacturing process Replacement and refill information No allowed movement Human or mobile transport machine may load or unload parts bin Human Generate potential occupancy Skills and certifications operator envelope based on model of Physical strength human anatomy and movement Shift and health information such as Move from point to point given required breaks a floor layout

3. Layout Optimization

[0046] The flowchart 200 shown in FIG. 2 illustrates the operation of a representative layout subsystem 150. In a first step 210, a work order is received. The work order specifies the constraints and requirements 140, including the operations to be performed and the objective function to be maximized (e.g., throughput) or minimized (e.g., power consumption or emissions). In step 210, the layout subsystem selects a factory layout template or an initial set of factory objects from the template store 120. In the latter case, the layout subsystem 150 may define the set of all possible layouts based on the selected factory objects. One of these may be chosen (step 220) as the current layout, either at random or based on initial application of the provided constraints; this may involve selection of attribute values of the factory objects within their allowed ranges. The performance of the current layout is simulated, and the results of the simulation are evaluated (step 230) based on the objective function. Another layout is chosen, or the current layout is modified, based on an optimization algorithm. In some embodiments, the optimization algorithm is a linear program, such the simplex algorithm. In other embodiments, the optimization algorithm is a machine-learning algorithm such as a continuous optimization algorithm. For example, with each iteration, a step vector may be computed using a fixed update formula, which is then used to modify the iterate. The update formula may be a function of the history of gradients of the objective function evaluated at the current and past iterates. For example, in gradient descent, the update formula is a scaled negative gradient; in momentum, the update formula is a scaled exponential moving average of the gradients. Alternatively, reinforcement learning can be employed. Reinforcement-learning algorithms such as DQN (or other Q-learning algorithms) may use graph representations (such as the precedence graph described below) as the basis upon which a neural network builds an optimal solution according to a probability-based policy that is refined with each iteration; the algorithm finds a policy with the maximum expected return, i.e., a layout best satisfying the objective function.

[0047] The new layout generated with each iteration of the chosen optimization algorithm, which may reflect a new configuration of objects and/or modification of attribute values within the allowed ranges, must satisfy the work order. The performance of this layout is calculated and compared to the current layout. Iteration continues in accordance with the algorithm until the system reaches a termination criterion (step 240) indicating that the objective function has been sufficiently optimized.

[0048] Operation of the layout subsystem 150 may be understood with reference to the following example, in which a bicycle is assembled pursuant to a series of defined tasks. The first step is to identify and list all of the tasks called for or implied by a work order and arrange them into groups as they may be performed in practice. This preparatory step is generally performed manually. A factory object is then defined for each of the tasks. Task object attributes include the task description, time to complete the task, physical and labor inputs required to complete the task, material and labor cost inputs, previous tasks that must or may be performed first (“precedent tasks”), subsequent tasks (“dependent tasks”), and whether the task is optional or specific to a particular finished product.

[0049] Task object attributes may also include tasks that can be considered “adjacent” to each other, so that they may be performed in groups, with tasks mapping to workcells whose object attributes include specific forms of assembly amenable to the particular group. Which tasks can be considered adjacent is a decision typically made by the human operator. Other task object attributes may be particular to a model-specific specific assembly process, and may include options—for example, “Gearing” for tasks involving assembly of bicycles with gears, as opposed to fixed gear; “Braking” for tasks involving assembly of bicycles with brakes; and “Luxury” for tasks involving high-end bicycles with, for example, a basket, headlights, or taillights.

[0050] The grouping of tasks can be made by the human operator, based on the knowledge of the object being assembled, or it may be automated, based on the minimization or maximization of specific task object attributes, such as time to assembly or assembly cost, but taking into account adjacency attributes of the tasks. This grouping can be performed using conventional combinatorial optimization algorithms (see, e.g., G. Boothroyd et al., Product Design for Manufacture and Assembly (2002) and Trevisan, Combinatorial Optimization: Exact and Approximate Algorithms (2011), available at https://theory.stanford.edu/˜trevisan/books/cs261.pdf; both of these references are incorporated herein by reference).

[0051] An example output of the grouping of tasks, including attributes such as adjacency or optionality (e.g. Gearing, Braking, or Luxury), is set forth in Table 2 below. The table contains 34 tasks arranged into 9 groups as they might be performed in practice. For example, tasks 5, 6, and 7 involve rear wheel assembly. Thus, they are adjacent and can be grouped into the “Rear Wheel” group as they are performed at the same time and on the combined physical and labor inputs of those three tasks.

TABLE-US-00002 TABLE 2 Gear- Brak- Lux- Group- Task- Group Task ing ing ury ID ID  0  1 Initial Unpack 1  1  2 Paint  2  3  4 Front Wheel Tire 2  3  5 Brake disks N, Y  4  6  7 Rear Wheel Gear cassette 3  5  8 Brake disks N, Y  6  9 Tire  7 10 11 Build Front Head set 4  8 12 Fork  9 13 Brakes 10 14 Handlebars 11 15 Wheel 12 16 17 Build Middle Bottom bracket 5 13 18 Crank arms 14 19 Derailleur N, Y 15 20 Pedals 16 21 22 Build Rear Derailleur 6 17 23 Brakes 18 24 Wheel 19 25 26 Shifting Chain 7 20 27 Shift lever front N, Y 21 28 Shift cable front N, Y 22 29 Shift level rear 23 30 Shift cable rear 24 31 32 Braking Brake lever front 8 25 33 Brake lever rear 26 34 Brake cable front 27 35 Brake cable rear 28 36 37 Final Seat post 9 29 38 Seat 30 39 Handle grips 31 40 Basket N, Y 32 41 Headlight N, Y 33 42 Taillight N, Y 34

[0052] Attributes for the “Rear Wheel” group are a combination of attributes for each of the individual tasks. For example, the time needed to complete the “Rear Wheel” group assembly may be the simple sum of the times necessary for the three underlying Tasks. This attribute combination may be performed by the human operator.

[0053] In this bicycle example, each group is a partial task sequence, where the term “partial” means it is a subset of the tasks required to build the entire product, yet all groups are required for every bicycle. In this example, a linear dependence attribute is asserted within each task group, i.e., the sequence of tasks within each group must be performed serially in the specified order. Nonlinear dependence is permitted between task groups; that is, groups can depend on one or more previous groups. The key property of nonlinear dependence is that the child group may be completed in any relative temporal order, but all child groups must be completed before their parent task can begin. For example, Shifting or Braking can be performed in either order, but both Shifting and Braking must be completed before Final Assembly.

[0054] As noted, the simplified bicycle task sequence consists of 9 groups, shown with their dependencies as a precedence graph in FIG. 3. Dashed lines define zones based upon dependency, i.e., groups within a zone require one or more groups from the previous zone as input. Groups within each zone can be permuted as shown in Table 3 below. For example, the Build Rear task can only be completed once the Initial and Rear Wheel tasks have been completed. While every task must be completed to assemble the bicycle, there is some freedom in the exact order. The precedence graph may be generated manually or using conventional graphing algorithms.

TABLE-US-00003 TABLE 3 Zone 1 Zone 2 Zone 3 Zone 4 [1, 2, 3] [4, 5, 6] [7, 8] [9] [1, 3, 2] [4, 6, 5] [8, 7] [2, 1, 3] [5, 4, 6] [2, 3, 1] [5, 6, 4] [3, 1, 2] [6, 4, 5] [3, 2, 1] [6, 5, 4]

[0055] Group sequences are the 72 permutations obtained by taking one list from each zone. For example, the first group sequence, spanning zones 1-4, is [1, 2, 3, 4, 5, 6, 7, 8, 9]; the second group sequence is [1, 2, 3, 4, 5, 6, 8, 7, 9], and the 72nd group sequence is [3, 2, 1, 6, 5, 4, 8, 7, 9].

[0056] To model the assembly process, these group sequences are represented in a way that reflects not only their sequence but also their nonlinear dependency. In a given group sequence, each group accepts one or more previous groups but only one following group. This is a “directed tree,” with each parent having one or more children, but each child having only one parent. Exceptions are that groups in zone 1 have no children, and the final group in zone 4 has no parent.

[0057] Every bicycle requires every group for assembly. For each group, the list of tasks may be substituted to produce task sequences each with 34 tasks in unique order. For example,

Sequence Index=37

Group Sequence=[2, 3, 1, 4, 5, 6, 8, 7, 9]

Task Sequence=[3, 4, 5, 6, 7, 1, 2, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 25, 26, 27, 28, 20, 21, 22, 23, 24, 29, 30, 31, 32, 33, 34]

[0058] Each of the 72 task sequences includes all 34 tasks. The variability in task sequences arises from the commutative property of groups within each zone, which arises solely from the group dependency. Table 2 also shows tasks with optional attributes, leading to product variants with fewer than 34 tasks. Because there are 3 optional tasks, each a binary choice, there are 2.sup.3=8 product variants. Each product variant can exploit the 72 options, giving a total of 8×72=576 product variants.

[0059] Assembly sequence planning is one of the well-known combinatorial optimization problems in manufacturing. Once the assembly is represented by a precedence graph, the group objects and their attributes (including optionality), traditional methods of combinatorial optimization may be used to generate a large number of feasible assembly sequences and then find the optimal sequence according to the objective function. Once a precedence graph has been established, the groups are mapped to workcell objects corresponding to physical workcells with dimensions and locations on the factory floor. Suppose that the parts to be assembled are brought into the factory (as represented by a factory object, with attributes relating to workspace area, available utilities, physical dimensions, etc.) from the left and leave the factory, assembled, on the right as shown in FIG. 4. At the bottom of the factory is space for IMRs to queue. Each of the IMRs is represented by an IMR object with attributes specifying speed, payload, geometric format, battery life, etc.

[0060] The initial mapping of groups to workcells (i.e., workcell objects) begins with the precedence graph as shown in FIG. 5. The next step is to optimize the number of workcells per group so as to optimize the objective function—e.g., maximize a profit function (for example, minimize cycle time) or minimize a cost function (for example, capital expenditures or occupied factory floor space). If, for example, group 5 (“Build Middle”) is a particularly lengthy step and is the cycle time bottleneck, a standard optimization algorithm may propose that the tradeoff between the layout of two group 5 workcells (including the cost of the workcell and labor, plus space utilization) would improve a profit function relative to only one group 5 workcell. This “de-bottlenecking” configuration is shown in FIG. 6.

[0061] The next step is to optimize the layout of workcells. Assume that the optimal number of workcells is represented by FIG. 5. Optimizing the layout means accounting for optimal IMR motion—minimizing, for example, total cycle time or IMR total travel. Optimization can exploit the flexible order among tasks and minimize IMR congestion among the workcells in order to optimize the overall efficiency of the factory.

[0062] In one embodiment, the layouts are scored using the product of the total path length and a congestion penalty when paths intersect. The congestion penalty may be a function of the type of intersection involved; for example, with reference to FIG. 7, the penalty may be determined by the number of paths that enter the intersection. An intersection with one entering path has a penalty of 0 because it is never necessary to stop at the intersection. An intersection with two entering paths has a penalty of 1 because, if two vehicles approach the intersection at the same time, one vehicle must wait for the other. Finally, an intersection with three entering paths has a penalty of 2 because two vehicles may have to wait for another vehicle.

[0063] Simulation of thousands of possible workcell layouts using standard optimization algorithms (such as Coffman-Graham or Turán's brick factory algorithm) indicates the layout in FIG. 5 to be one of the least efficient under the metric of (for example) total IMR travel time or minimization of expected IMR collisions. This layout creates a significant amount of congestion because it forces IMRs to cross paths in an unstructured way, resulting in a path length of 150 and a congestion penalty of 20. The workcells are oriented from left to right so that IMRs enter from the left and exit from the right. This means that, for example, were an IMR to start at workcell 1 and proceed to workcell 2, it would have to double back to get to the entrance of workcell 2 as illustrated in FIG. 8. This would create two intersections that could become highly congested choke points. This would not happen in isolation—other IMRs would be moving through the factory as well—so this IMR would potentially cross the paths of several other IMRs in the process.

[0064] Another layout attempted by the simulation, illustrated in FIG. 9, shows the workcells laid out in a 3×3 arrangement. The rows of workcells are aligned entrance-to-exit, providing a natural structure for the IMRs to use for “out-of-order” tasks without creating significant congestion. However, this layout does not take full advantage of the precedence relationship among workcells. As a result, the total path length (219) and congestion penalty (29) are the greatest of the three examples.

[0065] The simulation reveals that the layout shown in FIG. 10 is close to optimal under the constraint of minimizing IMR travel and potential collisions (the path length is 148 and the congestion penalty is 15). This layout is similar to that of FIG. 5, but the workcells are aligned in a manner similar to that shown in FIG. 9. This exploits the precedence graph and creates a structure that reduces IMR congestion and IMR travel time. The orientation of the workcells has been selected to reduce both the total path length (albeit by a small amount) and the congestion penalty. In particular, the high-congestion intersections seen in FIG. 7 are removed.

4. Scheduling Optimization

[0066] A schedule is built by allocating tasks in time for each product unit's task sequence. Hence, scheduling is layout-dependent and scheduling optimization generally follows layout optimization. This need not be the case, however; the processes can be combined, with scheduling optimization applied to intermediate layout candidates. For example, if the objective function maximizes throughput, one approach to optimization is to derive an optimal schedule as described below for a candidate layout and modify the layout in a manner likely to improve the schedule. For example, certain parameters (e.g., the workcell orientation) of the candidate layout may be varied randomly and the schedule simulation re-run and scored. If scheduling improves, the revised layout is retained. In effect, this is a gradient search to another local optimum in the search space from which optimization may continue.

[0067] In general, scheduling optimization may be guided or bounded by fixed rules or principles such as: [0068] 1 Prevent overlapping tasks in a workcell. [0069] 2 Assign a task to a single workcell. [0070] 3 A task, once started, must continue to completion. [0071] 4 Resource constraints must also be accounted for when allocating a task in time: [0072] a. Only active workcells can be assigned tasks. [0073] b. Tasks are assigned to time intervals when the workcell is idle. [0074] c. A workcell with the capability to process a task is available for that task if it has no task scheduled for the time interval equal to or larger than the task process time. [0075] d. If a task type requires workcell setup, the task is scheduled after the workcell setup procedure is completed. The workcell setup is independent of the work-in-process (WIP), but depends on parts and tools to arrive, if these are required by the setup or task. [0076] e. Depending on the task type, for similar tasks to be executed in sequence at the same workcell, the workcell might perform a reset procedure before starting the next task. [0077] 5 Follow the task precedence specified by the task sequence chosen for the product unit. [0078] a. A task with multiple precedents can only be allocated after all its immediate precedent tasks have been allocated. [0079] 6 Task resources availability: the task will be scheduled after all resources required by the task type are scheduled to arrive at the designated workcell. [0080] 7 IMR availability [0081] a. The earliest nearby IMRs with the required transportation capability are assigned to pick up a WIP. [0082] b. A task is assigned to an IMR after the IMR becomes available. [0083] c. After arriving at a workcell, an IMR can proceed to the workcell output port and wait for the WIP. [0084] d. An IMR can be scheduled to drop off a WIP at the workcell input port and depart to a designated area at the factory or be assigned to another task. [0085] e. An IMR can be assigned to pick up WIP at a workcell output port and depart to another workcell or a designated area at the factory. [0086] f. An IMR task is created each time an IMR is assigned to a product unit. [0087] 8 Transportation time: tasks will start no sooner than after the transportation unit is scheduled to arrive at its destination. [0088] 9 Factory floor: the paths of two or more IMRs cannot intersect at the same time.

[0089] An exemplary sequence of tasks is shown in FIG. 11. Execution of this task sequence results in production of two products, A and B, and the arrows illustrate the dependency between tasks. Product A represents a special case where, with the exception of the single first task, every task has only one dependent task. Product B illustrates the dependency of task 5 on multiple tasks, i.e., 3 and 4; in other words, tasks 3 and 4 are required to be performed before task 5.

[0090] A workcell sequence may be defined as described above, as an optimized layout. The layout will depend on workcell capability; FIG. 12A shows the task-execution capabilities of four workcells, WC1-WC4, and FIG. 12B illustrates a representative layout design (e.g., one that has been generated by layout optimization as described above, or a candidate layout design). The workcell layout and sequence shown in FIG. 12B can fulfill a work order of one unit of each product type.

[0091] The following algorithm may be used to produce a candidate (unoptimized) schedule for a workcell sequence WC_sequence:

TABLE-US-00004 1. Procedure Task_allocation(WC_sequence,     WC_schedule, Transportation_schedule) 2.  Create empty dictionary proposed\_schedules 3.  Randomly assign order of product units 4.  Create new WC_temp_schedule -->Start time is 0 5.  for all product_unit in WC_sequence 6.   while task in product_unit pending schedule 7.    for all task in product_unit 8.     Allocate task at WC_temp_schedule subject to:              Task sequence precedence. 9.    end for 10.   end while 11.  end for 12.  proposed_WC_sch is a copy of -->Start time is updated    WC_schedule 13.  proposed_IMR_sch is a copy of IMR_schedule 14.  for all product_unit in WC_sequence 15.   for all task in product_unit 16.    Find IMR with earliest availability at proposed_IMR_sch 17.    Find task time slot at proposed_WC_sch subject to:           IMR availability; and           Task sequence precedence. 18.    Create IMR task 19.    Update proposed_IMR_schedule 20.    Update proposed_WC_sch 21.   end for 22.  end for 23.  Add costs for proposed_WC_sch to proposed_schedules 24.  Add costs for proposed IMR_sch to proposed_schedules 25.  Add proposed_IMR_sch to proposed_schedules 26.  Add proposed_WC_sch to proposed_schedules 27.  return proposed_schedules 28. end procedure

[0092] Applying this algorithm to the sequence shown in FIG. 12B results in the schedule illustrated in FIG. 13.

[0093] A workcell schedule can be optimized according to the performance metrics sought. For instance, when possible, tasks are assigned to a workcell as early as possible as an attempt to compress the workcell schedule, resulting in the resources involved, such as IMR availability, being updated accordingly. Preventing IMRs from accumulating at a workcell entrance is another example of optimization with the goal of preventing traffic congestion; this is described in detail below. Another approach to schedule optimization is generating different schedules and optimizing to an objective function as described above. Parameters that may be varied in the optimization include:

[0094] 1. Product throughput

[0095] 2. Product type throughput

[0096] 3. workcell utilization

[0097] 4. IMR utilization

[0098] 5. IMR traveled distance

[0099] 6. Workcell downtime

[0100] 7. IMR downtime

[0101] 8. Product batch completion time

[0102] 9. Work order completion time

[0103] Once again, candidate solutions are generated by evolving previously known solutions until stopping conditions are met. The search may terminate if a solution that meets minimum requirements is found before a predefined timeout. In the event of a timeout, the candidates are ranked and the best solution is selected used as the workcell and transportation schedules.

[0104] Another approach is to optimize routing rather than optimizing the schedule per se; often the best routing protocol corresponds to the optimal schedule. Routing optimization plans and coordinates the motion of the IMR fleet to maximize the throughput of the factory; this process is sometimes referred to as the multi-robot motion planning problem. Both “coupled” and “decoupled” approaches to solve the multi-robot motion planning problem are known. Coupled methods extend single-robot path planning algorithms, which consider all potential collisions during the planning stage. However, the search space of this approach grows exponentially with the number of robots, which makes them unresponsive to the changes in the workspace and computationally unattractive. Decoupled methods address the computational load by breaking this challenging problem into two sub-problems: path planning and motion coordination. Path planning deals with finding a path for robots in the fleet, ignoring the potential collisions enroute. Motion coordination monitors the fleet and, if necessary, replans IMR motions to avoid collisions.

[0105] Decoupled methods can be classified as either centralized or decentralized. In decentralized approaches, each IMR plans its own path and communicates with its neighboring IMR to resolve collisions. Motion planning occurs at the IMR level using local information, which provides the states of the IMR within the communication range. A particular IMR might not receive information within the neighborhood because of the communication overhead, or the planned trajectory might lead to severe motion interferes with the IMRs that stay just outside the communication radius. Local information related to moving or stationary objects cannot guarantee collision-free or blockage-free motion for the fleet, or solution optimality. Centralized methods ensure the optimality and existence of a solution by gathering all information related to the fleet in a single processing unit. The single processing unit serves as a supervisory controller, which keeps track of the states of the IMRs, computes trajectories for the fleet, and prevents collisions.

[0106] Embodiments of the scheduling subsystem 155 utilize a centralized, decoupled approach to motion planning. In case the positional states of all moving or stationary objects, including but not limited to IMRs, workcells, human workers, and robots are available, this information is used to ensure the safety and unobstructed motion of the IMR fleet in the factory. The scheduling subsystem 155 may determine the IMR trajectories using the initial state of the IMRs and the factory layout. In these embodiments, the path planning part of the scheduling subsystem 155 employs a transportation network to find a route between any two locations of the factory. The motion coordination part of the scheduling subsystem 155 incorporates multiple steps of operations such as prediction, projection of future states, collision prediction, and optimization of IMR control commands to meet system performance levels.

[0107] The following nseudocode specifies a representative execution order:

TABLE-US-00005 1: procedure RUNTIME(I M R_data) 2:  Run IMR State Prediction (I M R_data) 3:  Run Collision Prediction (Predicted_I M R_states) 4:  Run Optimization (Predicted_I M R_states, Conflicting_I M R_pairs) 5:  return I M R_control_commands 6: end procedure

[0108] The scheduling subsystem 155 may maintain a topological representation of the factory as a digraph, which has a set of nodes (in the literature also called vertices) and edges. The nodes represent workcell input/output ports or any intermediate point on the factory floor that IMRs can visit, and edges represent directed paths that link nodes to each other. FIG. 14A illustrates representation of a factory floor as a grid 1400, and FIG. 14B indicates the locations of the nodes; the arrows are the directed edges of the transportation network. The scheduling subsystem 155 may utilize this representation for path planning (e.g., to find the best path for a given set of performance metrics), (ii) motion coordination using an occupancy map of the factory, and (iii) accommodating blockage of some specific areas of the factory (e.g., charging stations, parking, or temporary waiting areas). The below algorithm may be used to generate the topological factory representation.

TABLE-US-00006 1: procedure INIT(wc, factory_dimensions, wc_parameters, parking_lots) 2:  Create 2D grid 3:  Find Workcell Boundaries 4:  Remove Workcell Nodes and Edges 5:  Create Parking Zone 6:  return transportation_network 7: end procedure

[0109] A prediction component of the scheduling subsystem 155 uses position and orientation measurements and a motion model of the IMRs to estimate the current and near-future positions and orientation of IMRs. FIG. 15 illustrates the prediction of an IMR position on the given path or trajectory, where p(t) is the current position of the IMR and {tilde over (p)}(t) is the predicted position after a time step. In particular, the prediction component estimates the long-term future states of IMRs that originate from their current states by considering their path, motion models, and constraints—e.g., in accordance with the following algorithm:

TABLE-US-00007   1: procedure PREDICTION(I M R_data) 2:  for all I M R ϵ imr_list do 3:   Predict the states of the IMR 4:   Map IMR rigid body to the grid 5:  end for 6:  return Predicted_I M R_states, occupancy_grid 7: end procedure

[0110] A collision prediction component of the scheduling subsystem 155 may continually monitor potential collisions among two or more IMRs. Potential collisions are fed back to the path-planning component of the scheduling subsystem 155, which re-plans these IMRs' trajectories to prevent imminent collisions. In some embodiments, potential collisions are fed back to the layout subsystem 150, which may modify the layout to avoid collisions. (e.g. workcell orientation)

[0111] To achieve a safe fleet motion-coordination objective, position and orientation data may be combined with additional metrics such as IMR safety regions, change in the relative distance, and the relative distance between any two objects in the same neighborhood. The IMR safety region may be a rectangular area that extends out from the front bumper of an IMR and aligns with its motion direction. FIG. 16 illustrates an example configuration of two IMRs and their overlapping safety regions, i.e., Safety Zones 1 and 2. The width of the safety region may be equal to the width of the associated IMR, and the length of the safety region can be shorter or longer than the IMR length. A lengthy IMR safety region permits detection of potential collisions well in advance, enabling the path-planning component to take action earlier and prevent a collision with only minor changes in IMR motion commands and task arrival times. On the other hand, lengthy safety regions lead to more safety-region overlaps that can prompt adjustments more often than needed, significantly increasing the computational burden. The length of the safety region is a parameter that is desirably tuned such that the potential collision capture is maximized with a minimum computational effort.

[0112] The planar 2D motion of an IMR may be described by position vectors expressed with respect to the fixed reference frame, and the relative distance between any two IMRs may be expressed as

d=∥p.sub.1−p.sub.2∥

where ∥∘∥ returns the Euclidean norm of a vector. The relative distance calculation does not consider the geometry of the IMRs; therefore, it does not serve as a clearance, which refers to a free-space, between two IMRs. The change in the relative distance results in meaningful criteria for collision prediction, i.e., decreasing relative distance over time indicates that IMRs are moving towards each other. IMRs that locate in a similar vicinity can be identified when their relative distance is less than the IMR collision detection radius, a parameter that may be tuned so that only emerging collisions are timely captured.

[0113] The below pseudocode implements the collision-prediction component of the scheduling subsystem 155. After all three conditions are applied, the IMRs that meet all of them are specified as conflicting Milts, and sets of conflicting IMR pairs may be analyzed by an optimizer to determine whether they require any control actions.

TABLE-US-00008 1: procedure COLLISION PREDICTION(Predicted_I M R_states) 2:  for all I M R ϵ imr_list do 3:   Compute IMR Safety Zones 4:   Compute Relative Distances 5:   Compute Change in the Relative Distances 6:   end for 7:   Compute the IMRs within the same neighborhood 8:   Compute Overlapping Safety Zones 9:   Find IMRs that satisfy all Conditions 10:  return Conflicting_I M R_pairs 11: end procedure

[0114] The optimizer of the scheduling subsystem 155 gathers information from the prediction and collision prediction components, and alters route planning or updates the commands that the IMRs are already executing in accordance with an optimization algorithm (e.g., a combinatorial optimization algorithm) as described above. In some cases, the optimizer may produce a locally optimal solution, which resolves potential collisions but cannot satisfy the temporal constraint on the overall task. The scheduling subsystem 155 may attempt to revise this type of solution, which is not optimal but satisfies the relaxed constraints, to compensate for the delays or other impacts. The output of the optimizer may include or consist of motion commands for the IMR fleet, including but not limited to a path, trajectory, linear and angular velocities, or a new positional state causing the IMRs to wait temporarily. The below pseudocode implements the optimizer component of the scheduling subsystem 155.

TABLE-US-00009  1: procedure OPTIMIZATION(Predicted_I M R_states,   Conflicting_I M R_pairs)  2:   for all I M R_pair ϵ Conflicting_I M R_pairs do  3:   Project the states of the conflicting IMRs  4:   Check overlaps in the projected IMRs' states  5:   if projected_motion_conflicts > 0 then  6:    repeat  7:     Plan conflicting IMRs' motion commands  8:    until projected_motion_conflicts = 0  9:   end if  10:  end for  11:  return I M R_control_commands  12: end procedure

[0115] FIG. 17A illustrates a hypothetical scenario in which the collision prediction component of the scheduling subsystem 155 detects the potential collision of two IMRs (IMR 1, IMR 2) and the manner in which their initial paths cross. The optimizer finds the collision-free solution for this scenario as shown in FIG. 17B and updates the trajectory of IMR 2. In this solution, two additional nodes are included in the path of IMR 2 to prevent the potential collision. However, this path change will affect the IMR and workcell schedules, which are therefore revised by the scheduling subsystem 155 in the manner described above

[0116] It should be stressed that, although the previous discussion assumed that IMRs are identical, the scheduling subsystem 155 supports non-identical IMRs that have different capabilities, hardware, and kinematic and dynamic models as specified in their corresponding factory object attributes.

[0117] Certain embodiments of the present invention are described above. It is, however, expressly noted that the present invention is not limited to those embodiments; rather, additions and modifications to what is expressly described herein are also included within the scope of the invention.