Probabilistic production costing: An investigation of alternative algorithms

New production cost algorithms are compared with representative algorithms used by the electric utility industry. Accuracy and efficiency of new and conventional algorithms are assessed using the framework of probabilistic production costing. Their usefulness in the context of long-term capacity expansion models is evaluated. Accuracy is considered in two contexts: first, in fitting original customer demand; and second, in approximating generator forced outages. Comparisons of algorithm efficiency are based on an EPRI synthetic system with dispatch of 174 units. Conventional algorithms are drawn from models in use by TVA, Southern Company and MIT. The new algorithms are based upon continuous functions for fitting the equivalent load curve.     

Tractable supply chain production planning,modeling nonlinear lead time and quality of service constraints

This paper addresses the task of coordinated planning of a supply chain (SC). Work in process (WIP) in each facility participating in the SC, finished goods inventory, and backlogged demand costs are minimized over the planning horizon. In addition to the usual modeling of linear material flow balance equations, variable lead time (LT) requirements, resulting from the increasing incremental WIP as a facility’s utilization increases, are also modeled. In recognition of the emerging significance of quality of service (QoS), that is, control of stockout probability to meet demand on time, maximum stockout probability constraints are also modeled explicitly. Lead time and QoS modeling require incorporation of nonlinear constraints in the production planning optimization process. The quantification of these nonlinear constraints must capture statistics of the stochastic behavior of production facilities revealed during a time scale far shorter than the customary weekly time scale of the planning process. The apparent computational complexity of planning production against variable LT and QoS constraints has long resulted in MRP-based scheduling practices that ignore the LT and QoS impact to the plan’s detriment. The computational complexity challenge was overcome by proposing and adopting a time-scale decomposition approach to production planning, where short-time-scale stochastic dynamics are modeled in multiple facility-specific subproblems that receive tentative targets from a deterministic master problem and return statistics to it. A converging and scalable iterative methodology is implemented, providing evidence that significantly lower cost production plans are achievable in a computationally tractable manner.     

Approximating Fluid Schedules in Crossbar Packet-Switches and Banyan Networks

We consider a problem motivated by the desire to provide flexible, rate-based, quality of service guarantees for packets sent over input queued switches and switch networks. Our focus is solving a type of online traffic scheduling problem, whose input at each time step is a set of desired traffic rates through the switch network. These traffic rates in general cannot be exactly achieved since they assume arbitrarily small fractions of packets can be transmitted at each time step. The goal of the traffic scheduling problem is to closely approximate the given sequence of traffic rates by a sequence of transmissions in which only whole packets are sent. We prove worst-case bounds on the additional buffer use, which we call backlog, that results from using such an approximation. We first consider the NtimesN, input queued, crossbar switch. Our main result is an online packet-scheduling algorithm using no speedup that guarantees backlog at most (N+1)² /4 packets at each input port and each output port. Upper bounds on worst-case backlog have been proved for the case of constant fluid schedules, such as the N²-2N+2 bound of Chang, Chen, and Huang (INFOCOM, 2000). Our main result for the crossbar switch is the first, to our knowledge, to bound backlog in terms of switch size N for arbitrary, time-varying fluid schedules, without using speedup. Our main result for Banyan networks is an exact characterization of the speedup required to maintain bounded backlog, in terms of polytopes derived from the network topology     

An efficient algorithm for optimal reservoir utilization inprobabilistic production costing

An efficient and accurate algorithm is presented which determines optimal storage reservoir utilization (pumped hydro) in probabilistic production cost models with multiple storage, thermal, and limited-energy units. The algorithm exploits the special nature of the production cost function, which is piecewise linear with respect to the reservoir utilization levels. It achieves the same accuracy as previously developed, less efficient, approaches which require multiple production cost calculations. The proposed algorithm is also more efficient as well as more accurate than heuristic reservoir utilization algorithms, which are prone to inaccuracies when multiple storage units are considered     

Target-pursuing scheduling and routing policies for multiclass queueing networks

We propose a parametric class of myopic scheduling and routing policies for open and closed multiclass queueing networks. In open networks, they steer the state of the system toward a predetermined and fixed target, while, in closed networks they steer instantaneous throughputs toward a fixed target. In both cases, the proposed policies measure distance from the target using a weighted norm. In open networks, we establish that for an L2 norm the corresponding policies are stable. In closed networks, we establish that with proper target selection the corresponding policy is efficient, that is, attains bottleneck throughput in the infinite population limit. In both open and closed networks, the proposed policies are amenable to distributed implementation using local state information. We exploit the work in a previous paper to select appropriate parameter values and outline how optimal parameter values can be computed. We report numerical results indicating that we obtain near-optimal policies (when the optimal can be computed) and significantly outperform heuristic alternatives. This work has applications in a number of areas including optimizing the processing of information in sensor networks.     

System security control and optimal pricing of electricity

Optimal electricity spot pricing internalizes electricity transportation network costs and constraints. We extend spot pricing theory by including system security control issues in the model. The engineering and physics of system security control imposes a need for speed and precision of response. Traditionally this need has been met by central control of centrally owned equipment and little control of customer-owned equipment. We show that socially optimum prices exist which decentralize security control by internalizing its costs. These prices are robust and feasible to determine without unreasonable information requirements by the market maker. Families of optimal prices and price/quantity controls are determined and interpreted. Contingency planning and enhanced centre/market-maker roles are derived. Applications of immediate interest are also discussed, such as pricing of interruptible loads and assignment of power pool reserves. Symmetry between demand side and supply side security control is shown to be optimal.     

Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems

We improve the job specific decomposition Lagrangian relaxation algorithm applied to industry size job shop scheduling problems with more than 10 000 resource constraints. We introduce two new features in the Lagrange multiplier updating procedure. First, the usual solution of all subproblems followed by dual cost estimation and update of multiplier values is replaced by the estimation of a surrogate dual cost function and a more frequent update of multipliers is implemented after each subproblem solution. Second, an adaptive step size in the subgradient based multiplier update is introduced. Asymptotic properties of the surrogate dual cost function are obtained and the proposed algorithmic improvements are evaluated in extensive numerical examples including published data used by other researchers, as well as extensive real industrial scheduling system data.     

One-machine n-part-type optimal setup scheduling: analyticalcharacterization of switching surfaces

The authors consider optimal setup scheduling of a single reliable machine. Production flow of n different part types and the setup process are described by differential equations. Setup change rates are control variables. Necessary conditions on optimal setup changes are characterized analytically, and optimal setup change times are derived for a given setup change sequence. The linearization of optimal setup switching surfaces is derived, indicating the existence of attractors observed in numerical optimal solutions. The approach developed in this paper establishes a strong basis for studying multimachine production systems and for constructing tractable near-optimal numerical solution techniques     

Dynamics and design of a class of parameterized manufacturing flowcontrollers

The optimal production control of failure prone flexible manufacturing systems has received considerable attention. Analytically intractable optimality conditions render near optimal controller design the only available option for realistic size systems. This paper deals with a class of suboptimal feedback control policies that are parameterized over a finite set. In-depth analysis of the dynamics of the controlled system is undertaken and important properties of these dynamics are proven for the first time for multiple part-type systems. These properties provide the theoretical justification of an infinitesimal perturbation analysis-based controller parameter optimization technique whose validity has been previously supported by empirical evidence