Search

Currently, most independent system operators in the U.S. run auctions by minimizing the total bid cost ["bid cost minimization" (BCM)], and then calculate payments based on market clearing prices. Under this setup, the payment cost could be significantly higher than the minimized bid cost. Recently, an alternative auction mechanism that minimizes the consumer payment cost ["payment cost minimization" (PCM)] has been discussed. Literature has shown that for the same set of bids, PCM leads to reduced consumer payments. However, market participants may bid differently under the two auctions, and therefore, the payment reduction may not be realized. This necessitates the study of strategic behaviors of participants. In this paper, suppliers' bidding strategies in a day-ahead energy market are investigated for both auctions by using a game theoretic framework with Nash equilibrium as the solution concept. To simplify the solution process, the originally continuous strategies are discretized to form matrix games. Discretization may cause the loss of equilibria and the creation of artificial solutions. To reduce these side effects, "approximate Nash equilibria" are introduced to recover lost equilibria, and additional strategy samples are evaluated to eliminate artificially created solutions. Games are then solved by examining supplier payoffs obtained from running auctions. Characteristics of auctions are exploited, leading to improved computational efficiency. Numerical testing results show that the PCM leads to significant payment reductions and relatively small increases of production costs as compared to BCM. Also, the ?hockey-stick? bidding is more likely to occur under BCM. Finally, long-term impacts of PCM are discussed, and whether it would lower costs to consumers in the long run, including capacity payments, remains to be investigated.

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.

A job shop is a typical environment for manufacturing low-volume and high-variety discrete parts, where parts are of various due dates, priorities, and sequences of production operations. Good scheduling of when to do what using which resource is critical and challenging for the competitiveness of job shops. The Lagrangian relaxation neural network (LRNN) presented by Luh et al. provides an effective solution to this problem. To further speed up the scheduling of large problems, the parallelism of the LRNN approach is exploited in this paper for hardware implementation. A parallel processor based on the single-instruction multiple-data-stream architecture and its associated instruction set are designed. The architecture is implemented in a single-poly quadruple-metal 0.35-/spl mu/m CMOS technology. Test results shows that the fabricated chip achieves 10 and 30 times speed-up when compared with several commercial digital signal processor chips and a 600-MHz PC, respectively.

Time-based competition and market globalization make it imperative for supply chains to have short and reliable order deliveries. This is difficult to achieve in view that activities of individual manufacturers are subject to various uncertainties such as unknown order arrivals and stochastic operations. Furthermore, delays of one manufacturer may propagate to it downstream manufacturers through precedence relationships. To stay competitive, it is critical to control variability and order lead-times across a chain, and to achieve delivering final products within specified target time windows with high probability. This is the key idea of achieving x-sigma delivery performance. In this paper, make-to-order supply chains with sequential workflows are considered. An effective solution methodology is developed to minimize overall order tardiness, earliness costs and delivery variability through effective scheduling and coordination. To accommodate new arrivals while fulfilling commitments of existing orders, a rescheduling approach is presented to generate high-quality schedules in a timely fashion. Numerical testing results demonstrate that the new approach is effective to schedule manufacturers across a chain to achieve the required three-sigma deliveries.

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.

By combining neural network optimization ideas with “Lagrangian relaxation” for constraint handling, a novel Lagrangian relaxation neural network (LRNN) has recently been developed for job shop scheduling. This paper is to explore architectural design issues for the hardware implementation of such neural networks. A digital circuitry with a micro-controller and an optimization chip is designed, where a parallel architecture and a pipeline architecture are explored for the optimization chip. Simulation results show that the LRNN hardware will provide near-optimal solutions for practical job shop scheduling problems. It is estimated that the parallel architecture will obtain one order of magnitude speed gain, and the pipeline architecture will obtain two orders speed gain as compared with the currently used method.

This paper presents a new parallel conjugate direction method. Developed from parallel computation concept, the method generates n new conjugate directions mostly in parallel without explicitly using the approximate Hessian, and derives a new point by linearly combining n line search results that are obtained concurrently. Moreover, the convergence characteristics of the method is fully discussed under both the quadratic and non-quadratic settings

Building evacuation has long been recognized as an important issue to improve occupant survivability in case of emergencies. This paper presents coherent modeling and effective coordination of egress and HVAC systems for offline evacuation planning, with the goal to evaluate what is the best that can be achieved assuming that occupants follow egress instructions. Key characteristics of the egress and HVAC systems are abstracted to establish two linear state-space models, and their interdependencies are formulated as linear inequality constraints. To solve the problem, each system establishes a local representation of the global problem by combining its own detail model with an aggregate model of the other system. Model aggregation is achieved based on wavelet transformations, and a local representation of the global problem is solved by using dynamic programming within the Lagrangian relaxation and surrogate optimization framework. The novelty of our approach lies in the coherent transformations of states, multipliers, and decisions across different scales for interdependent systems with discrete variables. The method can generate a good solution when time is limited and allow incremental improvement when more time is available. Numerical results demonstrate the effectiveness of our method.

Standard market design for deregulated electricity markets adopts locational marginal pricing mechanism to manage transmission congestion. Currently independent system operators who run the electricity markets determine the power schedule by minimizing the total supply offer costs in auctions, but use marginal prices for payment in the subsequent settlement process. This inconsistence between the auction mechanism and the settlement mechanism has been pointed out, and payment minimization auction that minimizes the payment costs in the settlement process has been suggested as an alternative auction mechanism in recent papers. For payment minimization auctions, market settlement prices become decision variables in the auction process. As a result, how to define those prices is a key issue in the payment minimization auction. Transmission capacity constraints play an important role in determining the market prices. With transmission capacity constraints, locational prices are used to reflect transmission congestion. In this paper, locational prices and transmission congestion prices are defined through locational price decomposition formula and locational price-offer price inequalities. Payment minimization auction considering transmission capacity constraints is then formulated by incorporating the decomposition formulas, locational price-offer price inequalities, transmission capacity constraints, and other constraints. A Lagrangian relaxation and surrogate optimization framework is developed to overcome the inseparability of the resulting problem. Variable adjustment is applied in the solving subproblems to avoid local minimums. Examples are both analyzed and tested to illustrate the formulation and the solution methodology

This paper presents the research and development of the hybridization of a mathematical programming approach with a promising evolution on the daily imaging scheduling problem for the newest generation of low-orbit, earth observation satellite, FORMOSAT-2. This NP-hard satellite scheduling problem belongs to a class of single-machine scheduling problems with salient features of job-assembly characteristic, sequence-dependent setup effect, and constraint of operating time window. We construct innovative hybrid techniques that incorporate the best of Lagrangian relaxation and Tabu search solution approaches to solve this scheduling problem. Numerical results demonstrate that the proposed hybrid algorithms are effective and efficient in applications to the real problems.

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.

Deregulated electricity markets use a market clearing price (MCP) auction mechanism to pay market participants for energy and ancillary service products. Currently most independent system operators (ISO's) determine MCP's by using a traditional unit commitment approach that minimizes the offered costs. This is not appropriate because the costs minimized are not the purchase costs to be paid by customers. How to correctly set the MCP's is an open and challenging issue, and no solution has yet been reported in the literature. This paper presents an effective method to solve the new pay-at-MCP problem. In view of the specific features of the new problem including the nonseparability of the objective function and the discontinuity of offer curves, the standard Lagrangian relaxation technique cannot be applied. Our key idea is to use the augmented Lagrangian relaxation approach, but to form and solve MCP and offer subproblems by using an advanced surrogate optimization framework. Potential pitfalls and intricacies of our method are intuitively illustrated. Numerical testing results demonstrate that the method is effective, and the resulting costs are significantly lower than what are obtained by using the unit commitment approach.

A method is presented to solve constrained optimal control problems. Its main advantages are that it overcomes the difficulty caused by the growing number of constraints, and it can be used to solve general optimal control problems with linear system dynamic and linear constraints on states and controls (without requiring special structures on the part of A and B matrices). Its key features include decomposition along the time axis, coordination using initial and terminal states of subproblems, and parallel processing to take advantage of the availability of cost-effective parallel processing facilities. The numerical testing result shows that the approach is feasible and that the two-level algorithm is suitable for parallel processing. >

The daily scheduling for a research and development (R&D) pilot line of semiconductor wafer fabrication is addressed. An integer programming problem formulation is given, which captures the salient features, such as high variety and very low volume, cyclic process flows, batching at diffusion machines, single mask for each photolithography operation, loop test, and engineering splitting and merging of wafer lots. A solution methodology for scheduling flow shops based on Lagrangian relaxation is extended to solve this class of problems. It may also effectively handle data inaccuracy and cope with production uncertainties. Numerical results demonstrate both the feasibility and potential of this method. >

The Lagrangian relaxation method in optimization is examined to explain team coordination mechanisms in a distributed decision-making process. The dual variables (multipliers) are analyzed to reveal the impacts of potential conflicts, evaluate the benefits of coordination activities, and guide the allocation of coordination effort. Although the discussion is based on a generic team task sequencing problem, the issues addressed are fundamental for systematically investigating human team coordination. >

In this paper, we focus on the design issues of applying an SPC control chart to end-of-line wafer acceptance test (WAT) data. Since the sequence of end-of-line data is not the same as the sequence in each process step, an abnormal trend in any of the process steps is more difficult to detect based on the end-of-line data than based on single process data (if available). To overcome this deficiency, we propose an exponentially weighted moving average method for sequence-disordered data (EWMA/SD). The basic idea is that the moving average can smooth out the sequence-disordered effect and weighting factors allow us to choose an effective window size so that the underlying trend can be seen. It is different from the traditional EWMA method as it has the capability of handling sequence-disordered data. An end-of-line trend detection system has been developed for validation of the method, which consists of three modules: a run length distribution generator, an optimal parameter generator, and an EWMA/SD control chart. Based on process characteristics, the corresponding run lengths of an EWMA/SD control chart for different parameter vectors are derived by the Markov chain approach. The optimal parameter vector is chosen as the one which meets the requirement for maximum false alarm rate and maximizes the detection speed at the same time. Results of simulation and field data validation show that EWMA/SD is able to smooth out the sequence-disordered data, be sensitive to process changes, and be robust to background noise.

Job shop is a typical environment for manufacturing high-variety and low-volume discrete parts. Good scheduling is critical and challenging to the competitiveness of job shops. The Lagrangian relaxation neural network (LRNN) provides an approach of quantifiable quality and successful industrial applications. To further speed up scheduling for large-scale problems, in this paper, the parallelism of the LRNN approach is exploited for hardware implementation. New designs include a SIMD architecture, its associated instruction set and detailed circuits. Logic level simulation of the circuit design shows consistent schedules with those obtained by a software implementation. The hardware implementation is expected to have a one to two orders speed-up over the software one.

This paper studies function minimization using conjugate gradient method (CGM) and presents two new methods that do not require accurate line searches to generate conjugate directions. The idea is to use much relaxed line searches to obtain step sizes "close" to the optimal ones. Correction vectors are then formed to compensate for the inaccuracy and yield conjugate directions. There have been some algorithms of this type in the literature. However, their performances are not as good as expected since the validity of their correction terms heavily depend upon quadratic function form. Consequently, search directions generated may not satisfy the conjugacy relationship for an arbitrary convex function. In our first method (M1), correction vectors are formed by explicitly considering the function to be minimized. In our second method (M2), correction vectors are formed by utilizing diagonal elements of the Hessian matrix. In both cases, "compensated" conjugate directions are close to directions obtained from accurate line searches. Because of the proper incorporation of additional information (structure of the function in M1 and diagonal elements of Hessian in M2), both the number of iterations and the number of function evaluations are reduced while no cumbersome matrix manipulations and matrix inversions are involved. Two methods show good convergence. Testing results indicate that about 30% to 50% reductions in function evaluation are achieved in comparison to the traditional CGM algorithm.

This paper presents a new method to decompose a large scale optimal control problem into a hierarchical optimization problem, in which low level subproblems have much shorter time horizon. The initial and final states of each subproblem are chosen as coordination parameters to glue all subproblems together. In such a decomposition, the high level problem is a parameter optimization problem, and subproblems are completely decoupled so that they can be solved in parallel. It is shown that the decomposed two-level optimization problem is equivalent to the original problem. Moreover, the high level problem is a convex parameter optimization problem if the original problem has a convex cost function and linear system dynamics. A parallel processing algorithm based on the gradient method for the high level problem is presented. A numerical example is used to illustrate the ideas and demonstrate the feasibility of the approach.

This paper presents an effective, parallel algorithm for solving constrained optimal control problems with long time horizons. The basic idea is to first relax all contraints but the system dynamics by using the multiplier method. A time decomposition and target coordination scheme is then used to decompose the resultant unconstrained optimal control problem into a two-level optimization with a structure for parallel processing. A three-level optimization algorithm is developed to determine the multipliers and to solve the associated two-level unconstrained problem. The algorithm is a hybrid of the multiplier method, Newton method and the Differential Dynamic Programming technique, and has a highly paralel structure at each level of the algorithm. The algorithm is relatively easy to implement, convergent, and applicable to problems with quite general constraints and system dynamics. Numerical results demonstrate its feasiblity and potential computation efficiency when used for parallel processing.

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

By using advanced optimization methods, a production scheduling algorithm is developed for discrete-part, make-to-order type of flexible flow shops. The goal of scheduling is to meet due dates and the problem is formulated as a large-scale integer programming problem. The scheduling algorithm includes four parts: decomposition by Lagrangian relaxation into subproblems, a minimum cost linear network flow algorithm for solving subproblems, a subgradient algorithm for solving the dual problem, and a heuristic to obtain a near-optimal and feasible schedule. The algorithm is then compared with a heuristic rule that is considered effective by some local manufacturing firms. Preliminary results show that the scheduling algorithm not only is better in optimality but also provides more insights into scheduling complicated operations. >

The authors present further developments of a production scheduling algorithm introduced by S.C. Chang et al. (1990) for the class of discrete-part, make-to-order flexible flow shops where set-up costs and times are negligible. The scheduling problem is first formulated as a large-scale integer programming problems and a solution approach based on Lagrangian relaxation and minimum-cost linear network flow is then developed. Compared to the work of Chang et al., the present work modifies the objective of scheduling to meeting due dates just in time, considers finite buffers, completes the algorithm for finding a feasible schedule, and evaluates the algorithm through numerical experimentations. Numerical results indicate that the scheduling algorithm is near-optimal and has a reasonable computational efficiency for short-term scheduling. Algorithmic features and future research issues are also addressed. >