Optimization-based opportunistic part dispatching in flexible manufacturing systems

A new strategy for dynamically scheduling parts in computer-controlled flexible manufacturing systems (FMS) has been developed. In an FMS, the flexibility of part routing offers different loading options to a part at each stage of its journey through the shop. In principle, greater routing flexibility means greater capability of the system to schedule parts opportunistically in real time. The full advantage of this capability can only be realized by incorporating optimality-seeking decision algorithms in control software. Due to the intractably combinatorial nature of the situation, the bigger problem is, in practice, decomposed into simpler independent subproblems by deliberately foregoing some flexibility. As can be seen in most FMS, routing of a part is done independently in a one-at-a-time manner, decomposing an n-job routing problem into a sequence of n independent one-job problems. An interesting point of view emerges from the recognition that routing flexibility is an advantage not only for the parts in terms of alternative routings, but also for the machines in terms of multiple options in choosing a part for processing. In most FMS, the machines do not choose parts globally. Instead, each machine keeps getting the parts routed to it, and is beset with its own local sequencing problem. Thus, a possible m-machine problem--in which all machines would interact among themselves to choose parts in an optimal way--is decomposed into m number of independent subproblems to be solved locally using priority dispatching rules. In order to use routing flexibility to the best advantage, job dispatching should be done in a globally optimal manner, from the points of view of parts as well as machines. In other words, on each occasion of decision making, the entire m-machine, n-job dispatching problem should be optimally solved all at once without decomposition. This gives rise to the new idea of multiple dispatching which implies making routing decisions for all parts simultaneously. The notion of multiple dispatching provides the necessary abstraction for global (though myopic) optimization of loading decisions using matching or assignment algorithms of polynomial-time complexity. This idea has been developed in this research along with the suggested optimization procedure. Performance-superiority of the new approach over conventional methods has been demonstrated in simulation experiments. An interesting dimension of the new approach is that it provides a framework for an optimization-based global bidding scheme in distributed control environment