From amci@dcs.ed.ac.uk Thu Jan 20 16:41:10 EST 1994 Article: 20309 of comp.ai Xref: glinda.oz.cs.cmu.edu comp.ai:20309 comp.ai.shells:1379 Newsgroups: comp.ai,comp.ai.shells Path: honeydew.srv.cs.cmu.edu!nntp.club.cc.cmu.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!europa.eng.gtefsd.com!howland.reston.ans.net!pipex!ibmpcug!ibmpcug!exnet!dcs.ed.ac.uk!amci From: amci@dcs.ed.ac.uk (Alistair McIntyre) Subject: Scheduling Summary Message-ID: Sender: cnews@dcs.ed.ac.uk (UseNet News Admin) Organization: Department of Computer Science, University of Edinburgh Date: Thu, 20 Jan 1994 01:53:45 GMT Lines: 905 [Warning 38K of text follows] After sending a request on the subject of scheduling of factory processes to comp.ai on behalf of a friend, I received a large number of replies (28 pages in toto!) as well as several requests for a summary. I would like to express my thanks to all who replied. I have forwarded their responses, which I hope will be of some help to my friend. Friends aside, my own interest in the subject has grown, and the strong connections with constraint programming (the subject on which I wrote my thesis) which many people have suggested make me wonder if I shouldn't just do my PhD in this area. Now if I could just interest an institute and get some funding... Well here's the request I originally sent, followed by a summary of responses received. Once again, thank you all. > REQUEST: > I wonder if anyone out there can help, either with pointers to the > literature, tips, or best of all a *specific commercial package* to > help optimise the scheduling of operations in a manufacturing plant > to maximise plant efficiency. I recognise that it is likely that > finding an optimal solution may well be (close to) impossible, but > the closer the better. > > QUICK SUMMARY: > We need to dynamically adjust a schedule of operations to process > a stream of requests for products, whilst satisfying a number of > constraints. Fault-tolerance would be desirable. > > PROBLEM OUTLINE: > We have a schedule of promised deliveries to the customers, and a set > of constraints which we have to overcome to achieve this. The constraints > are along lines of the following: > > 1) We have a maximum capacity per time period for all products > (eg 6 pieces per day), but we can increase this by adding tools. > 2) We have constraint on the maximum number of materials used at any > particular station. > 3) We have a certain capacity of number of tools at a particular station. > 4) We have a certain number of stations that a particular product can be > made on. > > Maintenance/breakdown may make a station unavailable, thus requiring > re-scheduling around the problem. > > NOTES: > The plant is in operation more or less continuously, so it is really > a case of figuring out how to adjust the schedule as new requests for > products enter the system. > > RELATED AREAS? > * Dynamic scheduling of instruction issues in a superscalar microprocessor. > * Process allocation in a fault-tolerant multiprocessing environment. > * Critical path analysis. > > REQUEST ENDS -------------- THE SCHEDULING LIST-SERVER -------------------------- A number of people recommended subscribing to the scheduling list-server by sending listserver@vexpert.dbai.tuwien.ac.at the following single line: SUB SCHED-L Name SUMMARY OF RESPONSES -------------------- From: amziod@world.std.com (Merritt) Recommends contacting: Trinzic (nee AICorp), Waltham MA Several customers have implemented schedulers such as Frito-Lay, Lay-Z-Boy, etc using their forward chaining KBMS expert system shell. Bethlehem Steel schedules rolled steel production too. From: Juergen Dorn Suggests using iterative improvement algorithms; Tabu Search, GAs, Min-Conflicts, Simulated Annealing. Recommends subscribing to scheduling list-server (see top) From: Hester Tom Represents ADS, who supply a Constraint Based Scheduling Package in C++; Resource Allocation and Scheduling Libraries; not commercially available. You should contact the company who will co-operate to help solve problem. From: Ingemar Hulthage Paper enclosed: "Using Search for Efficient and Optimal Scheduling" in "Methodologies for Intelligent Systems 5" Z. W. Ras, M. Zemankova and M.L. Emrich (editors), Elsevier 1990. See [attachment 1] below for this paper's abstract and bibilography. From: Ilog UK Suppliers of ILOG modular C++ software components: ILOG Builder, ILOG Views, ILOG DB Link, ILOG Rules, ILOG Solver, ILOG Schedule Peter Kibble, 0483 440388, ILOG UK Send snail-mail address for details on paper. From: lepape@ilog.fr (Claude Le Pape) Supplied a large list of references biased towards generative constraint-based scheduling, subdivided into the following categories: 'MOST CLASSICAL OPERATIONS RESEARCH BOOKS ON SCHEDULING'; 'CONSTRAINT-BASED (OR-AI) & AI-ORIENTED SCHEDULING'; 'PROPAGATION OF TEMPORAL AND/OR CAPACITY CONSTRAINTS'; 'RECENT REVIEWS AND WORKSHOP REPORTS'. See [attachment 2] below. Claude recommends subscribing to scheduling list-server (see top). From: Russ Mannex Representative of Inference Corporation, recommends ART*Enterprise. Europe sales office, Slough, UK (753) 811-855 From: Joseph Pemberton Recommends scheduling list-server (see top). Suggests contacting Prof. Thomas Morton at CMU for scheduling from operations research perspective. From: "Thierry Pretet (Math Info" Recommends solution by constraint programming, suggesting ILOG's PECOS constraint programming environment, on top of LISP or C++. Gives contact: ILOG, SA; 2, av. Gallieni; BP 85; 94253 Gentilly CEDEX; France tel +33 (1) 46-63-66-66 fax +33 (1) 46-63-15-82 e-mail info@ilog.fr From: Mark Wallace Recommends using constraint logic programming for scheduling, using their ECLiPSe tool at around 100 pounds for academic use. If interested in commercial usage, you are to be referred to someone else for deals. Those interested in ECLiPSe, contact micha@ecrc.de Paper on CLP scheduling paper available by anonymous ftp from 'ecrc.de:pub/mark/scheduling.ps.Z' From: "Van D. Parunak" Has been working with industrial firms on a distributed approach in which the shop is seen as a collection of autonomous agents which respond locally to their environment, with collective behaviour emergently defining the schedule in real time, as opposed to a statically imposed hierarchical schedule ahead of time. There is a related paper in Encapsulated PostScript available by anonymous ftp from 'iti.org:pub/incoming/daiapps.eps', to appear in 'Foundations of Distributed Artificial Intelligence' by Nick Jennings, pub. Wiley Inter-Science later this year. From: Cyrus Hadavi Represents a company having a scheduling package which can optimize the efficiency of the operations in a factory. From: Jan.Carsten.Gjerlow@si.sintef.no Has surveyed commercial scheduling systems for the Norwegian market. Report reviews 40 different software systems for scheduling and manufacturing simulation. It is written in Norwegian, but most of the systems come from UK/USA/D, most addresses given are suppliers from these countries. From: S.Rai@bnr.co.uk Used DecisionPower for this sort of problem, but found dynamic adjustments infeasible. Currently using IlogSolver, 'appears to have extremely powerful capabilities for customising constraints, and backtracking algorithms'. Contact: John Kelly, Ilog Ltd., Surrey Technology Park, 40 Occam Rd., Guildford, GU2 5YH, tel: 0483 440388. ------------------------------------------------------------------------ [ ] [ ATTACHMENT 1 ] [ ] ------------------------------------------------------------------------ Abstract and Bibliography extracted from a paper kindly sent to me by: Ingemar Hulthage Associate Professor Computational Organization Design University of Southern California USING SEARCH FOR EFFICIENT AND OPTIMAL SCHEDULING Ingemar A. E. Hulthage Carnegie Mellon Research Institute 4400 Fifth Avenue Pittsburgh, PA 15213 ARPAnet: iaeh@cs.cmu.edu and Stephen E. Morrisson School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 ARPAnet: sem@cs.cmu.edu 27 March 1990 (Revised 4:43 pm, 1 August, 1990) Appearing in the Fifth International Symposium on Methodologies for Intelligent Systems Knoxville, Tennessee, October 25-27, 1990. Copyright ) 1990 Carnegie Mellon Research Institute ABSTRACT The problem of using search techniques to find optimal sequences of actions for realistic problems is addressed. The search technique used is based on A* with a generalized node comparison relation. Nodes are compared on three sequential main levels by: the multiobjective optimality criterium, the completeness criterium and finally by other preferences and search heuristics. We discuss in detail how this search algorithm can be applied to interesting scheduling problems of moderate size. REFERENCES 1. Henein H., Hulthage I. and Morrisson S., ``Billet sequencing of open die forging of alloy 718'', In preparation 2. Pareto, V., Cors d'Economie Politique, Rouge, Lausanne, Switzerland, 1896. 3. Hulthage I., ``Reasoning with Models in Artificial Intelligence'', in Methodologies for Intelligent Systems IV, Ras Z.W., ed., North Holland, New York, 1989. 4. Carnegie Group Inc., Knowledge Craft, Version 3.1, Five PPG Place, Pittsburgh, PA 15222, 1986, Knowledge Craft is a trademark of Carnegie Group Inc. 5. Ingerslev P. and Henein H., ``An analytical mathematical model for calculation of two dimensional heatflow in cylindrical ingots'', Tech.report, University of Alberta, Department of Mining Metallurgical & Petroleum Engineer- ing, 1990. 6. Hart P.E., ``A formal basis for the heuristic determination of minimum cost paths'', IEEE Trans. System Science and Cybernetics, Vol. SSC-4, No. 2, 1968, pp. 100-107. 7. Pearl J., ``On the discovery and generation of certain heuristics'', AI Magazine, No. 22-23, 1983. 8. Dechter R.and Pearl J., ``The Optimality of A*'', in Search in Artificial Intelligence, Springer-Verlag, New York, SYMBOLIC COMPUTATION - Artificial Intelligence, 1988, pp. 166-199, ch.5. 9. Harris L.R., ``The heuristic search under conditions of error'', Artificial Intelligence, Vol. 5, No. 3, 1974, pp. 217-234. 10. Beckmann M. et al., editors, Sequencing Theory, Springer-Verlag, New York, Lecture Notes in Economics and Mathematical Systems, Vol. 69, 1972, (see section 3.3) 11. Korf R.E., ``Optimal Path-Finding Algorithms'', in Search in Artificial Intelligence, Springer-Verlag, New York, SYMBOLIC COMPUTATION - Artificial Intelligence, 1988, pp. 223-267, ch. 7. ------------------------------------------------------------------------ [ ] [ ATTACHMENT 2 ] [ ] ------------------------------------------------------------------------ Copy of list of references kindly sent to me by lepape@ilog.fr (Claude Le Pape) of ILOG. ------------------------------------------------------ MOST CLASSICAL OPERATIONS RESEARCH BOOKS ON SCHEDULING ------------------------------------------------------ Kenneth R. Baker. Introduction to Sequencing and Scheduling. John Wiley and Sons, 1974. Jacques Carlier et Philippe Chretienne. Problemes d'ordonnancement : Modelisation / Complexite / Algorithmes. Masson, 1988. Edward G. Coffman Jr. (editor). Computers and Job-Shop Scheduling Theory. John Wiley and Sons, 1976. ----------------------------------- RECENT REVIEWS AND WORKSHOP REPORTS ----------------------------------- Stephen C. Graves. A Review of Production Scheduling. Operations Research, 29(4):646-675, 1981. Karl G. Kempf. Manufacturing Planning and Scheduling: Where We Are and Where We Need To Be. Proceedings of the IEEE International Conference on Artificial Intelligence Applications, Miami, Florida, 1989. Karl Kempf, Claude Le Pape, Stephen F. Smith and Barry R. Fox. Issues in the Design of AI-Based Schedulers: A Workshop Report. AI Magazine, 11(5):37-46, 1991. ABSTRACT: Based on the experience in manufacturing production scheduling which the AI community has amassed over the last ten years, a workshop was held to provide a forum for discussion of the issues encountered in the design of AI-based scheduling systems. Several topics were addressed including: the relative virtues of expert systems, deep methods and interactive approaches, the balance between predictive and reactive components in a scheduling system, the maintenance of convenient schedule descriptions, the application of the ideas of chaos theory to scheduling, the state of the art in schedulers which learn, and the practicability and desirability of a set of benchmark scheduling problems. This article expands on these issues, abstracts the papers which were presented, and summarizes the lengthy discussions that took place. Karl Kempf, Bruce Russell, Sanjiv Sidhu and Stu Barrett. AI-Based Schedulers in Manufacturing Practice: Report of a Panel Discussion. AI Magazine, 11(5):46-55, 1991. ABSTRACT: There is a great disparity between the number of papers which have been published about AI-based manufacturing scheduling tools and the number of systems which are in daily use by manufacturing engineers. It is argued that this is not a reflection of inadequate AI technology, but is rather indicative of a lack of a systems perspective by AI practitioners and their manufacturing customers. Case studies to support this perspective are presented by Carnegie Group as a builder of scheduling systems for its customers, by Texas Instruments and Intel Corporation as builders of schedulers for their own use, and by Intellection as a consulting house specializing in scheduling problems. Mitchell S. Steffen. A Survey of Artificial Intelligence-Based Scheduling Systems. Proceedings of the Fall Industrial Engineering Conference, Boston, Massachusetts, 1986. ------------------------------------------------- CONSTRAINT-BASED (OR-AI) & AI-ORIENTED SCHEDULING ------------------------------------------------- S. M. Alexander. An Expert System for the Selection of Scheduling Rules in a Job-Shop. Computers and Industrial Engineering, 12(3):167-171, 1987. David Applegate and William Cook. A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing, 3(2):149-156, 1991. Howard Beck. Constraint Monitoring in TOSCA. Working Papers of the AAAI Spring Symposium on Practical Approaches to Planning and Scheduling, Stanford, California, 1992. Gerard Bel et Didier Dubois. Potentialite des techniques de l'intelligence artificielle pour l'elaboration de regles de conduite d'un atelier de production. Actes du colloque ``Productique et Robotique'', Bordeaux, France, 1984. Gerard Bel, Eric Bensana et Didier Dubois. Un systeme d'ordonnancement previsionnel d'atelier utilisant des connaissances theoriques et pratiques. Sixiemes journees internationales sur les systemes experts et leurs applications, Avignon, France, 1986. Eric Bensana. Utilisation de techniques d'intelligence artificielle pour l'ordonnancement d'atelier. These de docteur-ingenieur, ENSAE, Toulouse, 1987. Pauline M. Berry. Satisfying Conflicting Objectives in Factory Scheduling. Proceedings of the IEEE International Conference on Artificial Intelligence Applications, Santa Barbara, California, 1990. Pauline M. Berry. A Predictive Model for Satisfying Conflicting Objectives in Scheduling Problems. PhD Thesis, University of Strathclyde, 1991. Pauline M. Berry. SCHEDULING: A Problem of Decision-Making Under Uncertainty. Proceedings of the Tenth European Conference on Artificial Intelligence, Vienna, Austria, 1992 Pauline M. Berry. The PCP: A Predictive Model for Satisfying Conflicting Objectives in Scheduling Problems. Artificial Intelligence in Engineering, 7:227-242, 1992. Peter Burke and Patrick Prosser. A Distributed Asynchronous System for Predictive and Reactive Scheduling. Technical Report, University of Strathclyde, 1989. Peter Burke. Scheduling in Dynamic Environments. PhD Thesis, University of Strathclyde, 1989. ABSTRACT: Much of the work in the area of automated scheduling systems is based on the assumption that the intended execution environment is static and deterministic. The work presented in this thesis is motivated by recognition of the fact that most real-world scheduling environments are dynamic and stochastic. It views the scheduling task as one of satisfaction rather than optimization, and maintenance over creation. This thesis reviews existing work in the area and identifies an opportunity to combine recent advances in scheduling technology with the power of distributed processing. Within a suitable problem-solving architecture it is argued that this combination can help to address the fondamental problems of executional uncertainty, conflicting objectives and combinatorial complexity. A scheduling system, DAS, which employs such a problem-solving architecture, is presented. It is distributed, asynchronous and hierarchical, and requires careful management of problem-solving effort. DAS adopts a opportunistic approach to problem-solving and the management of problem-solving effort. The mechanisms which manage problem-solving effort within DAS are also presented. In conclusion it is argued that the architecture and mechanisms presented lend themselves very well to the view taken of the scheduling task. Jacques Carlier. Problemes d'ordonnancement a contraintes de ressources : algorithmes et complexite. These de Doctorat d'Etat, Universite Paris VI, 1984. Jacques Carlier and Eric Pinson. An Algorithm for Solving the Job-Shop Problem. Management Science, 35(2):164-176, 1989. Jacques Carlier and Eric Pinson. A Practical Use of Jackson's Preemptive Schedule for Solving the Job-Shop Problem. Annals of Operations Research, 26:269-287, 1990. Yves Caseau, Pierre-Yves Guillo and Eric Levenez. A Deductive and Object-Oriented Approach to a Complex Scheduling Problem. Proceedings of the International Conference on Deductive and Object-Oriented Databases, 1993. Anne Collinot, Claude Le Pape and Gerard Pinoteau. SONIA: A Knowledge-Based Scheduling System. International Journal for Artificial Intelligence in Engineering, 3(2):86-94, 1988. Anne Collinot. Le probleme du controle dans un systeme flexible d'ordonnancement. These de l'Universite Paris VI, 1988. Anne Collinot and Claude Le Pape. Adapting the Behavior of a Job-Shop Scheduling System. International Journal for Decision Support Systems, 7(3):341-353, 1991. ABSTRACT: Factory scheduling consists in assigning resources (e.g. machines) and start and end times to operations. Our work is concerned with the problems of schedule generation and schedule revision when unanticipated events occur on the factory floor. SONIA is a knowledge-based scheduling system provided with a blackboard architecture for coordinating the activation of various scheduling and analyzing knowledge sources. In this paper, we focus on the various behaviors these knowledge sources can have and gather a collection of conclusions regarding the use of various backtracking strategies and the control of constraint propagation. Yannick Descotte et Herve Delesalle. Une architecture de systeme expert pour la planification d'activite. Sixiemes journees internationales sur les systemes experts et leurs applications, Avignon, France, 1986. Jacques Erschler. Analyse sous contraintes et aide a la decision pour certains problemes d'ordonnancement. These de Doctorat d'Etat, Universite Paul Sabatier, 1976. Patrick Esquirol. Regles et processus d'inference pour l'aide a l'ordonnancement de taches en presence de contraintes. These de l'Universite Paul Sabatier, 1987. Pierre Lopez. Approche energetique pour l'ordonnancement de taches sous contraintes de temps et de ressources. These de l'Universite Paul Sabatier, 1991. Barry R. Fox and Karl G. Kempf. Opportunistic Scheduling for Robotic Assembly. Proceedings of the IEEE International Conference on Robotics and Automation, Saint Louis, Missouri, 1985. Barry R. Fox and Karl G. Kempf. Reasoning about Opportunistic Schedules. Proceedings of the IEEE International Conference on Robotics and Automation, Raleigh, North Carolina, 1987. Barry R. Fox. Mixed Initiative Scheduling. Proceedings of the AAAI Spring Symposium on Artificial Intelligence in Scheduling, Stanford, California, 1989. Barry R. Fox. Chronological and Non-Chronological Scheduling. Proceedings of the First Annual Conference on Artificial Intelligence, Simulation and Planning in High Autonomy Systems, Tucson, Arizona, 1990. Mark S. Fox. Constraint-Directed Search: A Case Study of Job-Shop Scheduling. PhD Thesis, Carnegie-Mellon University, 1983. Mark S. Fox and Stephen F. Smith. ISIS: A Knowledge-Based System for Factory Scheduling. Expert Systems, 1(1):25-49, 1984. ABSTRACT: Analysis of the job shop scheduling domain has indicated that the crux of the scheduling problem is the determination and satisfaction of a large variety of constraints. Schedules are influenced by ssuch diverse and conflicting factors as due-date requirements, cost restrictions, production levels, machine capabilities and subsitutatibility, alternative production processes, order characteristics, resource requirements, and resource availability. This paper describes ISIS, a scheduling system capable of incorporating all relevant constraints in the construction of job-shop schedules. We examine both the representation of constraints within ISIS, and the manner in which these constraints are used in conducting a constraint-directed search for an admissible schedule. The important issues relating to the relaxation of constraints are addressed. Finally, the interactive scheduling facilities provided by ISIS are considered. Ira P. Goldstein. Bargaining Between Goals. Proceedings of the Fourth International Joint Conference on Artificial Intelligence, Tbilissi, USSR, 1975. Ira P. Goldstein and Bruce R. Roberts. NUDGE: A Knowledge-Based Scheduling Program. Proceedings of the Fifth International Joint Conference on Artificial Intelligence, Cambridge, Massachusetts, 1977. William P.-C. Ho. A Meta-Planning Model for Diminishing Resource Problems. International Journal for Artificial Intelligence in Engineering, 3(2):114-120, 1988. Gerald Kelleher. Emerging Reason Maintenance System Technologies and Their Application to Constraint-Based Scheduling. Proceedings of the Twelfth UK Planning SIG, Cambridge, United Kingdom, 1993. Gerald Kelleher and Philippe Retif. Controlling Constraint-Based Scheduling Using Focussed RMS. Proceedings of the AAAI-SIGMAN Workshop on Knowledge-Based Production Planning, Scheduling and Control, IJCAI, Chambery, France, 1993. Naiping Keng and David Y. Y. Yun. A Planning/Scheduling Methodology for the Constrained Resource Problem. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, Michigan, 1989. R. M. Kerr and R. N. Walker. A Job-Shop Scheduling System Based on Fuzzy Arithmetic. Proceedings of the Third International Conference on Expert Systems and the Leading Edge in Production Planning and Control, Charleston, South Carolina, 1989. Claude Le Pape. SOJA: A Daily Workshop Scheduling System. SOJA's System and Inference Engine. Proceedings of the Fifth Technical Conference of the British Computer Society Specialist Group on Expert Systems, Warwick, United Kingdom, 1985. Claude Le Pape. Des systemes d'ordonnancement flexibles et opportunistes. These de l'Universite Paris XI, 1988. Claude Le Pape. A Combination of Centralized and Distributed Methods for Multi-Agent Planning and Scheduling. Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati, Ohio, 1990. Claude Le Pape. Constraint Propagation in Planning and Scheduling. Technical Report, Stanford University, 1991. Claude Le Pape. Programmation par contraintes et ordonnancement : realites et perspectives. Actes du deuxieme congres ``Systemes Experts en Informatique de Gestion'', Nice, France, 1992. Claude Le Pape. Solving Scheduling Problems with Constraint Propagation and a Blackboard System. Information Technology (Journal of the Singapore Computer Society), 5(2):19-26, 1993. Claude Le Pape. Using Object-Oriented Constraint Programming Tools to Implement Flexible ``Easy-to-use'' Scheduling Systems. Proceedings of the NSF Workshop on Intelligent, Dynamic Scheduling for Manufacturing, Cocoa Beach, Florida, 1993. Claude Le Pape. A Universal Constraint-Based Representation of Time-Tables: Benefits and Costs ... and Benefits. Proceedings of the AAAI-SIGMAN Workshop on Knowledge-Based Production Planning, Scheduling and Control, IJCAI, Chambery, France, 1993. ABSTRACT: The resolution of industrial scheduling problems often requires the representation of time-tables to precisely define the availability of different types of resources over time. A generic framework for the representation of resource time-table constraints is presented. The framework allows the definition of ``tables of variables'' (representing variables the value of which are functions of some parameter, typically time) as part of the Ilog Solver object-oriented constraint programming library. Such a generic framework is known to have many advantages, from the sharing of source code to better opportunities for extension of completed applications. Yet a potential drawback of genericity is the overhead cost (in CPU time) encountered when running applications. Experiments made to evaluate the overhead cost incurred by the use of generic time-tables are described. The resulting average overhead of 23% is deemed very satisfactory given the fact that the generic framework allowed a significant reduction (50%) of the size of the source code, starting from an already compact Ilog Solver implementation. Claude Le Pape. The Cost of Genericity: Experiments with Constraint-Based Representations of Time-Tables. Proceedings of the Sixth International Conference on Software Engineering and its Applications, Paris-La Defense, France, 1993. Bing Liu. Scheduling via Reinforcement. International Journal for Artificial Intelligence in Engineering, 3(2):76-85, 1988. Mary Beth McMahon and Jack Dean. A Simulated Annealing Approach to Schedule Optimization for the SES Facility. Proceedings of the AAAI Spring Symposium on Artificial Intelligence in Scheduling, Stanford, California, 1989. David H. Mott, Jon Cunningham, Gerry Kelleher and Julie A. Gadsden. Constraint-Based Reasoning for Generating Naval Flying Programmes. Expert Systems, 5(3):226-246, 1988. Nicola Muscettola and Stephen F. Smith. A Probabilistic Framework for Resource-Constrained Multi-Agent Planning. Proceedings of the Tenth International Joint Conference on Artificial Intelligence, Milan, Italy, 1987. Peng Si Ow and Stephen F. Smith. Towards an Opportunistic Scheduling System. Proceedings of the Nineteenth Hawaii International Conference on System Sciences, Kona, Hawaii, 1986. Peng Si Ow and Stephen F. Smith. Two Design Principles for Knowledge-Based Systems. Decision Sciences, 18(3):430-447, 1987. Peng Si Ow, Stephen F. Smith and Alfred Thiriez. Reactive Plan Revision. Proceedings of the Seventh National Conference on Artificial Intelligence, Saint Paul, Minnesota, 1988. H. Van Dyke Parunak. Manufacturing Experience With the Contract Net. Proceedings of the Fifth Workshop on Distributed Artificial Intelligence, Sea Ranch, California, 1985. Eric Pinson. Le probleme de job-shop. These de l'Universite Paris VI, 1988. Patrick Prosser. Distributed Asynchronous Scheduling. PhD Thesis, University of Strathclyde, 1990. Jean-Marie Proth, Joel Quinqueton, H. Ralambondrainy et Kosta Voyiatzis. Utilisation de l'intelligence artificielle dans un probleme d'ordonnancement. Actes du congres ``Automatique, Productique et Robotique Intelligente'', Besancon, France, 1983. Christophe Roche. EAQUE-LRO. Generation de systemes experts. Application a des problemes d'ordonnancement. These de troisieme cycle, Institut National Polytechnique de Grenoble, 1984. Norman Sadeh and Mark S. Fox. Focus of Attention in an Activity-Based Scheduler. Proceedings of the NASA Conference on Space Telerobotics, Pasadena, California, 1989. Norman Sadeh and Mark S. Fox. Variable and Value Ordering Heuristics for Activity-Based Job-Shop Scheduling. Proceedings of the Fourth International Conference on Expert Systems in Production and Operations Management, Hilton Head, South Carolina, 1990. Norman Sadeh. Look-Ahead Techniques for Micro-Opportunistic Job-Shop Scheduling. PhD Thesis, Carnegie-Mellon University, 1991. James R. Slagle and Henry Hamburger. An Expert System for a Resource Allocation Problem. Communications of the ACM, 28(9):994-1004, 1985. Stephen F. Smith and Peng Si Ow. The Use of Multiple Problem Decompositions in Time-Constrained Planning Tasks. Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, California, 1985. Stephen F. Smith, Peng Si Ow, Claude Le Pape, Bruce McLaren and Nicola Muscettola. Integrating Multiple Scheduling Perspectives to Generate Detailed Production Plans. Proceedings of the SME Conference on Artificial Intelligence in Manufacturing, Long Beach, California, 1986. Stephen F. Smith, Peng Si Ow, Claude Le Pape and Nicola Muscettola. Reactive Management of Factory Schedules. Technical Report, Carnegie-Mellon University, 1986. Stephen F. Smith, Mark S. Fox and Peng Si Ow. Constructing and Maintaining Detailed Production Plans: Investigations into the Development of Knowledge-Based Factory Scheduling Systems. AI Magazine, 7(4):45-61, 1986. ABSTRACT: To be useful in practice, a factory production schedule must reflect the influence of a large and conflicting set of requirements, objectives and preferences. Human schedulers are typically overburdened by the complexity of this task, and conventional computer-based scheduling systems consider only a small fraction of the relevant knowledge. This article describes research aimed at providing a framework in which all relevant scheduling knowledge can be given consideration during schedule generation and revision. Factory scheduling is cast as a complex constraint-directed activity, driven by a rich symbolic model of the factory environment in which various influencing factors are formalized as constraints. A variety of constraint-directed inference techniques are defined with respect to thsi model to provide a basis for intelligently compromising among conflicting concerns. Two knowledge-based factory scheduling systems that implement aspects of this approach are described. Stephen F. Smith. A Constraint-Based Framework for Reactive Management of Factory Schedules. Proceedings of the First International Conference on Expert Systems and the Leading Edge in Production Planning and Control, Charleston, South Carolina, 1987. Stephen F. Smith and Juha E. Hynynen. Integrated Decentralization of Production Management: An Approach for Factory Scheduling. Proceedings of the ASME Annual Winter Conference, Boston, Massachusetts, 1987. Stephen F. Smith, Naiping Keng and Karl G. Kempf. Exploiting Local Flexibility During Execution of Pre-Computed Schedules. Technical Report, Carnegie-Mellon University, 1990. Katia Sycara, Stephen Roth, Norman Sadeh and Mark S. Fox. An Investigation into Distributed Constraint-Directed Factory Scheduling. Proceedings of the IEEE International Conference on Artificial Intelligence Applications, Santa Barbara, California, 1990. ABSTRACT: We present an approach to focus search in a distributed system in which individual agents search spaces so as to optimize decisions in the global space. The chosen domain is distributed factory scheudling. The importance of distributed decision-making in factory environments arises from the fact that factories are inherently distributed, and from the need of effective responsiveness to change. The approach relies on a set of ``texture measures'' that quantify several characteristics of the space being searched. These textures play four important roles in distributed search: (1) they focus the attention of an agent to globally critical decision points in its local search space, (2) they provide guidance in making a particular decision at a decision point, (3) they are good predictive measures of the impact of local decisions on system goals, and (4) they are used to model beliefs and intentions of other agents. The development of the presented texture neasures is the result of extensive experimentation in a single agent setting. We have completed the implementation of a distributed testbed and are currently performing experiments involving multiple agents. Katia P. Sycara, Steven F. Roth, Norman Sadeh and Mark S. Fox. Resource Allocation in Distributed Factory Scheduling. IEEE Expert, 6(1):29-40, 1991. --------------------------------------------------- PROPAGATION OF TEMPORAL AND/OR CAPACITY CONSTRAINTS --------------------------------------------------- Abderrahmane Aggoun and Nicolas Beldiceanu. Extending CHIP in Order to Solve Complex Scheduling and Placement Problems. Premieres journees francophones sur la programmation en logique, Lille, France, 1992. James F. Allen. An Interval-Based Representation of Temporal Knowledge. Proceedings of the Seventh International Joint Conference on Artificial Intelligence, Vancouver, Canada, 1981. James F. Allen. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 26(11):832-843, 1983. James F. Allen. Towards a General Theory of Time. Artificial Intelligence, 23(2):123-154, 1984. Colin E. Bell and Austin Tate. Using Temporal Constraints to Restrict Search in a Planner. Technical Report, University of Edinburgh, 1984. Anne Collinot and Claude Le Pape. Controlling Constraint Propagation. Proceedings of the Tenth International Joint Conference on Artificial Intelligence, Milan, Italy, 1987. Malik Ghallab and Amine Mounir Alaoui. Managing Efficiently Temporal Relations Through Indexed Spanning Trees. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, Michigan, 1989. Malik Ghallab et Amine Mounir Alaoui. Relations temporelles symboliques : representations et algorithmes. Revue d'intelligence artificielle, 3(3):67-115, 1989. Peter B. Ladkin and Roger D. Maddux. On Binary Constraint Networks. Technical Report, Kestrel Institute, 1988. Claude Le Pape and Stephen F. Smith. Management of Temporal Constraints for Factory Scheduling. Proceedings of the Working Conference on Temporal Aspects in Information Systems, Sophia-Antipolis, France, 1987. Pierre Lopez. Approche energetique pour l'ordonnancement de taches sous contraintes de temps et de ressources. These de l'Universite Paul Sabatier, 1991. Jean-Francois Rit. Propagating Temporal Constraints for Scheduling. Proceedings of the Fifth National Conference on Artificial Intelligence, Philadelphia, Pennsylvania, 1986. Jean-Francois Rit. Modelisation et propagation de contraintes temporelles pour la planification. These de l'Institut National Polytechnique de Grenoble, 1988. Eric Rutten and Lionel Marce. Temporal Logics Meet Telerobotics. Proceedings of the NASA Conference on Space Telerobotics, Pasadena, California, 1989. Norman Sadeh and Mark S. Fox. Preference Propagation in Temporal/Capacity Constraint Graphs. Technical Report, Carnegie-Mellon University, 1989. Stephen F. Smith. Exploiting Temporal Knowledge to Organize Constraints. Technical Report, Carnegie-Mellon University, 1983. Peter Van Beek. Approximation Algorithms for Temporal Reasoning. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, Michigan, 1989. Peter Van Beek. Reasoning about Qualitative Temporal Information. Proceedings of the Eighth National Conference on Artificial Intelligence, Boston, Massachusetts, 1990. Steven A. Vere. Planning in Time: Windows and Durations for Activities and Goals. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5(3):246-267, 1983. Marc Vilain. A System for Reasoning about Time. Proceedings of the Second National Conference on Artificial Intelligence, Pittsburgh, Pennsylvania, 1982. Marc Vilain and Henry Kautz. Constraint Propagation Algorithms for Temporal Reasoning. Proceedings of the Fifth National Conference on Artificial Intelligence, Philadelphia, Pennsylvania, 1986. -------------------- END OF TEXT --------------------