Evacuation behavior is an important human factor in safety performance engineering, and pre-evacuation phase is an interval between receiving an alarm signal and decisive escaping for safety. To better understand and evaluate human awareness and response during pre-evacuation phase, this paper formulates a multi-agent model to simulate crowd pre-evacuation behavior. The model mainly combines the DeGroot dynamics with binary phase transition to describe how group pre-evacuation time emerges from individual interaction. The model parameters are quantitatively meaningful to human factors research within socio-psychological background, and the modeling framework also describes collective motion of many evacuee agents in a planar space. The resulting multi-agent system is partly similar to the Vicsek flocking model, and it is meaningful to explore complex behavior during phase transition of a non-equilibrium process.

Job-shop scheduling is an important but difficult combinatorial optimization problem for low-volume and high-variety manufacturing, with solutions required to be obtained quickly at the beginning of each shift. In view of the increasing demand for customized products, problem sizes are growing. A promising direction is to take advantage of Machine Learning (ML). Direct learning to predict solutions for job-shop scheduling, however, suffers from major difficulties when problem scales are large. In this paper, a Deep Neural Network (DNN) is synergistically integrated within the decomposition and coordination framework of Surrogate Lagrangian Relaxation (SLR) to predict good-enough solutions for subproblems. Since a subproblem is associated with a single part, learning difficulties caused by large scales are overcome. Nevertheless, the learning still presents challenges. Because of the high-variety nature of parts, the DNN is desired to be able to generalize to solve all possible parts. To this end, our idea is to establish “surrogate” part subproblems that are easier to learn, develop a DNN based on Pointer Network to learn to predict their solutions, and calculate the solutions of the original part subproblems based on the predictions. Moreover, a masking mechanism is developed such that all the predictions are feasible. Numerical results demonstrate that good-enough subproblem solutions are predicted in many iterations, and high-quality solutions of the overall problem are obtained in a computationally efficient manner. The performance of the method is further improved through continuous learning.Note to Practitioners—Scheduling is important for the planning and operation of job shops, and high-quality schedules need to be obtained quickly at the beginning of each shift. To take advantage of ML, in this paper, a DNN is integrated within our recent decomposition and coordination approach to learn to predict “good-enough” solutions to part subproblems. To be able to predict solutions for parts of various characteristics“, surrogate” part subproblems that are easier to learn are established, and a generic “pointer network” is developed to learn to predict their solutions. To satisfy the constraints of the surrogate part subproblems, the pointer network is enhanced with a novel “masking mechanism” such that all the predictions are feasible. The solutions to the original part subproblems are calculated based on the predictions. Testing results demonstrate that subproblem solutions are efficiently obtained based on predictions, and the high-quality solutions of the overall problem are thus efficiently obtained. Through continuous learning, the performance of the method is further improved. Python codes and datasets are submitted together with the paper.

This IEEE Transactions on Automation Science and Engineering (T-ASE) Special Section on New Frontiers in Smart Factories: Smart Automation and Human–Robot Interaction focuses on promising, innovative research outcomes and industrial applications of different key technologies for smart automation and human–robot interaction.

Job shops are an important production environment for low-volume high-variety manufacturing. Its scheduling has recently been formulated as an integer linear programming (ILP) problem to take advantages of popular mixed-integer linear programming (MILP) methods, e.g., branch-and-cut. When considering a large number of parts, MILP methods may experience difficulties. To address this, a critical but much overlooked issue is formulation tightening. The idea is that if problem constraints can be transformed to directly delineate the problem convex hull in the data preprocessing stage, then a solution can be obtained by using linear programming (LP) methods without combinatorial difficulties. The tightening process, however, is fundamentally challenging because of the existence of integer variables. In this article, an innovative and systematic approach is established for the first time to tighten the formulations of individual parts, each with multiple operations, in the data preprocessing stage. It is a major advancement of our previous work on problems with binary and continuous variables to integer variables. The idea is to first link integer variables to binary variables by innovatively combining constraints so that the integer variables are uniquely determined by the binary variables. With binary and continuous variables only, it is proved that the vertices of the convex hull can be obtained based on vertices of the LP problem after relaxing binary requirements. These vertices are then converted to tightened constraints for general use. This approach significantly improves our previous results on tightening individual operations. Numerical results demonstrate significant benefits on solution quality and computational efficiency. This approach also applies to other complex ILP and MILP problems with similar characteristics and fundamentally changes the way how such problems are formulated and solved.Note to Practitioners—Scheduling is an important but difficult problem in planning and operation of job shops. The problem has been recently formulated in an integer linear programming (ILP) form to take advantage of popular mixed-integer linear programming methods. Given an ILP problem, there must exist a linear programming (LP) formulation so that all of its vertices are also the vertices to the ILP problem. If such an LP problem can be found in the data preprocessing stage, then the corresponding ILP problem is tight and can be solved by using an LP method without difficulties. In this article, an innovative and systematic approach is established to tighten the formulations of individual parts, each with one or multiple operations. It is a major advancement of our previous work on problems with binary and continuous variables by novel exploitation of the relationship between integer and binary variables in job-shop scheduling. The resulting tightened constraints are characterized by part parameters and the length of the scheduling horizon and can be easily adjusted for other data sets. Results demonstrate significant benefits on solution quality and computational efficiency. This approach also applies to other complex ILP and MILP problems with similar characteristics and fundamentally changes the way how such problems are formulated and solved.

With the emergence of the Internet of Things that allows communications and local computations and with the vision of Industry 4.0, a foreseeable transition is from centralized system planning and operation toward decentralization with interacting components and subsystems, e.g., self-optimizing factories. In this article, a new “price-based” decomposition and coordination methodology is developed to efficiently coordinate a system consisting of distributed subsystems such as machines and parts, which are described by mixed-integer linear programming (MILP) formulations, in an asynchronous way. The novel method is a dual approach, whereby the coordination is performed by updating Lagrangian multipliers based on economic principles of “supply and demand.” To ensure low communication requirements within the method, exchanges between the “coordinator” and subsystems are limited to “prices” (Lagrangian multipliers) broadcast by the coordinator and to subsystem solutions sent at the coordinator. Asynchronous coordination, however, may lead to convergence difficulties since the order in which subsystem solutions arrive at the coordinator is not predefined as a result of uncertainties in communication and solving times. Under realistic assumptions of finite communication and solve times, the convergence of our method is proven by innovatively extending the Lyapunov stability theory. Numerical testing of generalized assignment problems through simulation demonstrates that the method converges fast and provides near-optimal results, paving the way for self-optimizing factories in the future. Accompanying CPLEX codes and data are included.Note to Practitioners—In view of a foreseeable transition toward self-optimizing factories whereby machines and parts have communication and computational capabilities, a novel “price-based” distributed and asynchronous method to coordinate a system consisting of distributed subsystems is developed. Under realistic assumptions of finite communication and solve times, method convergence is proven. Numerical testing of generalized assignment problems through simulation demonstrates that the method converges fast and provides near-optimal results, paving the way for self-optimizing factories in the future. Accompanying CPLEX codes and data are included.

Fault prognosis of the air-handling systems, which are the key subsystems of heating, ventilation, and air conditioning systems, allows system operators to know the remaining useful life (RUL), thus preventing unexpected breakdowns and reducing the operational and maintenance costs. In this article, a new hidden semi-Markov model-based method is developed. In the method, only relevant state-transition points are selected and estimated, leading to computational efficiency. Physics-based models are used in a novel way to provide “mapping matrices” relating component capacities to fault severities, capturing impacts of multiple failure modes. Experimental results show that our method can effectively estimate the RUL of the components and the systems.

Many operation optimization problems such as scheduling and assignment of interest to the automation community are mixed-integer linear programming (MILP) problems. Because of their combinatorial nature, the effort required to obtain optimal solutions increases drastically as the problem size increases. Such operation optimization problems typically need to be solved several times a day and require short solving times (e.g., 5, 10, or 20 min). The goal is, therefore, to obtain near-optimal solutions with quantifiable quality in a computationally efficient manner. Existing MILP methods, however, suffer from slow convergence and may not efficiently achieve this goal. In this paper, motivated by fast convergence of augmented Lagrangian relaxation (LR), a novel advanced price-based decomposition and coordination “surrogate absolute-value LR” (SAVLR) approach is developed. Within the method, convergence of our recent surrogate LR (SLR), which has overcome all major difficulties of traditional LR, is significantly improved by penalizing constraint violations by adding “absolute-value” penalties. Moreover, such penalties are efficiently linearized in a standard way, thereby enabling the use of MILP solvers. By exploiting the beautiful property of exponential reduction of complexity of subproblems upon decomposition, subproblems are efficiently solved and their solutions are efficiently coordinated by updating Lagrangian multipliers. Convergence is then proved under novel adjustment of penalty coefficients. A series of generalized assignment problems is considered, and for these problems, superior performance of SAVLR over other state-of-the-art and state-of-the-practice methods is demonstrated. Accompanying CPLEX codes, whereby SAVLR is implemented, are also included.Note to Practitioners—Examples of important problems that arise in automation community include scheduling and assignment problems. Because of their combinatorial nature, the effort required to obtain optimal solutions increases drastically as the problem size increases. Existing mixed-integer linear programming (MILP) methods, however, may suffer from slow convergence and may not efficiently achieve this goal. The new method revolutionizes the way such problems can be solved with major improvements on the overall performance. It is based on our recent breakthrough “surrogate Lagrangian relaxation” (LR), which has overcome all major difficulties of traditional LR while exploiting the beautiful property of exponential reduction of complexity upon decomposition. To significantly improve convergence while maintaining linearity so as to use MILP solvers, our idea is to penalize violations of relaxed constraints by the infrequently used “absolute-value” penalty functions. Although not differentiable, absolute-value penalties have the advantage of being exactly linearizable through extra variables and constraints. The difficulties caused by those extra constraints, which couple subproblems, are resolved by adaptive adjustment of penalty coefficients. A series of generalized assignment problems is considered and superior performance of the new method against state-of-the-art and state-of-the-practice methods is demonstrated. Accompanying CPLEX codes whereby the new method is implemented are also included.

Online knowledge sharing networks (KSNets) have made significant impacts on the economy as well as wellbeing of societies through sharing. One of the most successful KSNets is Wikipedia that allows users to create contents in a collaborative manner and to provide fast and easy access at no cost to users. Recent research, however, has shown that the numbers of “Wikipedians” and new page creations have been declining, reflecting decrease in user contributions and in new contents. To facilitate management for sustainability, this paper aims at quantitatively modeling how the decline in new contents affects the number of Wikipedians and in turn content creations, and predicting decline start time and speed based on available Wikipedia data. The novel modeling approach adopts auto-regression with an extended Bass Diffusion model (AREBDM) embedded to describe the Wikipedia-wide evolutions of the number of Wikipedians and content developments. Model parameters are then extracted by a nonlinear least square method from early Wikipedia data. Simulation predictions match well with actual Wikipedia decline trajectories of later stages. Our analysis shows that the decline of new page creation leads in time the decline of the number of new Wikipedians, and the decline speed increases with the decrease of new contents. Our approach therefore has the potential to predict decline time and speed so that proactive actions can be taken as early as possible.

Fault management is critical for efficiently supporting the increasing microgrids' penetration in distribution networks but remains an open problem. No existing ride through methods can ride through symmetrical and asymmetrical faults without increasing the fault current magnitude, meanwhile balancing microgrid power and eliminating double frequency ripples in microgrid inverters. The paper bridges this gap by contributing a novel active fault management (AFM) method. The new contributions include: 1) the development of a new conceptual AFM to control multiple variables during voltage dips; 2) the optimization-based AFM to coordinate different objectives according to a guidance and 3) a combined optimization and feedback control, during which optimization method provides the optimal trade-offs among different objectives and the feedback control ensures accurate realization of chosen operation points. Simulations with different types of faults prove that the developed AFM can achieve better trade-offs and coordination among various control objectives in comparison to the conventional ride through method.

A chiller plant consists of chiller, cooling tower, and pump subsystems. Two major configurations, primary-only and primary-secondary systems, are often used. Given the high energy costs of a plant, chiller plant operation optimization is important to save energy. For both configurations, chilled/condenser water supply temperatures are critical in improving chiller efficiency and should be considered as decision variables. However, nonlinearity of the problem is increased since chiller power consumption is a highly nonlinear function of these temperatures. Additionally, the problem is combinatorial considering the number of active units (e.g., chillers). In this paper, primary-only systems with identical units in each subsystem and primary-secondary systems with units of two sizes are studied, and both supply temperatures are optimized for energy savings. To obtain near-optimal solutions efficiently, a recent decomposition and coordination approach with little multiplier zigzagging and fast reduction of coupling constraint violations combining with sequential quadratic programming (SQP) is used. Penalties for the constraints that are difficult to be satisfied (e.g., mass balance constraints between fixed-speed pumps and variable-speed chillers) are added. After decomposition, complexity and nonlinearity of a subproblem are reduced drastically as compared with the original problem so that SQP is used. Numerical testing demonstrates that our approach is efficient in obtaining near-optimal solutions, and major energy savings are achieved as compared with benchmark strategies. The approach is scalable and can be used for chiller plant optimization and beyond.

It is unclear what triggers the behavior of active shooters, but their consequences are severe. There is opportunity to implement an automated response system capable of delivery guidance to evacuees' to aide people to safety. Optimizing guidance delivery is challenging because active shooter incidents evolve quickly and are unpredictable. In this paper, we develop a new problem formulation specific for active shooter events by utilizing the structure of each room. To effectively solve this problem, a divide-and-conquer approach is deployed to split evacuees into groups. The egress routes are decomposed and coordinated for each group are optimized using stochastic dynamic programming. Numerical testing and simulation show our solution with a safe room the solution fast relevant to shooting events and effectively.

In a heating, ventilation, and air conditioning system, an air-handling system is a key module. Its components (e.g., air handling unit, air-mixing box, and fans), linked through airflows, condition air to a desired temperature and/or humidity based on comfort or controlled environment requirements. Identifying failure modes and estimating their severities allow maintenance crews to know which faults have occurred, how critical they are, and be guided in the repair process to improve the system availability. The problem of fault detection and diagnosis in air-handling systems is complex because of fault propagation across components, and high false alarm rates caused by uncertainties in system and measurement dynamics. In this paper, to capture fault propagation impacts in an efficient manner, dynamic hidden Markov models are developed to identify failure modes, since they contain state transition matrices depending on other components and do not generate joint states. To filter out false alarms, “coupled statistical process control” techniques are developed by using state transitions matrices representing coupling among components. Experimental results show that the method can effectively diagnose faults with high-diagnosis accuracy. Note to Practitioners-Faults in heating, ventilation, and air conditioning air handling units (AHU) may cause high energy consumption and discomfort to occupants. Fault diagnosis in AHU is challenging since: 1) effects of faults propagate across components connected by airflows and 2) measurement noises may cause high false alarm rates. In this paper, a novel fault diagnosis method is established to identify failure modes and fault severities. This method explicitly considers the fault coupling among components. To reduce false alarm rates, new statistical process control techniques are developed to filter out false alarms. Experimental results show that our method can effectively diagnose faults with high diagnosis accuracy.

To reduce energy costs and emissions of microgrids, daily operation is critical. The problem is to commit and dispatch distributed devices with renewable generation to minimize the total energy and emission cost while meeting the forecasted energy demand. The problem is challenging because of the intermittent nature of renewables. In this paper, photovoltaic (PV) uncertainties are modeled by a Markovian process. For effective coordination, other devices are modeled as Markov processes with states depending on PV states. The entire problem is Markovian. This combinatorial problem is solved using branch-and-cut. Beyond energy and emission costs, to consider capital and maintenance costs in the long run, microgrid design is also essential. The problem is to decide device sizes with given types to minimize the lifetime cost while meeting energy demand. Its complexity increases exponentially with the problem size. To evaluate the lifetime cost including the reliability cost and the classic components such as capital and fuel costs, a linear model is established. By selecting a limited number of possible combinations of device sizes, exhaustive search is used to find the optimized design. The results show that the operation method is efficient in saving cost and scalable, and microgrids have lower lifetime costs than conventional energy systems. Implications for regulators and distribution utilities are also discussed.

The steelmaking-continuous-casting (SCC) process, which includes steelmaking, refining and continuous casting, is one of the major bottlenecks of iron and steel production. Efficient and effective scheduling of this process is essential to improve the productivity and reduce the production costs of the entire production system. We present a time-index formulation for this scheduling problem and a Lagrangian relaxation (LR) approach based on the relaxation of the machine capacity constraints. The relaxed problem is solved using an efficient polynomial dynamic programming algorithm. The corresponding Lagrangian dual (LD) problem is solved using a deflected conditional subgradient level method. Unlike the conventional subgradient algorithms for the LD problem, our method guarantees convergence using the Brannlund's level control strategy to replace the strict convergence condition that the optimum of the dual problem is known a priori. Furthermore, our method enhances the efficiency by introducing a deflected conditional subgradient to weaken the zigzagging phenomena that slows the convergence of conventional subgradient algorithms. The computational results demonstrate that the approaches can quickly obtain high-quality solutions and are notably promising for the SCC scheduling. Note to Practitioners-Efficient and effective SCC schedule is vital for the manufacturing system of iron and steel production. Unfortunately, the scheduling is extremely difficult because of its combinatorial nature and practical complex constraints such as job grouping constraints, precedence constraints, different transport time, and setup times. To obtain high-quality solutions within an acceptable computational time, we can use a problem-oriented approach, which can be the LR. However, there are two deficiencies in this approach: its empirical termination criteria, such as maximal iteration number or running time, which make it difficult to find a golden rule for various problems, and the inefficiency, which is caused by the so-called zigzagging phenomena. To overcome these deficiencies, this paper develops an effective subgradient method for SCC scheduling based on the machine capacity relaxation. This method gives an objective termination criterion based on the convergence condition of the method, and improves the efficiency based on a new search direction or a new subgradient. Then, the work shows how this method can be applied to solve an SCC scheduling problem. The computational results confirm their effectiveness and efficiency. The approaches can also be applied to other similar production scheduling problems.

Optimizing HVAC operation becomes increasingly important because of the rising energy cost and comfort requirements. In this paper, an innovative event-based approach is developed within the Lagrangian relaxation framework to minimize an HVAC's day-ahead energy cost. To solve the HVAC optimization problem based on events is challenging since with time-dependent uncertainties in weather, cooling load, etc., the optimal policy is not stationary. The nonstationary policy space is extremely large, and it is time consuming to find the optimal policy. To overcome the challenge, we develop an event-based approach to make the nonstationary optimal policy stationary in the planning horizon. The key idea is to augment state variables to include the time-dependent variables that make the optimal policy nonstationary and then define events based on the extended state variables. In addition, we develop within the Lagrangian relaxation framework a Q-learning method where Q-factors are used to evaluate event-action pairs and to obtain the optimal policy. Numerical results demonstrate that, as compared with time-based approaches, the event-based approach maintains similar levels of energy costs and human comfort, but reduces computational efforts significantly and has a much faster response to events.

Considering that energy use in buildings represents more than 40% of global energy consumption and that humans spend 90% of the time indoors, technologies enabling smarter buildings can lead to significant reductions in greenhouse gas emissions, and produce a comfortable, efficient and sustainable environment. This is to be achieved through smart sensing, advanced automation, and intelligent computing/communication technologies to efficiently operate, monitor, and maintain buildings. In this talk, two topics will be highlighted, including 1) Integrated Building Energy Management, 2) HVAC (Heating, Ventilation, and Air Condition) Fault Detection. For each topic, problem importance, challenges and some of our results obtained thus far will be highlighted. The goal is to demonstrate that Smart Buildings are a fertile problem context for meaningful research and development. The talk will end with a brief introduction of the Technical Committee on Smart Buildings of the IEEE Robotics and Automation Society (RAS).

Buildings worldwide account for nearly 40% of global energy consumption. The biggest energy consumer in buildings is the Heating, Ventilation and Air Conditioning (HVAC) systems. HVAC also ranks top in terms of number of complaints by tenants. Maintaining HVAC systems in good conditions through early fault detection is thus a critical problem. The problem, however, is difficult since HVAC systems are large in scale, consisting of many coupling subsystems, building and equipment dependent, and working under time-varying conditions. In this paper, a model-based and data-driven method is presented for robust system-level fault detection with potential for large-scale implementation. It is a synergistic integration of: ) Statistical Process Control (SPC) for measuring and analyzing variations; 2) Kalman filtering based on gray-box models to provide predictions and to determine SPC control limits; and (3) system analysis for analyzing propagation of faults' effects across subsystems. In the method, two new SPC rules are developed for detecting sudden and gradual faults. The method has been tested against a simulation model of the HVAC system for a 420-meter-high building. It detects both sudden faults and gradual degradation, and both device and sensor faults. Furthermore, the method is simple and generic, and has potential replicability and scalability.

Exploitation of short-interval spectrum availability offers an opportunity to better utilize spectrum for wireless communications. One significant class of short-interval secondary spectrum (SiSS) markets involves a primary license holder (PLH) renting out homogeneous spectrum units to a few competing Mobile Virtual Network Operators (MVNOs). This paper presents a design of SiSS market framework with brokerage services that mitigate information asymmetry and host auctions. The novel SiSS auction design is single-round and Vickrey-Clarke-Groves (VCG) auction-based and integrates two innovations. The first is a highly expressive bidding format that allows maximum bidding options to MVNOs in single submission. The second is a virtual bidder by the broker, whose bids are based on PLH's specification of per-unit reserve price, to avoid MVNOs' consideration of undesirable bidding strategies and guarantee that per-unit payment be no less than the reserve price. Such a design exploits the truthfulness of VCG and further achieves individual rationality and budget balance. Numerical experimentation shows that SiSS auction generates in average 31.3% higher per-unit revenue than VCG. For a SiSS market of 200 MVNOs and 500 spectrum units, computation time of clearing auction is within 15 seconds. These designs suit for SiSS applications in time efficiency and economic considerations.

Buildings account for nearly 40% of global energy consumption. About 40% and 15% of that are consumed, respectively, by HVAC and lighting. These energy uses can be reduced by integrated control of active and passive sources of heating, cooling, lighting, shading and ventilation. However, rigorous studies of such control strategies are lacking since computationally tractable models are not available. In this paper, a novel formulation capturing key interactions of the above building functions is established to minimize the total daily energy cost. To obtain effective integrated strategies in a timely manner, a methodology that combines stochastic dynamic programming (DP) and the rollout technique is developed within the price-based coordination framework. For easy implementation, DP-derived heuristic rules are developed to coordinate shading blinds and natural ventilation, with simplified optimization strategies for HVAC and lighting systems. Numerical simulation results show that these strategies are scalable, and can effectively reduce energy costs and improve human comfort.

The increasing pressure to meet demand are forcing semiconductor manufacturers to seek efficient scheduling methods. Lithography, with a limited number of expensive resources and the reentrant nature of the fabrication processes, is a major bottleneck. This paper presents a litho machine scheduling formulation for high-volume and low-variety manufacturing over a day, with novel modeling of resource setups, reticle expirations, and future stacking layer load balancing. The problem is believed to be NP hard. After linearization and simplification, it is solved by using the branch-and-cut method by exploiting problem linearity. Near-optimal solutions for practical problems, however, are still difficult to obtain efficiently. Through detailed analyses, it was discovered that the convex hull of the problem is difficult to delineate and many low-efficient branching operations are needed. A two-phase approach is therefore established. In the first phase, a simplified problem with certain complicating constraints dropped is efficiently solved by exploiting linearity to reduce ranges of decision variables. The problem with the full set of constraints is then solved in the second phase with a much reduced decision space. Numerical testing shows that this two-phase approach can generate near-optimal schedules within reasonable amounts of computation time. This two-phase approach is generic, and will have major implications on other semiconductor scheduling problems and beyond.

The interaction between a smart target and a smart MIMO radar is investigated from a game theory perspective. Since the target and the radar form an adversarial system, their interaction is modeled as a two-person zero-sum game. The mutual information criterion is used to formulate the utility functions. The unilateral, hierarchical, and symmetric games are studied, and the equilibria solutions are derived.

It is widely accepted that new production scheduling tools are playing a key role in flexible manufacturing systems to improve their performance by avoiding idleness machines while minimizing set-up times penalties, reducing penalties for do not delivering orders on time, etc. Since manufacturing scheduling problems are NP-hard, there is a need of improving scheduling methodologies to get good solutions within low CPU time. Lagrangian Relaxation (LR) is known for handling large-scale separable problems, however, the convergence to the optimal solution can be slow. LR needs customized parametrization, depending on the scheduling problem, usually made by an expert user. It would be interesting the use of LR without being and expertise, i.e., without difficult parameters tuning. This paper presents innovative approaches on the LR method to be able to develop a tool capable of solve scheduling problems applying the LR method without requiring a deep expertise on it. First approach is the improvement of an already existing method which use Constraint Programming (CP) to obtain better primal cost convergence. Second approach is called Extended Subgradient Information (ESGI) and it speed up the dual cost convergence. Finally, a set of step size rules for the Subgradient (SG) method are compared to choose the most appropriate rule depending on the scheduling problem. Test results demonstrate that the application of CP and ESGI approaches, together with LR and the selected step size rule depending on the problem, generates better solutions than the LR method by itself.

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

Group elevator scheduling has received considerable attention due to its importance to transportation efficiency for mid-rise and high-rise buildings. One important trend to improve elevator systems is to collect advance traffic information. Nevertheless, it remains a challenge to develop new scheduling methods which can effectively utilize such information. This paper is to solve the group elevator scheduling problem with advance traffic information. This problem is difficult due to various traffic patterns, complicated car dynamics, and combinatorial explosion of the search space. A two-level formulation is developed with passenger-to-car assignment at the high-level and single car dispatching that is innovatively formulated as passenger-to-trip assignment at the low-level. Detailed car dynamics are embedded in simulation models for performance evaluation. Taking advantage of advance information, a new door action control method is suggested to increase the flexibility of elevators. In view of the hierarchical problem structure, a two-level optimization framework is established. Key problem characteristics are exploited to develop an effective trip-based heuristic for single car dispatching, and a hybrid nested partitions and genetic algorithm method for passenger-to-car assignment which can be extended to solve a generic class of sequential decision problems. Numerical results demonstrate solution quality, computational efficiency, benefit of advance information and the new door action control method, and values of new features in our hybrid 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.

Concurrent engineering has been widely used in managing design projects to speed up the design process by concurrently performing multiple tasks. Since the progress of a design task often depends on the knowledge about other tasks and requires effective communication, tasks and communication activities need to be properly coordinated to avoid delays caused by waiting for information or the need for rework. This paper presents a novel formulation for design project scheduling with explicit modeling of task dependencies and the associated communication activities. General dependencies are modeled as combinations of three basic types representing sequential, concurrent, and independent processes. Communication activities are also modeled as tasks, and their interactions with design tasks are described by sets of intertask constraints. The objective is to achieve timely project completion with limited resources. To improve algorithm convergence and schedule quality, penalties on the violation of constraints coupling design tasks are added to the objective function. A solution methodology that combines Lagrangian relaxation, dynamic programming, and heuristic is developed to schedule design and communication tasks, and a surrogate optimization framework is used to overcome the ldquoinseperabilityrdquo caused by nonadditive penalties. A heuristic procedure is then developed to obtain scheduling policies from optimization results and to dynamically construct schedules. Numerical results show that the approach is effective to handle various task dependencies and the associated communication activities to provide high-quality schedules.

Maintaining an asset with life-limited parts, e.g., a jet engine or an electric generator, may be costly. Certain costs, e.g., setup cost, can be shared if some parts of the asset are replaced jointly. Reducing the maintenance cost by good joint replacement policies is difficult in view of complicate asset dynamics, large problem sizes and the irregular optimal policy structures. This paper addresses these difficulties by using a rollout optimization framework. Based on a novel application of time-aggregated Markov decision processes, the ldquoOne-Stage Analysisrdquo method is first developed. The policies obtained from the method are investigated and their effectiveness is demonstrated by examples. This method and the existing threshold method are then improved by the ldquorollout algorithmrdquo for the total cost case and the average cost case. Based on ordinal optimization, it is shown that excessive simulations are not necessary for the rollout algorithm. Numerical testing demonstrates that the policies obtained by the rollout algorithms with either the ldquoOne-Stage Analysisrdquo or the threshold method significantly outperform traditional threshold policies.

Many maintenance networks as well as supply networks and virtual enterprises consist of multiple organizations. A common problem arising in these different domains is multiorganization scheduling and coordination. The traditional centralized methods are not appropriate because of the existence of private information and decision-making authorities at different organizations. Although many distributed mechanisms have been presented for supply networks and virtual enterprises, they may not be effective for maintenance networks because of the difficulties of scheduling the tightly related maintenance operations and handling the massive uncertainties involved. These difficulties as well as the heterogeneity of the distributed environment make it challenging to develop an efficient framework for maintenance networks that can obtain a high-quality solution under different conditions, schedule in a timely manner, solve large-scale problems, and so on. In this paper, a price-based multiagent scheduling and coordination framework for maintenance networks is explored, and a systematic experimental study is carried out to evaluate the effects of different factors on its performance. The results show that the framework is able to overcome these difficulties and could be a step toward the next generation of e-scheduling for maintenance networks

Market competition forces manufactures to schedule their resources efficiently for on-time order delivery and low inventory. However, for companies such as textile and steel-making companies, optimizing schedules is difficult because of the NP-hard nature of the problem and the complex product structures: assemblies, disassemblies and couplings across orders. To address the difficulties, this paper extends the Lagrangian relaxation approach through selectively relaxing precedence constraints. The solution oscillation is identified and alleviated by adding auxiliary penalty and by nonlinear approximation. Furthermore, the normalized surrogate subgradient method is developed to accelerate the convergence of Lagrangian multipliers to obtain good solutions in computational efficient manner. Testing results demonstrate that better schedules are obtained when solution oscillation is alleviated. The newly developed normalized method significantly improves traditional methods

Group elevator scheduling is important for transportation efficiency in mid-rise and high-rise buildings, and incessant efforts have been made to improve the service efficiency of elevators. Although these efforts have achieved performance improvements, the performance limit remains an open issue. This paper tries to address that goal by estimating the optimal performance of group elevator scheduling with complete knowledge of future traffic information. A two-level minimization formulation is presented, with passenger-to-car at the high level, and single car dispatching at the low level. The low level is formulated as a passenger-to-trip assignment problem by using a concept trip to facilitate the description of single car dispatching strategies. In view of the difficulty to obtain the absolute optimal performance, our goal turns into its upper and lower bounds. The upper bound is obtained by finding a good feasible solution to this problem. The lower bound is obtained by finding the lower bound for a newly constructed problem whose optimal performance is less than or equal to that of the original problem. Numerical results demonstrate the effectiveness and the scalability of our method

In a building, effective operations of transportation systems including elevators, escalators, and stairs are vital. Among them, group elevator scheduling has long been recognized as an important issue for transportation efficiency. The problem, however, is difficult because of the large state space, various traffic profiles, and uncertainties. With the progress in information technology and sensor networks, one potential way is to use advanced traffic information to reduce uncertainties and optimize the performance. How to effectively utilize such information remains an open and challenging issue. This paper presents the optimized scheduling of a group of elevators with advanced traffic information for normal operations and coordinated emergency evacuation. A look-ahead time window is first introduced to model advanced information. Key characteristics of group elevator scheduling are abstracted to establish an innovative formulation. The objective function is transformed into an additive form to facilitate the decomposition of the problem into individual car subproblems. Subproblems are independently solved by using a local search method in conjunction with dynamic programming with a novel definition of stages, states, decisions, and costs to optimize single car dispatching. With surrogate optimization, local search is “good enough” to set multiplier updating directions. Individual cars are then coordinated through the updating of multipliers by using surrogate optimization for near-optimal solutions. Numerical testing results demonstrate that near-optimal solutions are obtained for problems of moderate sizes under selected traffic patterns. The results also show the value of advanced information through testing different window sizes and rescheduling intervals.

Overhaul and repair services are important segments of the remanufacturing industry, and are characterized by complicated disassembly, repair and assembly process plans, stochastic operations, and the usage of rotable inventory. In view of today's time-based competition, effectively scheduling such services and managing rotable inventory and uncertainties are becoming imperative to achieve on-time deliveries and low overall costs. In this paper, a novel formulation for overhaul and repair services is presented where key characteristics, such as uncertain asset arrivals and operation processing times, and rotable parts are abstracted to model an overhaul center and multiple repair shops in a distributed framework to reflect organizational structures. Interactions between the overhaul center and repair shops are described by sets of coupling constraints across the organizations. Rotable inventory dynamics is formulated in terms of repair operation completion times and asset assembly beginning times to facilitate minimization of inventory holding costs through scheduling. A solution methodology combining Lagrangian relaxation, stochastic dynamic programming, and heuristics is developed to schedule operations in a coordinated manner to minimize total tardiness, earliness, and inventory holding costs. Additionally, penalty terms associated with coupling constraint violations are introduced to the objective function to improve algorithm convergence and schedule quality, and a surrogate optimization framework is used to overcome the inseparability difficulty caused by the penalty terms. Numerical testing results show that the new approach is computationally effective to handle rotable inventory and uncertainties, and provides high quality schedules with low overall costs for stochastic remanufacturing systems. Note to Practitioners-Overhaul and repair services for jet engines, helicopters, airplanes, are important segments of the remanufacturing industry, and are characterized by complicated disassembly, repair and assembly process plans, stochastic operations, and the usage of rotable inventory. In view of today's highly competitive business climate, effectively scheduling such services and managing rotable inventory and uncertainties are becoming critical to achieve on-time deliveries and low overall costs. In this paper, a novel formulation for overhaul and repair services is presented where key characteristics, such as uncertain asset arrivals and operation processing times, and rotable parts are abstracted to model an overhaul center and multiple repair shops in a distributed framework to reflect organizational structures. A solution methodology based on decomposition and coordination is developed to schedule operations to minimize total tardiness, earliness, and inventory holding costs. Numerical testing results show that the method is computationally efficient for managing rotable inventory and uncertainties, and generates high quality schedules with low overall costs. The value of rotable inventory to reduce tardiness costs and buffer uncertainties is demonstrated, and the robustness of the new method is evaluated by cases with different settings of machine utilization levels and uncertainty levels. The scalability of the method to solve large problems with hundreds of assets is also demonstrated.

Time-based competition and market globalization make it imperative for supply chains to have reliable product deliveries within customer required lead times. This may not be easy to achieve in view that manufacturing activities are subject to various uncertainties. Furthermore, a delay of one manufacturer may propagate to others through precedence relationship. To improve delivery performance, it is critical to reduce the variance of product lead times. Motivated by the six sigma quality movement, a variance control technique is developed where lead time variances are accurately calculated and significantly reduced through effective scheduling individual manufacturers as well as coordinating across a chain with limited communication requirements. Numerical testing results demonstrate that the new approach is effective to schedule manufacturers on a supply chain 1:0 achieve on-time and reliable deliveries.

Many industries rely on maintenance networks to maintain their key assets, and a key characteristic of such maintenance services is the wide use of rotable parts. In view of today's time-based competition, efficiently managing the rotable inventory becomes imperative for a maintenance network to achieve short turn-around-times and low costs. This, however, is difficult in view of complicated and uncertain maintenance processes, and hybrid inventory replenishments from both new and refurbished parts. As the information on demands and replenishments is highly dependent on maintenance processes, and can be obtained, utilizing this information opens a new way to improve the inventory operational efficiency. This paper presents a new approach for rotable inventory control with the demand and replenishment information. Key characteristics of maintenance processes and hybrid replenishments are abstracted to form a novel model within the context of stochastic optimal control, where the demand and replenishment information is incorporated in the system state. Comparing to traditional approaches with a large-size augmented state, an aggregated state variable is defined based on inventory dynamics to reduce the number of required state components. A solution methodology based on stochastic dynamic programming (SDP) is developed, with stage-wise costs obtained in terms of aggregated state variables. Steady state solutions are computed offline, and are stored as inventory policies to be implemented by table lookup. Simulation results demonstrate the effectiveness of the approach on reducing inventory costs with the demand and replenishment information.

A model of multi-part asset with dependent maintenance cost is presented. The problem is to minimize the long-run average cost per time unit. To share some costs, a good policy may jointly replace multiple parts when an asset is maintained. However, it is difficult to obtain an optimal joint replacement policy in view of combinatorial explosion of the states and stochastic system dynamics. To obtain optimal policies for small problems, a novel method is built by recent developed time aggregation Markov decision approach, which leads to analytical and computational simplifications as compared with traditional Markov decision approaches. One-stage and two-stage analysis methods are developed for large problems. The upper bound of one-stage analysis method for single part problems is obtained to show the insight that it can achieve near or true optimal policy. For multi-part problems, they are proved to satisfy certain necessary optimality conditions. These conditions can significantly simplify their implementation. Numerical results show that they are more efficient and effective than other near optimal methods.

Real world maintenance networks often involve multi-organizational scheduling. The traditional centralized methods are not appropriate for solving the maintenance-scheduling problem because of the existence of private information and decision-making authorities at different organizations. Multi-agent scheduling and coordination is able to protect the private information and retain the decision-making authorities at different organizations. However, it presents its own challenges, such as obtaining a high-quality solution in a timely manner, providing the organizations with guidance on operating economically, being able to solve large-scale problems, and so on. In this paper, a price-based multi-agent scheduling and coordination framework is explored and a systematic study is carried out to evaluate the effects of factors on its performance. The empirical results not only show that the framework is able to quickly find high quality solutions for large-scale problems, but also reflect interesting relationships between selected factors such as resource utilization and performance measures such as mean asset turn-around-time.

The publication offers a note of thanks and lists its reviewers.

Pressed by market globalization, a recent trend for manufacturers is to have their design teams at different locations to better serve local markets and reduce design costs. Under the concurrent engineering paradigm, tasks in a design project are required to be performed in parallel, however, are often interdependent in a complex way. As a result, effective communication and coordination among teams become vital for a project to be successful. The complex interdependencies have not been adequately addressed in the literature. This paper presents a novel optimization formulation that explicitly models the interdependencies among tasks and the communication activities required. A solution methodology that combines Lagrangian relaxation and the surrogate subgradient method has been developed to solve the optimization problem that is inseparable. Backward/forward Dynamic programming is used to solve task subproblems. Numerical results demonstrate that complex dependencies among tasks are satisfied via communication activities, and near-optimal schedules are efficiently obtained.

As more and more companies are relying on their suppliers to provide raw materials or component parts, effective coordination and inventory management of supply chain members became critical issues. Various methods including information sharing and postponing strategy have been explored to improve supply chain performance. However, questions regarding what information to share and the benefits under different conditions for different members are not fully understood. This paper presents a simulation study on a three-level infinite capacity supply chain through a systematic design of experiments. Independent variables include lead times, information sharing patterns, demand uncertainties, and service levels. It is shown through the analysis of means and the analysis of variance that one-way full information sharing is sufficient to achieve good performance. The types of benefit received by different members, however, are different. Furthermore, as more information is shared, the benefit from postponing customization decreases.

Overhaul and repair services are an important segment of the remanufacturing industry, where an asset is disassembled, and component parts are repaired and then assembled to restore the asset to an "as new" condition. A key characteristic of such services is the wide use of rotable parts, i.e., using repaired parts from other assets for assembly, as opposed to waiting for the completion of part repairs from the original assets. However, it is difficult to evaluate the performance of such system. In this paper, and overhaul and repair system characterized by a fork/join structure with rotable inventory is studied. The effects of rotable inventory to system performance are analyzed, and an approximation method is then developed for evaluating key performance measures. By modelling the rotable inventory as a "negative" queue, a system with one overhaul center and one rotable repair shop is first reduced to a tandem queue. Numerical results demonstrate that by this model reduction, TAT can be efficiently estimated within ten percent loss of accuracy as compared with results obtained from hours of simulation. A system with one overhaul center and N rotable repair shops is then reduced to a fork/join system with multiple branches of tandem queues. With appropriate methods to analyze fork/join tandem systems, approximated performance measures can be evaluated.

Lagrangian Relaxation (LR) bas been used for manufacturing scheduling with good results. For practical applications, the method, however, may suffer from slow convergence, and may not be able to generate good results within a required CPU time. To improve convergence and solution quality, a new augmented LR method is presented in this paper where additional penalty terms associated with constraint violation is added to the objective function. To overcome the inseparability difficulty caused by the penalty term, a surrogate subgradient direction is used to update the multipliers and to guarantee solvability and convergence. Numerical testing results demonstrate that compared with the standard LR method, the augmented LR method is computationally efficient, and generates good schedules with reduced cost.

Pressed by market globalization and concomitant competition, more and more manufacturers are relying on their suppliers to provide raw materials and component parts so as to focus on their core competence. As a result, the coordination of activities across a network of suppliers becomes critical to quickly respond to dynamic market conditions. In this paper, a novel framework combining mathematical optimization and the contract net protocol is presented for make-to-order supply network coordination. Interactions among organizations are modeled by a set of interorganizational precedence constraints and the objective is to achieve the organizations' individual and shared goals of fast product delivery and low inventory. These interorganizational constraints are relaxed by using a set of interorganizational prices that represent marginal costs per unit time for the violation of such constraints. The overall problem is thus decomposed into organizational subproblems, where individual organizations schedule their activities based on their internal situations and interorganizational prices. Coordination is achieved through an iterative price-updating process carried out in a distributed and asynchronous manner. With prices dynamically updated and schedules adjusted, this approach coordinates activities to fulfill existing commitments while maintaining agility to take on new orders. Numerical testing results show that interorganizational prices converge and prices may change as new orders arrive to reflect the new pressure on deliveries.

In view of today's "time-based competition," scheduling manufacturing operations using the most advanced scheduling tools has become a crucial issue for manufacturers. This can be achieved by using an Internet-based scheduling system. The main considerations in designing such a system are how to provide an effective scheduling tool without major investment, and how to ensure fast and easy access for manufacturers who have diversified computational platforms and settings. This paper presents such an Internet-based scheduling system that meets these considerations. The system is a novel combination of judiciously selected components with several architectural design options, and delivers high quality scheduling solutions in a reasonable computational time via a user friendly and secure Internet environment. The testing results are compared for different implementations of scheduling systems and results for problems of different sizes are provided.

A time window based approach is developed for job shop scheduling problems to minimize the weighted earliness and tardiness cost. With the time windows provided by Lagrangian relaxation within which parts are processed to minimize the cost and an effective algorithm to find a feasible schedule within or approximately within the windows, the approach can generate schedules better than those generated by the Lagrangian relaxation approach for large problems in a similar computation time. This demonstrates that our approach can be used to solve practical scheduling problems with an improved performance.

In this paper, a macro-level scheduling method is developed to provide high-level planning support for factories with multiple coordinating cells. To model the problem with manageable complexity, detailed operations of a product within a cell are aggregated as a single operation whose processing time is related to the amount of resources allocated. "Overload variables" are introduced and penalized in the objective function. The goal is to properly allocate resources, efficiently handle complicated process plans, and coordinate cells to ensure on-time delivery, low working-in-process inventory, and small resource overload. The formulation obtained is "separable" and can be effectively decomposed by using Lagrangian relaxation. A combined backward and forward dynamic programming (BFDP) method is developed to solve a product sub-problem after a novel transformation of its process plan. The BFDP is further simplified and solved approximately.

Manufacturing enterprise automation was focused on factory level where scheduling is a key issue in the past. As more and more companies are relying on their business partners or suppliers, the coordination of activities through the chain of suppliers becomes critical to quickly respond to changing market conditions. The rapid growth of information technology is now opening up a unique opportunity for companies to coordinate with their customers and suppliers to further improve their responsiveness. Effective approaches for coordination, however, have to be developed to grab the opportunity. In the paper, existing approaches for scheduling and coordination are summarized, important issues for coordination such as architecture, solution concept and scalability are discussed, and a price-based approach is presented for supply chain coordination. In the approach, each organization makes its own decision based on the prices associated with inter-organization constraints, and the coordination among organizations is performed in a distributed and asynchronous way with prices iteratively adjusted by related organizations. The coordination approach is scalable if the prices are constantly adjusted to dynamically adapt to changing conditions and the price adjustment process is stable.

Inventory plays a major role in deciding the overall manufacturing costs, and a good scheduling system should balance the on-time delivery of products versus low work-in-progress (WIP) inventory. In this paper, the "constant work-in-process" (CONWIP) concept is applied to job shop scheduling to effectively control WIP inventory. A new mathematical formulation of CONWIP-based job shop scheduling with a separable structure is presented. By using a synergistic combination of Lagrangian relaxation, dynamic programming, and heuristic methods, good schedules are obtained in a reasonable amount of computation time. Results show that the new method can directly control the maximum WIP levels while maintaining good on-time delivery performance.

Manufacturing scheduling is an important but difficult task. In order to effectively solve such combinatorial optimization problems, the paper presents a Lagrangian relaxation neural network (LRNN) for separable optimization problems by combining recurrent neural network optimization ideas with Lagrangian relaxation (LR) for constraint handling. The convergence of the network is proved, and a general framework for neural implementation is established, allowing creative variations. When applying the network to job shop scheduling, the separability of problem formulation is fully exploited, and a new neuron-based dynamic programming is developed making innovative use of the subproblem structure. Testing results obtained by software simulation demonstrate that the method is able to provide near-optimal solutions for practical job shop scheduling problems, and the results are superior to what have been reported in the neural network scheduling literature. In fact, the digital implementation of LRNN for job shop scheduling is similar to the traditional LR approaches. The method, however, has the potential to be implemented in hardware with much improved quality and speed.

Inventory plays a major role in deciding the overall manufacturing costs, and a good scheduling system should balance the on-time delivery of products versus low work-in-process (WIP) inventory. In this paper, the "constant work-in-process" (CONWIP) concept is applied to job shop scheduling to effectively control WIP inventory. A new mathematical formulation of CONWIP-based job shop scheduling with a separable structure is presented. By using a synergistic combination of Lagrangian relaxation, dynamic programming, and heuristic methods, good schedules are obtained in a reasonable amount of computation time. Results show that the new method can directly control WIP levels while maintaining good on-time delivery performance.

Multilayer perceptron networks have been used to perform a variety of forecasting tasks, and back propagation is one of the most widely used training methods. It is a gradient method that can get stuck in local minima and has slow convergence. This paper presents a novel learning algorithm using the multiplier method. Testing results show that the new method has better convergence performance and generalization capability as compared to the back propagation method.

This paper presents an effective approach for job-shop scheduling considering uncertain arrival times, processing times, due dates, and part priorities. A separable problem formulation that balances modeling accuracy and solution method complexity is presented with the goal to minimize expected part tardiness and earliness cost. This optimization is subject to arrival time and operation precedence constraints, and machine capacity constraints. A solution methodology based on a combined Lagrangian relaxation and stochastic dynamic programming is developed to obtain dual solutions. A good dual solution is then selected by using "ordinal optimization", and the actual schedule is dynamically constructed based on the dual solution and the realization of random events. The computational complexity of the overall algorithm is only slightly higher than the one without considering uncertainties, and a dual cost is proved to be a lower bound to the optimal expected cost for the stochastic formulation considered.

Manufacturing scheduling is an important but difficult task. Building on our previous success in developing optimization-based scheduling methods using Lagrangian relaxation for practical applications, this paper presents a novel Lagrangian relaxation neural network (LRNN) optimization technique. The convergence of LRNN for separable convex programming problems is established. For separable integer programming problems, LRNN is constructed to obtain near optimal solution in an efficient manner. When applying LRNN to separable job shop scheduling, a new neural dynamic programming method is developed to solve subproblems making innovative use of the dynamic programming structure. The synergy of Lagrangian relaxation and neural dynamic programming leads to a powerful neural optimization method for job shop scheduling. Testing results obtained by software simulation demonstrate that the performance is superior to what has been reported in the neural network literature. Results are also very close to what were obtained by a state-of-the-art optimization algorithm, and should be much improved when the method is refined and implemented in hardware.

For the production of mid to high volume products with long setups, products are generally grouped into production lots. Previously, lot splitting techniques were used to split a lot into multiple smaller transfer lots, and each transfer lot can be transferred to its successor operation immediately upon completion. This paper presents a novel integer programming formulation for scheduling job shops with transfer lots without introducing excessive decision variables relating to transfer lots. A combined Lagrangian relaxation and dynamic programming algorithm is used to solved the problem. After coupling constraints are relaxed by using Lagrange multipliers, the problem is decomposed into lot-level subproblems, and an efficient dynamic programming algorithm is developed to solve these subproblems. The multipliers are updated at the high level by using the previously developed reduced complexity bundle method. Numerical testing results show that the algorithm can be effectively used to schedule job shops with transfer lots.

In mid to high volume apparel production, garments are typically grouped into production lots, and each lot is processed in its own manufacturing cell. A flexible manufacturing system used in this environment enables quick cell configuration, and the efficient operation of cells. The scheduling problem is to decide when to set up a cell and consequently begin garment production in the cell, and to decide the quantity of machines to allocate to each cell, under the constraints of limited machines. The time to process a production lot depends on the quantity of machines allocated to the cell in which the lot will be processed, and thus scheduling and resource allocation are highly coupled. In this paper, an accurate and low-order integer programming model is developed which integrates scheduling and resource allocation. Insight is provided into how the model relates to the operation of a real factory. The model is solved using the Lagrangian relaxation methodology, and a new bundle method is used for optimizing the Lagrangian dual function. The combination of an accurate low-order model, Lagrangian relaxation, and the bundle method is shown to be very practical.

A machining center is an advanced NC (numerical control) machine that has the capability to perform a variety of operations on a part by automatically changing the cutting tools. Because of the versatile processing capabilities, a machining center is often a production bottleneck, and effective scheduling can result in significant improvement of system performance. The problem, however, is very difficult since many factors such as machine setups, pallets, tool magazine, and the possible tool overlapping among different part types, have to be considered. This paper presents an optimization-based approach for the scheduling of a machining center with two pallets. A novel "separable" problem formulation that considers the above mentioned factors is presented. Lagrangian relaxation is applied to decompose the problem into simple subproblems, which are efficiently solved without encountering complexity difficulties. The subgradient method is then used to update the multipliers. Preliminary testing results indicate that the approach is effective, and the algorithm provides a valuable tool for solving standalone machining center scheduling problems.

The author states that, in the original paper (D.L. Hoitomt and P.B. Luh ibid., vol. 9, no. 1, p. 1-13, 1993), the model formulation of the scheduling problem is highly irregular. If one were to consider the formulation by itself it would seem that since neither the precedence nor processing time constraints are linked to time, we could set all /spl delta//sub ijkh/=0 and obtain a feasible solution with jobs overlapping on machines. It is noted that in the subsequent relaxation of the capacity constraint, the binary variables have been set to 1 from start to finish time of the corresponding operation to account for capacity. The need for the model formulation to include such constraints explicitly is discussed, and the original authors discuss the relevance of the comments. The existence of related and similar results in previous works is also considered.>

Underlying each production system are activities fraught with uncertainty; for example, uncertain future demand, machine breakdowns, and processing time estimates for one-of-a-kind parts. These uncertain events can cause any detailed schedule to become outdated, and the effects may propagate throughout the schedule, affecting product delivery dates. Scheduling algorithms considering future uncertainties could improve the quality of schedules and, as a result, smooth the production of the system. As a step towards incorporating uncertainties in the scheduling consideration, this paper presents a fuzzy optimization methodology for scheduling single operation parts on identical machines with possible breakdowns. A fuzzy optimization formulation is first developed. A Lagrangian relaxation technique is used to decompose the problem into part-level subproblems and a fuzzy membership subproblem. The Lagrange multipliers are then updated by using a subgradient method. To evaluate the performance of the resulting algorithm in a dynamic environment, fuzzy simulation is developed. Preliminary testing results show that, with possible machine breakdowns, this algorithm outperforms the deterministic one.>

A bill of materials specifies the sequence in which parts are to be processed and assembled in order to manufacture a deliverable product. In practice, a bill of materials may be quite complex, involving hundreds of parts to be processed on a number of limited resources, making scheduling difficult. This has forced many practitioners to turn to Material Requirements Planning (MRP) and heuristic rules to perform scheduling. These methods are seldom integrated, resulting in unreliable completion times for products and, hence, low customer satisfaction. This paper addresses the issue of integrally scheduling parts that are related through a bill of materials for the purpose of improving the on-time performance of products as well as reducing work-in-process (WIP) inventory. The technique presented here is based on an existing Lagrangian relaxation (LR) approach for the scheduling of independent parts in a job shop. An auxiliary problem formulation with a modified subgradient method is adopted to improve the computation time of the existing LR approach. This improved LR approach allows the bill of material constraints to be considered directly in the problem formulation.>

The use of Lagrangian relaxation to schedule job shops, which include multiple machine types, generic precedence constraints, and simple routing considerations, is explored. Using an augmented Lagrangian formulation, the scheduling problem is decomposed into operation-level subproblems for the selection of operation beginning times and machine types, with given multipliers and penalty coefficients. The multipliers and penalty coefficients are then updated at the higher level. The solution forms the basis of a list-scheduling algorithm that generates a feasible schedule. A procedure is also developed to evaluate the quality of this feasible schedule by generating a lower bound on the optimal cost. Numerical examples are taken from a representative industrial job shop. High-quality schedules are efficiently generated every other day over a three-week period, with costs generally within 4% of their respective lower bounds. The methodology compares favorably with knowledge-based scheduling.>

A method for batching jobs within a class in advance of sequencing is presented. It is shown that under certain simplifying assumptions, optimal batch composition can be obtained independent of the sequencing problem. This composition is determined by assigning parts to batches according to an earliest due date (EDD) rule. An efficient methodology for sequencing the batches based on the Lagrangian relaxation technique is presented. The solution to the Lagrangian relaxation dual problem is a lower bound on the cost of the optimal schedule. If the assumptions are relaxed, the EDD rule becomes a heuristic for solving the batch composition problem, and the same batch sequencing algorithm can be used to obtain a schedule. In that case, the dual cost is a lower bound on the cost of all possible sequences with the same batch composition. Preliminary results show that good schedules can be efficiently obtained.>

Dynamic, distributed, human team resource allocation and task processing is considered in an abstracted Navy-like command and control environment. A hierarchical team of one leader and three subordinates is to process multiple types of randomly arriving tasks (threats) that have different processing resource requirements, time requirements, values, and deadlines. Each subordinate is responsible for processing a subset of these tasks. Two kinds of team leader (resource coordinator) are considered: an active leader who transfers resources among the subordinates, and a passive leader who provides offline guidance only. The individual decision-making and coordination processes of both types of leader are described and analytically modeled. A team-in-the-loop experiment provides data to compare with model predictions. The self-centered bias (wherein human decision-makers overvalue their own responsibilities) is identified as a major contributor to model-data mismatch. Incorporating such human cognitive limitations and biases into the normative models successfully replicates the experimental results.>

A distributed job shop scheduling algorithm has been implemented in the LAN (local area network) environment. The algorithm is a good candidate for distributed implementation since much of the computation time required for a solution is expended in distributable portions of the algorithm. A distributed processing support system (DPSS) was developed to ease the implementation of this and future distributed algorithms. Preliminary results indicate considerable potential for reducing the computation time. Additional portions of the algorithm may be distributed to improve the results, and streamlining of the underlying communication mechanism of DPSS is underway.>

Two related issues in the development of scheduling algorithms are addressed. The first centers on the inability of schedulers to predict when jobs will actually be completed. Existing jobs scheduled without information concerning future arrivals are frequently postponed to make room for incoming jobs of significant urgency. A probabilistic method of considering future arrivals when scheduling a bottleneck work center via the Lagrangian relaxation method is presented. In addition, a method of reducing the scheduling time step is presented. Implementation of a smaller time step allows for more accurate representation of job processing times. Both methods are combined to improve the determination of promised delivery dates.>

Consideration is given to distributed dynamic resource allocation within a two-person team. Having different but overlapping responsibilities, two geographically separated human decision-makers (DMs) are to process multiple types of randomly arriving tasks with a set of renewable resources. To maximize the team reward for task processing, the DMs must coordinate on the assignment of common tasks (tasks of joint responsibility) and on the transfer of resources. A normative-descriptive approach is adopted to describe the human decision-making process in the above setting. The approach starts with a normative model that predicts the team's optimal decision-making and a human-in-the-loop experiment that generates experimental data. Human limitations and cognitive biases are then identified to explain differences between model predictions and experimental data. Incorporating human limitations and cognitive biases into the normative model, a normative-descriptive model is obtained. This model matches experimental data in almost all measures and provides insights to human decision-making behavior.>

An exploration is made of the use of Lagrangian relaxation to schedule job shops, which include multiple machine types, generic precedence constraint, and simple routing considerations. From an augmented Lagrangian formulation, a decomposed solution methodology is developed using a Jacobi-type iterative approach. The subgradient method and the multiplier method are used to update the multipliers and the penalty coefficients. The dual solution forms the basis of a list scheduling algorithm which generates a feasible schedule. Unfortunately, the dual cost is not a lower bound on the optimal cost because of the Jacobi iterative technique employed. In order to evaluate the schedule, a second problem formulation is adopted. Its solution would ordinarily require prohibitive memory and considerable computation time. By utilizing part of the multipliers obtained from the first problem formulation, however, an effective lower bound on the optimal cost can be quickly obtained. A numerical example is given in which schedule cost is within 2% of its lower bound.>

A methodology for scheduling independent jobs with due dates on identical, parallel machines is presented. The jobs have different levels of importance and various processing times on the machines, and the objective is to minimize the total weighted job tardiness of the schedule. Since the problem is NP hard, the goal is not to obtain the optimal schedule. Rather, an efficient near-optimal algorithm based on Lagrangian relaxation is presented. This approach provides a lower bound on the cost, which can be used as a measure of suboptimality. According to an implementation for a work center at Pratt and Whitney, most schedules generated are within 1% of the optima with reasonable CPU times. Furthermore, the method provides valuable job interaction information, which shop floor management uses to answer 'what if' questions, to reconfigure the schedule to accommodate dynamic changes, and to schedule new jobs.>

The authors present a methodology for scheduling independent jobs with due dates on identical parallel machines. The jobs have different levels of importance and various processing times on the machines, and the objective is to minimize the total weighted job tardiness of the schedule. Since the problem is NP-hard, the goal is not to obtain the optimal schedule. Rather, an efficient near-optimal algorithm based on Lagrangian relaxation is presented. A nice feature of this approach is that it provides a lower bound on the cost, which can be used as a measure of suboptimality. On most problems tested, results are within 1% of the optima and have reasonable CPU times. Furthermore, the method provides job interaction information, which is then used to provide quick answers to 'what if' questions, to reconfigure the schedule to accommodate dynamic changes, and also to schedule jobs.>

Results are presented on the empirical part of a normative-descriptive approach for studying distributed resource allocation in human teams. An experimental paradigm was developed with the key ingredients of different command structures, finite time and resource available for task processing, distributed resource ownership and dynamic resource sharing, etc. Using the paradigm, an experiment was run across three sets of independent variables: two command structures (hierarchical and parallel), two levels of tempo (low and high task arrival rates), and three levels of reward structure. A queueing model was developed; to select nominal values of key experimental parameters. The model extends the classical M/D/1 queueing models to incorporate finite time available for task processing and the distributed resource ownership. Several experimental hypotheses were generated to address critical issues in team resource allocation.>

A new approach is presented for solving long-horizon, constrained optimal control problems by using the mixed coordination method. The method was originally developed for unconstrained optimal control problems, with key ideas including time decomposition, mixed coordination and parallel processing. In extending the method to constrained problems, constraints on state and control variables are relaxed by using the multiplier method. For a given set of Lagrange multipliers, the problem is unconstrained and is solved by using the mixed coordination method. The Lagrange multipliers are then updated in a simple and efficient way. Three problems, including one with nonlinear system dynamics and constraints, and a hydroelectric scheduling problem with ten reservoirs, are tested. Results shows that the new approach is numerically stable, and significant speedups are obtained in a simulated parallel-processing environment. The method can be easily extended to handle unpredicted changes during the online operation phase of a system.>

A manufacturing system with one server (machine), two classes of jobs, finite buffer sizes and nonnegligible setup times is analyzed. Classes are served in a fixed order. A new cycling service discipline called "triggered" cycling is introduced as a type of exhaustive cycling where a job must be present to process before the setup for that class takes place. The state of the machine, whether in setup or in processing, is explicitly considered in the model. Utilization, mean queue length and cycle time are derived by using Markovian analysis, first under a fixed lot size environment and then with random lot sizes. With lot sizes fixed (deterministic), increasing arrival rates, setup times and service times generally increase utilization, cycle time and queue length. Sensitivity analyses indicate a minimum exists for queue length with respect to lot size. When lot sizes are random, negligible variations in cycle time result, with somewhat smaller queue length as compared to the fixed lot size case. Despite lack of a product form solution to the problem, an approximate mean value analysis yielding cycle time is developed and the results are compared to Markovian analysis. Numerical studies show robustness of the mean value analysis for utilizations under 0.7.