Search

This paper develops a new method for synthesizing deadlock avoidance controllers (DACs) that realize job and machine dispatching policies of a flexible manufacturing system (FMS) into deadlock free control actions. Such controllers not only keep the FMS capable of repeating any of its operations, i.e., live, but also achieve a high resource utilization under any given dispatching policy. Our methodology is based on an untimed Petri net formalism. It consists of four ingredients: 1) a bottom up approach for synthesizing a controlled production Petri net (CPPN) model of a FMS, 2) a necessary and sufficient liveness condition based on decomposition of the CPPN into controlled production subnets and the concept of minimal resource requirements, 3) a sufficient procedure to test whether the liveness condition is kept after a control action is executed and 4) an algorithm that combines the test procedure with the given dispatching policy to generate valid and utilization maximizing control actions. We assess that this method is of polynomial time complexity and show that it results in a much larger class of controls than that of an existing deadlock avoidance scheme.

This paper presents an efficient, optimization model-based approach for scheduling the production of discrete-part, make-to-order type of flexible flow shops, where setup effects are negligible. A nominal scheduling algorithm based on Lagrangian relaxation and minimum cost linear network flow is first developed for scheduling under nominal conditions. Fast rescheduling algorithms that exploit the economic interpretation of the Lagrange multipliers and the network structure of production flows are then proposed for timely adjusting the nominal schedule to cope with disturbances. Numerical results on realistic examples demonstrate that our methodology is quite effective; it generates near-optimal schedules, provides relatively smooth adjustment (i.e., no drastic change from the nominal schedule) for small disturbances, and is computationally efficient.