Job shop scheduling with setup times, deadlines and precedence constraints

In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art. Paper presented in New York at MISTA 2005. E. Balas supported by the National Science Foundation through grant DMI-9802773 and by the Office of Naval Research through contract #N00014-97-1-0133.     

On multiple moving objects

This paper explores the motion-planning problem for multiple moving objects. The approach taken consists of assigning priorities to the objects, then planning motions one object at a time. For each moving object, the planner constructs a configuration space-time that represents the time-varying constraints imposed on the moving object by the other moving and stationary objects. The planner represents this space-time approximately, using two-dimensional slices. The space-time is then searched for a collision-free path. The paper demonstrates this approach in two domains. One domain consists of translating planar objects; the other domain consists of two-link planar articulated arms.This report describes research performed at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Michael Erdmann is supported in part by a fellowship from General Motors Research Laboratories. Tomás Lozano-Pérez is supported by an NSF Presidential Young Investigator grant. Support for the Laboratory's Artificial Intelligence research is provided in part by the System Development Foundation, in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494, and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-80-C-0505 and N00014-82-K-0344.     

Mechanism design for policy routing

The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising from an AS’s underlying utility for each route and study the problem of finding a set of routes that maximizes the overall welfare (ie, the sum of all ASes’ utilities for their selected routes). We show that, if the utility functions are unrestricted, this problem is NP-hard even to approximate closely. We then study a natural class of restricted utilities that we call next-hop preferences. We present a strategyproof, polynomial-time computable mechanism for welfare-maximizing routing over this restricted domain. However, we show that, in contrast to earlier work on lowest-cost routing mechanism design, this mechanism appears to be incompatible with BGP and hence difficult to implement in the context of the current Internet. Our contributions include a new complexity measure for Internet algorithms, dynamic stability, which may be useful in other problem domains. Supported in part by ONR grant N00014-01-1-0795 and NSF grantITR-0219018.Supported by ONR grant N00014-01-1-0795 and NSF grant ITR-0219018. Most of this work was done while the author was at Yale University. Supported in part by NSF grants ITR-0121555 and ANI-0207399. This work was supported by the DoD University Research Initiative (URI) program administered by the Office of Naval Research under Grant N00014-01-1-0795. It was presented in preliminary form at the 2004 ACM Symposium on Principles of Distributed Computing [7]. Portions of this work appeared in preliminary form in the second author’s PhD Thesis [16].     

The complexity of planar compliant motion planning under uncertainty

We consider the computational complexity of planning compliant motions in the plane, given geometric bounds on the uncertainty in sensing and control. We can give efficient algorithms for generating and verifying compliant motion strategies that are guaranteed to succeed as long as the sensing and control uncertainties lie within the specified bounds. We also consider the case where a compliant motion plan is required to succeed over some parametric family of geometries. While these problems are known to be intractable in three dimensions, we identify tractable subclasses in the plane.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K.-0334. The author was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory, and in part by the Mathematical Sciences Institute and the National Science Foundation.     

Automated Analysis of Fault-Tolerance in Distributed Systems

A method for automated analysis of fault-tolerance of distributed systems is presented. It is based on a stream (or data-flow) model of distributed computation. Temporal (ordering) relationships between messages received by a component on different channels are not captured by this model. This makes the analysis more efficient and forces the use of conservative approximations in analysis of systems whose behavior depends on such inter-channel orderings. To further support efficient analysis, our framework includes abstractions for the contents, number, and ordering of messages sent on each channel. Analysis of a reliable broadcast protocol illustrates the method.Supported in part by NSF under Grant CCR-9876058 and ONR under Grants N00014-99-1-0358, N00014-01-1-0109, and N00014-02-1-0363.Supported in part by ARPA/RADC grant F30602-96-1-0317, AFOSR grant F49620-00-1-0198, Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory Air Force Material Command USAF under agreement number F30602-99-1-0533, National Science Foundation Grant 9703470, and a grant from Intel Corporation. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of these organizations or the U.S. Government.Some of the material contained herein previously appeared in [32]     

A BGP-based mechanism for lowest-cost routing

The routing of traffic between Internet domains, or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address the problem of interdomain routing from a mechanism-design point of view. The application of mechanism-design principles to the study of routing is the subject of earlier work by Nisan and Ronen [16] and Hershberger and Suri [12]. In this paper, we formulate and solve a version of the routing-mechanism design problem that is different from the previously studied version in three ways that make it more accurately reflective of real-world interdomain routing: (1) we treat the nodes as strategic agents, rather than the links; (2) our mechanism computes lowest-cost routes for all sourcedestination pairs and payments for transit nodes on all of the routes (rather than computing routes and payments for only one sourcedestination pair at a time, as is done in [12,16]); (3) we show how to compute our mechanism with a distributed algorithm that is a straightforward extension to BGP and causes only modest increases in routing-table size and convergence time (in contrast with the centralized algorithms used in [12,16]). This approach of using an existing protocol as a substrate for distributed computation may prove useful in future development of Internet algorithms generally, not only for routing or pricing problems. Our design and analysis of a strategyproof, BGP-based routing mechanism provides a new, promising direction in distributed algorithmic mechanism design, which has heretofore been focused mainly on multicast cost sharing. Supported in part by ONR grants N00014-01-1-0795 and N00014-01-1-0447 and NSF grant CCR-0105337. Supported in part by NSF grants ITR-0081698 and ITR-0121555 and by an IBM Faculty Development Award. Supported by ONR grant N00014-01-1-0795. Supported in part by NSF grants ITR-0205519, ANI-0207399, ITR-0121555, ITR-0081698, ITR-0225660, and ANI-0196514. This work was supported by the DoD University Research Initiative (URI) program administered by the Office of Naval Research under Grant N00014-01-1-0795. It was presented in preliminary form at the 2002 ACM Symposium on Principles of Distributed Computing [5].     

Timing analysis of MRL: A real-time rule-based system

This paper examines issues on how to predict timing behavior of rule-based decision systems for real-time applications. In particular, we focus on the analysis of response time of rule-based programs written in the production system language MRL. The design goal of MRL is to allow programmers to write OPS5-like rule-based programs in a language that is more amenable to formal analysis based on the semantic foundation underlying the language Unity. The language MRL, its analysis algorithms, and its execution system form a package of design tools for programming real-time rule-based decision systems.This project is partly supported by research grants from Office of Naval Research under ONR contract number N00014-89-J-1472 as well as ONR contract number N000014-89-J-1913, by a grant from Texas Advance Technology Program, and also by a grant from Texas Instruments Corporation.     

A note on the optimal pricing and production decisions with price‐driven substitution

Recently, Kim and Bell ( 2011 ) developed a revenue managemnent pricing model with price‐driven substitution. The authors considered production decisions under unlimited production capacity and investigated the impact of price‐driven substitution on a firm's pricing and production decisions. The authors modeled the consumer demands for each market segment as linear additive demand function based on exogenous variables, where demand substitution occurred as a function of price differences between the two products. In this article, we extend this work to examine the impact of a production capacity constraint on the firm's joint pricing and inventory decisions. Based on this extended model, we investigate the impact of price‐driven substitution on a firm's pricing and production decisions where there is a limit on total capacity. We show how revenue managers should adjust prices and production levels to take into account price‐driven substitution under a capacity constraint setting. Both deterministic and stochastic models are developed, and the impact of price‐driven substitution and a capacity constraint on the optimal prices, production levels, and revenues is illustrated.     

Using counterfactuals in knowledge-based programming

This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi [3,4]. The use of counterfactuals is illustrated by designing a protocol in which an agent stops sending messages once it knows that it is safe to do so. Such behavior is difficult to capture in the original framework because it involves reasoning about counterfactual executions, including ones that are not consistent with the protocol. Attempts to formalize these notions without counterfactuals are shown to lead to rather counterintuitive behavior.Received: 15 November 2001, Accepted: 15 April 2004, Published online: 13 July 2004Joseph Y. Halpern: Work supported in part by NSF under grant IRI-96-25901, IIS-0090145, and CTC-0208535, by the Air Force Office of Scientific Research under grant F49620-96-1-0323 and F48620-02-1-0101, and by ONR under grants N00014-00-1-03-41, N00014-01-1-0795, and by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grant N00014-01-1-0795.)A preliminary version of this paper appeared in the Proceedings of the Seventh Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 1998.     

Pricing and inventory carryover strategy considering cost learning effect and strategic consumers

Anticipating the markdown in the future price due to the cost reduction of the firm, more and more consumers tend to delay their purchasing to the later period. Incorporating the strategic behavior of consumers, this paper establishes a two-period production and selling model under dynamic pricing strategy and price commitment strategy respectively, with considering stochastic learning effect in which the firm may or may not have the inventory carryover option. The results show that the firm may hold inventory under dynamic pricing while no inventory is kept under price commitment. Additionally, consumers' patience level enhances the benefit of inventory carryover. Furthermore, for the firm with relatively high farsighted level and low inventory holding cost, the dynamic pricing equipped with inventory carryover outperforms the price commitment strategy. Finally, numerical examples are conducted to analyze the impacts of important parameters on the firm's choice of pricing strategies.     

Infinitesimal Perturbation Analysis and Optimization for Make-to-Stock Manufacturing Systems Based on Stochastic Fluid Models

In this paper we study Make-To-Stock manufacturing systems and seek on-line algorithms for determining optimal or near optimal buffer capacities (hedging points) that balance inventory against stockout costs. Using a zStochastic Fluid Model (SFM), we derive sample derivatives (sensitivities) which, under very weak structural assumptions on the defining demand and service processes, are shown to be unbiased estimators of the sensitivities of a cost function with respect to these capacities. When evaluated based on the sample path of discrete-part systems, we show that these estimators are greatly simplified. Thus, they can be easily implemented and evaluated on line. Though the implementation on discrete-part systems does not necessarily preserve the unbiasedness property, simulation results show that stochastic approximation algorithms that use such estimates do converge to optimal or near optimal hedging points. Supported in part by the National Science Foundation under Grants EEC-0088073 and DMI-0330171, by AFOSR under contract F49620-01-0056, and by ARO under grant DAAD19-01-0610.     

Topological numbering of features on a mesh

Assume we are given ann ×n binary image containing horizontally convex features; i.e., for each feature, each of its row's pixels form an interval on that row. In this paper we consider the problem of assigning topological numbers to such features, i.e., assign a number to every featuref so that all features to the left off in the image have a smaller number assigned to them. This problem arises in solutions to the stereo matching problem. We present a parallel algorithm to solve the topological numbering problem inO(n) time on ann ×n mesh of processors. The key idea of our solution is to create a tree from which the topological numbers can be obtained even though the tree does not uniquely represent the to the left of relationship of the features.The work of M. J. Atallah was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, and the National Science Foundation under Grant DCR-8451393, with matching funds from AT&T. Part of this work was done while he was a Visiting Scientist at the Center for Advanced Architectures project of the Research Institute for Advanced Computer Science, NASA Ames Research Center, Moffett Field, CA 94035, USA. S. E. Hambrusch's work was supported by the Office of Naval Research under Contracts N00014-84-K-0502 and N00014-86K-0689, and by the National Science Foundation under Grant MIP-87-15652. Part of this work was done while she was visiting the International Computer Science Institute, Berkeley, CA 94704, USA. The work of L. E. TeWinkel was supported by the Office of Naval Research under Contract N00014-86K-0689.     

On the parallel-decomposability of geometric problems

There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n ^1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen >p. The goal we seek is to achieve, when solving a problem of sizen >p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen >p as when solving a problem of sizep.The research of M. J. Atallah was supported by the Office of Naval Research under Contracts N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Jyh-Jong Tsay's research was partially supported by the Office of Naval Research under Contract N00014-84-K-0502, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, and the National Science Foundation under Grant DCR-8451393.     

On the wavelet based differentiation matrix

The Daubechies wavelet based differentiation matrix will be constructed for periodic boundary conditions. It will be proved that this matrix displays the very important property of superconvergence. The relationship between Daubechies-based numerical methods and finite difference methods will be seen.This research was supported by AFOSR Grant 90-0093, by DARPA grant N00014-91-4016, and by NSF grant DMS-9211820, in partial fulfillment of a Ph.D. in Applied Mathematics under the guidance of Professor David Gottlieb.     

Addressing real-time constraints in the design of autonomous agents

The Phoenix project is an experiment in the design of autonomous agents for a complex environment. The project consists of a simulator of the environment, a basic agent architecture, and specific implementation of agents based on real-time techniques; the first two parts have been constructed, the third is on-going. The facets of Phoenix that facilitate real-time research are: a simulator parameterized for varying environmental conditions and instrumented to record behaviors, an agent architecture designed to support adaptable planning and scheduling, and methods for reasoning about real-time constraints.This research has been supported by DARPA, # F30602-85-C-0014; the Office of Naval Research, under a University Research Initiative grant, N00014-86-K-0764; the Office of Naval Research, # N00014-88-K0009, and a grant from the Digital Equipment Corporation. We wish to thank Mike Greenberg for his keen understanding of design issues and mastery of programming that made Phoenix what it is today. We also wish to thank Paul Silvey and David Westbrook for their help.     

Particle Swarm Optimization and Pure Adaptive Search in Finish Goods’ Inventory Management

Abstract

Inventory management deals with a tradeoff between the benefits of keeping stocks of goods that allows fulfillment of the customer’s demand, and the cost of carrying inventory. Inventory control techniques are very important components and the most organizations can substantially reduce their costs associated with the flow of materials. This paper presents new inventory management model based on particle swarm optimization and pure adaptive search global optimization algorithm in production-inventory system. The proposed model is focusing on planned level of demand for finished goods, production and raw materials cost, production capacity as the norm, change of the production cost and inventory capital cost, all of which are typical factors in automobile manufacture industry. The model determines different factors such as the minimizing inventory quantity, minimizing inventory value, and minimizing production cost based on demand for production items. The model is tested with original real-world dataset obtained from the automotive company Lear from US and its factory in Novi Sad, Serbia.     

Augmented infinitesimal perturbation analysis: An alternate explanation

Augmented infinitesimal perturbation analysis (APA) was introduced by Gaivoronski [1991] to increase the purview of the theory of Infinitesimal Perturbation Analysis (IPA). In reference [Gaivoronski 1991] it is shown that an unbiased estimate for the gradient of a class of performance measures of DEDS represented bygeneralized semi-Markov processes (GSMPs) (cf. [Glynn 1989] can be expressed as a sum of an IPA-estimate and a term that takes into account the event order changes. In this paper we present an alternate approach to establishing the result of Gaivoronski, and from this we derive a necessary and sufficient condition for the validity of the IPA algorithm for this class of performance measures. Finally we validate our results by simulation examples.This research was supported by the National Science Foundation under grant number ECS-85-15449, Office of Naval Research Grants Nos. N00014-90-K-1093 and N00014-89-J-1023 and by Army Grant No. DAAL-03-86-K-0171.     

Systolic algorithms as programs

We represent a systolic algorithm by a program consisting of one multiple assignment statement that captures its operation and data flow. We use invariants to develop such programs systematically. We present two examples, matrix multiplication and LU-decomposition of a matrix.This work was supported in part by a grant from the Office of Naval Research under grant N00014-85-K-0057For photographs and biographics see Distributed Computing (1986) 1:40–52     

A sensing strategy for the reverse engineering of machined parts

The reverse engineering of machined parts requires sensing an existing part and producing a design (and perhaps a manufacturing process) for it. We have developed a reverse engineering system that has proven effective with a set of machined parts. This paper describes the system, presents some results, and discusses strategy for a new system.This work was supported by ARPA under ARO grant number DAAH04-93-G-0420, DARPA grant N00014-91-J-4123, NSF grant CDA 9024721, and a University of Utah Research Committee grant. All opinions, findings, conclusions or recommendations expressed in this document are those of the authors and do not necessarily reflect the views of the sponsoring agencies.     

时变需求下生产与库存系统的最优控制决策方法

针对供应链中库存随着需求的变化可能导致的积压和对生产(或采购)产生的不利影响,为了更好地协调生产(或采购)并减少产品库存,本文研究了以生产为中心的一类基于库存约束和动态线性时变需求下的多品种、多周期、多循环的生产与库存的最优控制模型,结合应用最优控制理论,给出了一种采用切比雪夫多项式逼近和高斯.切比雪夫数值积分对最优控制问题进行数值求解的方法.最后,对某一时变需求情况下的模型应用MATLAB软件进行了求解,得到了生产(采购)与库存的最优控制策略,有效地保证了供应链系统的持续稳定的循环.