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: <CJwnxL.Hz8@dcs.ed.ac.uk>
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 <dorn@vexpert.dbai.tuwien.ac.at>
Suggests using iterative improvement algorithms; Tabu Search,
GAs, Min-Conflicts, Simulated Annealing.
Recommends subscribing to scheduling list-server (see top)
From: Hester Tom <hester_tom@smtpmac.bah.com>
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 <hulthage@torsk.usc.edu>
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 <iloguk@cix.clink.co.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 <mannex@inference.com>
Representative of Inference Corporation, recommends
ART*Enterprise. Europe sales office, Slough, UK (753) 811-855
From: Joseph Pemberton <pemberto@CS.UCLA.edu>
Recommends scheduling list-server (see top).
Suggests contacting Prof. Thomas Morton at CMU for scheduling
from operations research perspective.
From: "Thierry Pretet (Math Info" <pretet@iremia.fr>
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 <Mark.Wallace@ecrc.de>
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" <van@iti.org>
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 <cyrus_hadavi@intellection.com>
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 <hulthage@torsk.usc.edu>
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 --------------------