Constraint-directed search : a case study of job-shop scheduling
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Published 1 January 1983Open access
Mark S. Fox
Citations530
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
In this thesis, a system called ISIS is presented, which uses a constraint-directed search paradigm to solve the scheduling problem and provides a knowledge representation language for modeling organizations and their constraints.
Abstract
Robotics Institute
Keywords
Computer ScienceEngineering
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
IBM Journal of Research and DevelopmentSome Studies in Machine Learning Using the Game of Checkers
4,355 Citations1959Arthur L. Samuel
A new signature-table technique is described together with an improved book-learning procedure which is thought to be much superior to the linear polynomial method and to permit the program to look ahead to a much greater depth than it otherwise could do.
Artificial IntelligenceStrips: A new approach to the application of theorem proving to problem solving
4,073 Citations1971Richard Fikes, Nils J. Nilsson
A new problem solver called STRIPS is described that attempts to find a sequence of operators in a space of world models to transform a given initial world model into a model in which a given goal formula can be proven to be true.
Sketchpad
1,804 Citations1963Ivan E. Sutherland
The Sketchpad system makes it possible for a man and a computer to converse rapidly through the medium of line drawings, and opens up a new area of man-machine communication.
Artificial IntelligencePlanning in a hierarchy of abstraction spaces
1,163 Citations1974Earl D. Sacerdoti
Examples of the ABSTRIPS system's performance are presented that demonstrate the significant increases in problem-solving power that this approach provides, and some further implications of the hierarchical planning approach are explored.
Understanding Line drawings of Scenes with Shadows
879 Citations1975David L. Waltz
A detailed discussion of the standard approach to computer interpretation of line drawings as three-dimensional scenes as well as some alternative approaches to this approach are discussed.
Elsevier eBooksGPS, A PROGRAM THAT SIMULATES HUMAN THOUGHT
817 Citations1988Allen Newell, Herbert A. Simon
This work shows that the techniques that have emerged for constructing sophisticated problem-solving programs also provide us with new, strong tools for constructing theories of human thinking that finally reveal with great clarity that the free behavior of a reasonably intelligent human can be understood as the product of a complex but finite and determinate set of laws.
IEEE Transactions on Information TheoryThe logic theory machine--A complex information processing system
776 Citations1956Allen Newell, Herbert A. Simon
A complex information processing system that is capable of discovering proofs for theorems in symbolic logic, written in a formal language, of the nature of a pseudo-code, suitable for coding for digital computers is described.
Communications of the ACMProgram development by stepwise refinement
690 Citations1983Niklaus Wirth
The process of successive refinement of specifications is illustrated by a short but nontrivial example, from which a number of conclusions are drawn regarding the art and the instruction of programming.
Elsevier eBooksON THE EPISTEMOLOGICAL STATUS OF SEMANTIC NETWORKS**Prepared in part at Bolt Beranek and Newman Inc. under contracts sponsored by the Defense Advance Research Projects Agency and the Office of Naval Research. The views and conclusions stated are those of the author and should not be interpreted as necessarily representing the official policies, either express or implied, of the Defense Advanced Research Projects Agency or the U.S. Government.
623 Citations1979Ronald J. Brachman
This chapter examines in detail the history of a set of network-structured formalisms for knowledge representation—the so-called “semantic networks,” which were introduced around 1966 as a representation for the concepts underlying English words and were designed expressly to treat concepts as formal representational objects.
Communication with automata
503 Citations1966C. A. Petri
The theory of automata is shown not capable of representing the actual physical flow of information in the solution of a recursive problem and a theory of communication is proposed that yields a means of representation that with equal rigor and simplicity accomplishes more than the theory of synchronous automata.
The HARPY speech recognition system
467 Citations1976B. Lowerre
The HARPY system is the result of an attempt to understand the relative importance of various design choices of two earlier speech recognition systems developed at Carnegie-Mellon University, in which knowledge is represented as a finite state transition network but without the a-priori transition probabilities.
Elsevier eBooksOn Representations of Problems of Reasoning about Actions
268 Citations1981Saul Amarel
The chapter discusses a specific problem of transportation scheduling to evaluate the effects of alternative formulations of this problem on the expected efficiency of mechanical procedures for solving it and also to examine the processes that come into play when a transition takes place from a given problem formulation into a better one.
Artificial IntelligenceA planning system for robot construction tasks
226 Citations1974Scott E. Fahlman
A powerful heuristic control structure enables BUILD to use a number of sophisticated construction techniques in its plans, including the incorporation of pre-existing structure into the final design, pre-assembly of movable sub-structures on the table, and the use of extra blocks as temporary supports and counterweights in the course of the construction.
Artificial IntelligenceThe B∗ tree search algorithm: A best-first proof procedure
188 Citations1979Hans Berliner
The algorithm, which is named B*, finds a proof that an arc at the root of a search tree is better than any other by attempting to find both the best arc atThe root and the simplest proof, in best-first fashion.
Boston studies in the philosophy of scienceScientific Discovery and the Psychology of Problem Solving
186 Citations1977Herbert A. Simon
Artificial IntelligenceMechanizing temporal knowledge
153 Citations1977Ken Kahn, G. Anthony Gorry
The construction of a time specialist is discussed, a program knowledgable about time in general which can be used by a higher level program to deal with the temporal aspects of its problem-solving.
Artificial IntelligenceREF-ARF: A system for solving problems stated as procedures
125 Citations1970Richard Fikes
An effort to design a heuristic problem-solving program which accepts problems stated in a nondeterministic programming language and applies constraint satisfaction methods and heuristic search methods to find solutions.
NUDGE, a Knowledge-based Scheduling Program
102 Citations1979Ira Goldstein, Richard B. Roberts
The NUDGE program uses an extensive knowledge base to debug scheduling requests by supplying typical values for qualitative constraints, supplying missing details and resolving minor inconsistencies, and has served an experimental vehicle for testing advanced representation techniques.
Management ScienceA Computer Aided Decision System
91 Citations1969R. L. Ferguson, Curtis H. Jones
The authors have devised a specific apportionment of the problem environment which permits users of their information system to explore the effects of various combinations of heuristics and programmed decision rules in multi-dimensional, time-variant problem solving.
An examination of a frame-structured representation system
89 Citations1979Mark Stefik
The Unit Package was created for a hierarchical planning application, and is now in use by several AI projects, and compares it with other current knowledge representation languages.
International Joint Conference on Artificial IntelligenceSome necessary conditions for a master chess program
63 Citations1973Hans Berliner
The outline of a model of chess playing that avoids the Horizon Effect and appears extendable to play Master level chess is presented, together with some results already achieved.
A I I E TransactionsInteractive Scheduling: Historical Survey and State of the Art
58 Citations1978Victor B. Godin
The history and current status of the application of interactive man-computer systems in scheduling situations are surveyed, and a scarcity of material on both prototype and operational interactive scheduling systems is cited.
Computer CompactsThe intelligent management system: An overview
50 Citations1983Mark S. Fox
Research in the modeling of organizations, constraint- based job-shop scheduling, organization simulation, user interfaces, and system architecture is described, and examples of working systems are provided.
International Joint Conference on Artificial IntelligenceOn the construction of evaluation functions for large domains
47 Citations1979Hans Berliner
It is shown how to create sensitive evaluation functions and how to avoid stability problems in non-linear functions and two effects, not previously found in the literature: the suicide construction, and the blemish effect.
International Joint Conference on Artificial IntelligenceOn inheritance in knowledge representation
46 Citations1979Mark S. Fox
This paper proposes that in some cases inheritance between concepts is idiosyncratic and does not fit predefined inheritance relations and current methods of specifying inheritance modification and similarity mappings are complex to specify and understand.
Management SciencePriority Update Intervals and Anomalies in Dynamic Ratio Type Job Shop Scheduling Rules
40 Citations1980Nabil R. Adam, Julius Surkis
Ease of implementation of the various procedures in a real world job shop environment is discussed, and a simple modification to remove the anomaly in ratio type dynamic priority rules is suggested.
Exploiting Temporal Knowledge to Organize Constraints.
36 Citations1983Stephen F. Smith
This work is motivated by ongoing research with ISIS, an intelligent scheduling and information system currently being applied to the problem of scheduling job shops, and examples throughout the paper are drawn from this domain.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Hierarchical Production Planning Systems.
35 Citations1977Arnoldo C. Hax, Jonathan Golovin
The development of hierarchical planning systems to support medium range planning and operational decisions in a batch processing production environment and an analysis of the existing methodology to design hierarchical production systems are given.
DSpace@MIT (Massachusetts Institute of Technology)Bargaining between goals
34 Citations1975Ira Goldstein
A bargaining system is designed to handle the problem of scheduling an individual's weekly activities and appointments based on the powerful reasoning strategy of producing a simplified linear plan.
Focus of attention in a distributed-logic speech understanding system
26 Citations2005Frederick Hayes‐Roth, Victor Lesser
A general Attentional control mechanism is developed that facilitates the experimental evaluation of a variety of specific attentional control policies and allows the modular addition of specialized heuristics for the speech understanding task.
International Joint Conference on Artificial IntelligenceExtending a knowledge-based system to deal with ad hoc constraints
23 Citations1981John McDermott, Barbara Steele
Rules are added to R1 that can now accept as input commands that specify how particular components are to be configured Whenever one of the commands becomes relevant, these rules take control, extend the configuration in the direction indicated by the command, and then step aside, allowing Rt's ordinary-case configuration rules to regain control.
Defense Technical Information Center (DTIC)The Causal Representation and Simulation of Physical Mechanisms.
15 Citations1976Chuck Rieger, Milt Grinberg
A theoretical framework and a LISP implementation for describing and simulating the cause-effect behavior of mechanisms, which include any naturally-occurring physical devices and principles whose cause and effect relationships are of use to humans.
I NTERACTI VE FRAME I NSTANTIATION
14 Citations1980Carl Engelman, Ethan A. Scarl +1 more
The representations and algorithms of an implemented software solution are presented and the requirements that interactive frame instantiation imposes on constraint verification are discussed.
Journal of the Operational Research SocietyEvaluation of Value Time Sequencing Rules in a Real World Job Shop
9 Citations1980V. Arumugam, S. Ramani
This paper reports a case study carried out in an Engineering industry manufacturing nineteen types of products against orders to select the sequencing rule that will optimise the combined performance of work-in-process inventory in monetary terms and delivery performance.
The Counterplanning Process: A Model of Decision-Making in Adverse Situations
6 Citations1979Jaime G. Carbonell
Defense Technical Information Center (DTIC)Interactive Scheduling of a Generalized Flowshop.
1 Citations1980Gerald W. McDonald, Thom J. Hodgson
A case history is described which describes the development of an interactive system being used to schedule the starting dates for the overhaul of military aircraft at a Naval Aircraft Rework Facility.