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, 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

In building emergency evacuation, the perception of hazards can stress crowds, evoke their competitive behaviors, and trigger disorder and blocking as they pass through narrow passages (e.g., a small exit). This is a serious concern threatening evacuees' survivability and egress efficiency. How to optimize crowd guidance while considering such effects is an important problem. Based on advanced microscopic pedestrian models and simulations, this paper establishes a new macroscopic network-flow model where fire, smoke, and psychological factors can evoke a crowd's desire to escape—the desired flow rate. Disorder and blocking occur when the desired flow rate exceeds the passage capacity, resulting in a drastic decrease of crowd movement in a nonlinear and random fashion. To effectively guide cro wds, a divide-and-conquer approach is developed based on groups to reduce computational complexity and to reflect psychological findings. Egress routes for individual groups are optimized by using a novel combination of stochastic dynamic programming and the rollout scheme. These routes are then coordinated so that limited passage capacities are shared to meet the total need for joint movement. Numerical testing and simulation demonstrate that, compared with a strategy of merely using nearest exits, our solution can evacuate more people more rapidly by preventing or mitigating potential disorder and blocking at bottleneck passages.

This paper presents a Lagrangian relaxation-based approach for production scheduling of flexible flow shops (PSFFS) where sequence-dependent setup effects are significant. PSPFS is first formulated as a separable integer programming problem with synchronization constraints between production and machine usage. Lagrangian relaxation is then applied, and the scheduling is decomposed into part production and machine scheduling. In these subproblems, there are network flow structures in the equality constraints describing machine status change and production flow balance. Our iterative algorithm applies a minimum cost network flow algorithm to individual subproblems and adopts an efficient surrogate subgradient method to optimize Lagrangian multipliers. A machine availability-searching heuristic finally adjusts the solution to satisfy all synchronization constraints by exploiting the network structure, economic interpretation of Lagrangian multipliers, and the slack time policy. Numerical results of 16 cases, each having 20 test problems, demonstrate that differences between the schedules obtained by our approach and the true optima are on average within 15%, CPU times spent are all less than 17 min on a Pentium-II personal computer. Among the problem dimension factors, the number of part types has the most significant effect on both optimality and computation efficiency. Application of the methodology to daily scheduling of a realistic integrated circuit testing facility of 30 machines takes about 6 min of CPU time to generate a near-optimal solution

Deregulated electricity markets in the U.S. currently use an auction mechanism that minimizes total supply bid costs to select bids and their levels. Payments are then settled based on market-clearing prices. Under this setup, the consumer payments could be significantly higher than the minimized bid costs obtained from auctions. This gives rise to ldquopayment cost minimization,rdquo an alternative auction mechanism that minimizes consumer payments. We previously presented an augmented Lagrangian and surrogate optimization framework to solve payment cost minimization problems without considering transmission. This paper extends that approach to incorporate transmission capacity constraints. The consideration of transmission constraints complicates the problem by entailing power flow and introducing locational marginal prices (LMPs). DC power flow is used for simplicity and LMPs are defined by ldquoeconomic dispatchrdquo for the selected supply bids. To characterize LMPs that appear in the payment cost objective function, Karush-Kuhn-Tucker (KKT) conditions of economic dispatch are established and embedded as constraints. The reformulated problem is difficult in view of the complex role of LMPs and the violation of constraint qualifications caused by the complementarity constraints of KKT conditions. Our key idea is to extend the surrogate optimization framework and use a regularization technique. Specific methods to satisfy the ldquosurrogate optimization conditionrdquo in the presence of transmission capacity constraints are highlighted. Numerical testing results of small examples and the IEEE Reliability Test System with randomly generated supply bids demonstrate the quality, effectiveness, and scalability of the method.

Group elevator scheduling has long been recognized as an important problem for building transportation efficiency, since unsatisfactory elevator service is one of the major complaints of building tenants. It now has a new significance driven by homeland security concerns. The problem, however, is difficult because of complicated elevator dynamics, uncertain traffic in various patterns, and the combinatorial nature of discrete optimization. With the advent of technologies, one important trend is to use advance information collected from devices such as destination entry, radio frequency identification, and sensor networks to reduce uncertainties and improve efficiency. How to effectively utilize such information remains an open and challenging issue. This paper presents the optimized scheduling of a group of elevators with destination entry and future traffic information for normal operations and coordinated emergency evacuation. Key problem characteristics are abstracted to establish a two-level separable formulation. A decomposition and coordination approach is then developed, where subproblems are solved by ordinal optimization-based local search, and top ranked nodes are selectively optimized by using dynamic programming. The approach is then extended to handle up-peak with little or no future traffic information, elevator parking for low intensity traffic, and coordinated emergency evacuation. Numerical testing results demonstrate near-optimal solution quality, computational efficiency, the value of future traffic information, and the potential of using elevators for emergency evacuation.